Prove that ## gcd(a, n)=gcd(b, n) ##.

[Math100]

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)$.

 

[fresh_42]

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)$.

I'm not sure whether this is the most elegant way to write it, but it is correct. Maybe a few too many $\Longrightarrow$.A common technique is to prove only $d\,|\,h$ and state that $h\,|\,d$ for symmetry reasons.

Also, there is an error in all of it. Any statement about divisors is always only true up to units. Units are invertible numbers, integers in this case. The only units in the ring of integers are $\pm 1.$ Hence we cannot conclude equality unless we add the requirement that the greatest common divisor has to be positive, which might be the case, I don't know. But from $d\,|\,h$ and $h\,|\,d$ alone, we only get $d=\pm h.$

 

[Math100]

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$ where $d$ is a positive integer.
Note that $d\mid a\land d\mid n\implies d\mid (a-kn)\implies d\mid b$.
Thus $d\mid n\land d\mid b\implies d\mid gcd(b, n)\implies d\mid h$.
Conversely, $h\mid d$ by symmetry.
Since $d\mid h$ and $h\mid d$,
it follows that $d=h\implies gcd(a, n)=gcd(b, n)$.
Therefore, if $a\equiv b \mod n$, then $gcd(a, n)=gcd(b, n)$.