Register to reply 
Discrete Math  a modulus proof 
Share this thread: 
#1
Sep1508, 10:06 PM

P: 58

1. The problem statement, all variables and given/known data
I have to prove the following claim. Claim: For any positive integers m and n, m and n both greater than 1, if nm and a≡b(mod m), then a≡b(mod n). 2. Relevant equations n/a 3. The attempt at a solution so i first changed each equation (ex: a≡b(mod m)) to a=b+qm and a=b+qn I figured in these forms I could show that the equations are equal. so I eventually get (ab)/q=m or =n respectively. So I believe this shows their equality, but i am completely unsure because it won't always work I don't think. I need to also show that nm. So tired dividing the m=(ab)/q by the n= equation and of course I just get 1... To be completely honest I am not quite sure how to prove this. I am not quite familiar with the mod function and I am incredibly weak with proofs. If anyone can give me insight into solving this problem I would great appreciative. also note that this should be able to be done with a direct proof. thanks! 


#2
Sep1508, 10:28 PM

Sci Advisor
HW Helper
Thanks
P: 25,243

a=b(mod m) means m(ab). a=b(mod n) means n(ab). If nm what can you conclude from this?



#3
Sep1508, 11:03 PM

P: 58

I guess you could conclude that (m(ab)) / (n(ab)). Or I guess that's like mn? Actually I'm not really sure. I'm not sure if that's correct. If it is, I'm not really sure if that proves the statement. If mn is true, does that mean they're the same integer? In which case I assume that would prove it.



#4
Sep1508, 11:11 PM

Sci Advisor
HW Helper
Thanks
P: 25,243

Discrete Math  a modulus proof
m(ab) and n(ab) are true/false statements. You can't DIVIDE them. Think about this. If ab and bc then ac, right?



#5
Sep1508, 11:54 PM

P: 58

If nm and m(ab), then n(ab) is like saying If ab and bc then ac. I think that there is some constant k so that kn=m? Then in this case, because they're modular, they come up with the same answer. Is that any more correct? 


#6
Sep1608, 12:02 AM

Sci Advisor
HW Helper
Thanks
P: 25,243

Yes. I just really didn't like (m(ab)) / (n(ab)). Didn't make much sense to me. Maybe it did to you.



#7
Sep1608, 11:09 AM

P: 58

I see, but this is where my weak point is. I'm not sure how I write a proof for that.



#8
Sep1608, 01:29 PM

Sci Advisor
HW Helper
Thanks
P: 25,243

"If nm and m(ab), then n(ab) is like saying If ab and bc then ac." That's the basis of the proof. Can you just flesh that out into a full proof? Start with "if nm and a≡b(mod m)" and conclude with "then a≡b(mod n)".



#9
Sep1608, 03:14 PM

Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,353

If a= b mod m, then m divides a b so ab= km for some integer k. If n divides m then m= pn for some integer p. Put those together to get that ab= ?n.



#10
Sep1608, 03:21 PM

P: 58

alright, thanks you two. Hopefully that'll help. I'll let you know if I have any further questions. Thanks! :)



Register to reply 
Related Discussions  
Discrete math.. venn diagram proof  Set Theory, Logic, Probability, Statistics  4  
DISCRETE MATH: Binomial Theorem proof (using Corollary 2)  Calculus & Beyond Homework  6  
Discrete math induction proof  Precalculus Mathematics Homework  9  
Proof in Discrete math  Calculus & Beyond Homework  3  
Discrete math and proof  Calculus & Beyond Homework  2 