Modular Congruence and GCD Proof

[Colleen G]

Homework Statement

If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).[/B]

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

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!

 

[Dick]

Homework Statement

If a≡b(mod n) and d=gcd(a.n), prove that d=gcd(b,n).[/B]

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

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!

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.