- #1

Math100

- 756

- 206

- Homework Statement
- If ## a\equiv b \mod n ##, prove that ## gcd(a, n)=gcd(b, n) ##.

- Relevant Equations
- None.

Proof:

Suppose ## a\equiv b \mod n ##.

Then ## n\mid (a-b)\implies kn=a-b ## for some ## k\in\mathbb{Z} ##.

Let ## gcd(a, n)=d ## and ## gcd(b, n)=h ##.

Note that ## d\mid a \land d\mid n\implies d\mid (a-kn)\implies d\mid b ## and ## h\mid b \land h\mid n\implies h\mid (b+kn)\implies h\mid a ##.

Thus ## d\mid n \land d\mid b\implies d\mid gcd(b, n)\implies d\mid h ## and ## h\mid n \land h\mid a\implies h\mid gcd(a, n)\implies h\mid d ##.

Therefore, if ## a\equiv b \mod n ##, then ## gcd(a, n)=gcd(b, n) ##.

Suppose ## a\equiv b \mod n ##.

Then ## n\mid (a-b)\implies kn=a-b ## for some ## k\in\mathbb{Z} ##.

Let ## gcd(a, n)=d ## and ## gcd(b, n)=h ##.

Note that ## d\mid a \land d\mid n\implies d\mid (a-kn)\implies d\mid b ## and ## h\mid b \land h\mid n\implies h\mid (b+kn)\implies h\mid a ##.

Thus ## d\mid n \land d\mid b\implies d\mid gcd(b, n)\implies d\mid h ## and ## h\mid n \land h\mid a\implies h\mid gcd(a, n)\implies h\mid d ##.

Therefore, if ## a\equiv b \mod n ##, then ## gcd(a, n)=gcd(b, n) ##.