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!