Greatest common divisor property: $\gcd(a, b)=\gcd(a+nb, b)$

Question

how to prove that $\gcd(a, b)=\gcd(a+nb, b)$ for any integer $n$? I tried to how that $\gcd(a, b) \leq \gcd(a+nb, b)$ and $\gcd(a, b) \geq \gcd(a+nb, b)$ but I ended up not being able to prove the later inequality. It would be highly appreciated to either prove it or provide an alternative.

Answer 1

Let $g_1 = (a,b)$ and $g_2 = (a+nb, b)$. Then,
$\begin{align} g_1\mid a \land g_1\mid b & \Rightarrow g_1\mid a{+}nb \\ & \Rightarrow g_1\mid (a+nb, b) = g_2 \end{align}$

On the other hand,
$\begin{align} g_2\mid b & \Rightarrow g_2\mid nb \\ g_2\mid nb \land g_2\mid a{+}nb & \Rightarrow g_2\mid a \\ &\Rightarrow g_2\mid (a,b) = g_1 \end{align}$

So, $g_1\mid g_2 \land g_2\mid g_1 \Rightarrow |g_1|=|g_2|$, and since gcd is defined positive, the result follows.

Answer 2

We see that couples $(a, b)$ and $(a + nb, b)$ have the same sets of common divisors. From here the equality of the maximum common divisors is clearly deduced. Now, due to the linearity property of the divisibility relation, we have the following implications.

$$d|a\quad \text{and}\quad d|b\Rightarrow d|(a+nb)$$ $$d|(a+nb)\quad \text{and}\quad d|b\Rightarrow d|(a+nb)-nb=a.$$

Answer 3

Take a deep breath.

If $k|a$ and $k|b$ then there are $a',b'$ so that $a= a'k; b=b'k$. So $a + bn= k(a' + nb')$. So $k$ being a common divisor of $a,b\implies k$ is a common divisor of $b, a+nb$.

If $m|b$ and $m|a + nb$ then there is are $b''$ and $d$ so that $b = b''m$ and $a+nb = dm$. So $a = (a+nb) - nb = dm - nb''m = m(d-nb'')$. So $m$ being a common divisor of $b, a+nb$ $\implies m$ is a common divisor of $a$ and $b$.

So $a,b$ and $b, a+nb$ have the exact same common divisors. SO they must have the exact same greatest common divisor.

(There is a catch. And it still catches me-- now and then. $\gcd(a, b) = \gcd(b, a+ nb) = \gcd(a, b + na)$ but $\gcd(a,b) \ne \gcd(a,a + nb)$ and $\gcd(a,b) \ne \gcd(b , b + na)$)