Discrete Math - a modulus proof


by CaptainSFS
Tags: discrete, math, modulus, proof
CaptainSFS
CaptainSFS is offline
#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
SensaBubble: It's a bubble, but not as we know it (w/ video)
The hemihelix: Scientists discover a new shape using rubber bands (w/ video)
Microbes provide insights into evolution of human language
Dick
Dick is offline
#2
Sep15-08, 10:28 PM
Sci Advisor
HW Helper
Thanks
P: 25,175
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
CaptainSFS is offline
#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
Dick is offline
#4
Sep15-08, 11:11 PM
Sci Advisor
HW Helper
Thanks
P: 25,175

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
CaptainSFS is offline
#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
Dick is offline
#6
Sep16-08, 12:02 AM
Sci Advisor
HW Helper
Thanks
P: 25,175
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
CaptainSFS is offline
#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
Dick is offline
#8
Sep16-08, 01:29 PM
Sci Advisor
HW Helper
Thanks
P: 25,175
"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
HallsofIvy is offline
#9
Sep16-08, 03:14 PM
Math
Emeritus
Sci Advisor
Thanks
PF Gold
P: 38,898
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
CaptainSFS is offline
#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