0
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That's a good one, thank you $\endgroup$ – Derhham Jun 21 '18 at 1:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.