Modular Congruence and GCD Proof

1. Feb 21, 2015

Colleen G

1. The problem statement, all variables and given/known data
If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).

2. Relevant equations
If a≡b(mod n) → n|(a-b) → a-b =nk, for some k∈ℤ → a=nk+b
If d=gcd(a.n) → d=ax+ny
gcd(b,n)=d ↔ d|b and d|n, and if c|b and c|n, then c ≤ a.

3. The attempt at a solution
Since a=nk+b and d=ax+ny, then
d=(nk+b)x+ny
d=nkx+bx+ny
d=bx+n(kx+y)
d=bx+nw, where w=kx+y and w∈ℤ.

I have gotten this far. Originally I thought this was enough to prove d was the gcd of b and n. But now I see that I need to show d|b, d|n, and that if there is a c such that c|b and c|n, then c ≤ d.

Help!

2. Feb 21, 2015

Dick

It's pretty clear that if d|n and d|a then d|b, right? Show that. Now if there is a smaller c that also divides b and n, then it also must divide a and n, right? Show that. Put the two together.

Last edited: Feb 21, 2015