Register to reply

Discrete Math - a modulus proof

by CaptainSFS
Tags: discrete, math, modulus, proof
Share this thread:
CaptainSFS
#1
Sep15-08, 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 n|m 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 (a-b)/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 n|m. So tired dividing the m=(a-b)/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!
Phys.Org News Partner Science news on Phys.org
FIXD tells car drivers via smartphone what is wrong
Team pioneers strategy for creating new materials
Team defines new biodiversity metric
Dick
#2
Sep15-08, 10:28 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
a=b(mod m) means m|(a-b). a=b(mod n) means n|(a-b). If n|m what can you conclude from this?
CaptainSFS
#3
Sep15-08, 11:03 PM
P: 58
I guess you could conclude that (m|(a-b)) / (n|(a-b)). Or I guess that's like m|n? 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 m|n is true, does that mean they're the same integer? In which case I assume that would prove it.

Dick
#4
Sep15-08, 11:11 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
Discrete Math - a modulus proof

m|(a-b) and n|(a-b) are true/false statements. You can't DIVIDE them. Think about this. If a|b and b|c then a|c, right?
CaptainSFS
#5
Sep15-08, 11:54 PM
P: 58
Quote Quote by Dick View Post
m|(a-b) and n|(a-b) are true/false statements. You can't DIVIDE them. Think about this. If a|b and b|c then a|c, right?
Right, i mean that makes sense, but that's just reiterating the claim isn't it?

If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c.

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?
Dick
#6
Sep16-08, 12:02 AM
Sci Advisor
HW Helper
Thanks
P: 25,228
Yes. I just really didn't like (m|(a-b)) / (n|(a-b)). Didn't make much sense to me. Maybe it did to you.
CaptainSFS
#7
Sep16-08, 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.
Dick
#8
Sep16-08, 01:29 PM
Sci Advisor
HW Helper
Thanks
P: 25,228
"If n|m and m|(a-b), then n|(a-b) is like saying If a|b and b|c then a|c." That's the basis of the proof. Can you just flesh that out into a full proof? Start with "if n|m and a≡b(mod m)" and conclude with "then a≡b(mod n)".
HallsofIvy
#9
Sep16-08, 03:14 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 39,552
If a= b mod m, then m divides a- b so a-b= km for some integer k. If n divides m then m= pn for some integer p. Put those together to get that a-b= ?n.
CaptainSFS
#10
Sep16-08, 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