Thread: congruence and gcd

Can anyone please help me with this proof?

“ if ab≡0(mod n), then shows that gcd⁡(a,n)∙gcd⁡(b,n)=n. “

Any suggestions will be very appreciate.

denise,

This is a standard problem in elementary number theory. I'll provide you with my general approach but I'll leave some details up to you.

First given the nature of what we want to prove, we infer that n is a postive integer. Let d = gcd(a,n) and e = gcd(b,n). We show that de|n and n|de (Recall a|b denotes a divides b). Now clearly since d|a and e|b, it follows that de|ab. Now as gcd(ab,n) = n (why? because ab = 0 (mod n)), we have de|n.

To show that n|de, we use another property of gcd. Recall by Bezout's theorem that there exist integers x and y such that gcd(a,b) = ax + by. So apply this to d and e and you will see that since ab = 0 (mod n), it follows that n|de.

I hope this is of some help to you. Feel free to give me reps (whatever that is) Good Luck!

Best,

m_s_d

Originally Posted by math_science_dude

denise,

This is a standard problem in elementary number theory. I'll provide you with my general approach but I'll leave some details up to you.

First given the nature of what we want to prove, we infer that n is a postive integer. Let d = gcd(a,n) and e = gcd(b,n). We show that de|n and n|de (Recall a|b denotes a divides b). Now clearly since d|a and e|b, it follows that de|ab. Now as gcd(ab,n) = n (why? because ab = 0 (mod n)), we have de|n.

To show that n|de, we use another property of gcd. Recall by Bezout's theorem that there exist integers x and y such that gcd(a,b) = ax + by. So apply this to d and e and you will see that since ab = 0 (mod n), it follows that n|de.

I hope this is of some help to you. Feel free to give me reps (whatever that is) Good Luck!

Best,

m_s_d

Thank you for your suggestions.
Actually, I completed the second part of the proof.
It's the first part that gave me . I will try out the proof again.
Thanks again.