# Math Help - congruence and gcd

1. ## congruence and gcd

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

Any suggestions will be very appreciate.

2. 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

3. 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