Question

Show that if a, b and m are integers such that$m\ge 2$ and $a\equiv b\left(\mathrm{mod}m\right)$, then $\gcd \left(a,m\right)=\gcd \left(b,m\right)$

Short answer

$\gcd \left(a,m\right)=\gcd \left(b,m\right)$

Step-by-step solution

Step: 1

Since m divides a-b then we have and then there exist an integer c such that

Let us consider that$a-b=mc\Rightarrow a=mc+b$

$$\begin{gathered} A=\gcd (a,m) \\ B=\gcd (b,m) \end{gathered}$$where A and B are constants.

Step: 2

We have $a=mc+b,\frac{A}{a},\frac{A}{m}\to \frac{A}{b}$

Step: 3

The integer divides greatest common divisor if and only if the integer divides the two integers of the greatest common divisor.

$$\begin{gathered} \frac{\gcd (b,m)}{\gcd (a,m)}and \\ \frac{B}{\gcd (a,m)} \end{gathered}$$

We have

role="math" localid="1668524869064" $$\begin{gathered} A=\gcd (a,m) \\ B=\gcd (b,m) \\ \frac{A}{B}and\frac{B}{A}\Rightarrow A=B \end{gathered}$$

Hence$\gcd (a,m)=\gcd (b,m)$