Modular arithmetic Proofs

Question

For all $a$, $m \in\mathbb{Z}$, prove that

For all $x \in [a]$, where $[a]$ is the congruence class of $a \pmod m$, $\quad\gcd(x,m)=\gcd(a,m)$.

I have no idea where to start for this.

Answer 1

Hint:

With your notation

$$x\in [a]\iff x=a+mk\;,\;\;k\in\Bbb Z$$

If now we put

$$\;d=gcd(x,m)\iff \begin{cases}x=x'd\\{}\\m=m'd\end{cases}\implies a=x-mk=(x'-m'k)d\implies d\mid a$$

Your work now: show that $\;d\;$ is the greatest divisor of $\;a\;$ in the above (contradiction may help here...), and do also the other direction, namely:

$$d=gcd(a,m)\implies d=gcd(x,m)$$

Answer 2

Hints:

• Let $g = \gcd(x,m)$ and $h = \gcd(a,m)$. We want to show that $g = h$.
• To do this, it suffices to show that $g \mid h$ and $h \mid g$.
• Apply Bézout's identity to each gcd.
• Since $x \in [a]$, we know that $x = a + km$ for some $k \in \mathbb Z$.