- #1
Colleen G
- 6
- 0
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!