Prove that $(a+nb,b)=(a,b)$

Question

Prove that $(a+nb,b)=(a,b)$ for any integer $n$.

Let $(a,b) = d$.

So $d = ax_1 + by_1$ where $x_1$ and $y_1 \in \mathbb{Z} $

Now consider, $(a+nb)x_1 + b(y_1 -nx_1)$ . Now clearly $(y_1 -nx_1)$ and $x_1$ are $\in \mathbb{Z}$

Also

$(a+nb)x_1 + b(y_1 -nx_1) = ax_1 + by_1 = d $

Is this correct ?

Answer 1

This proves one direction, but not the other. Remember that $d=(a,b)$ if and only if $d$ is the smallest positive integer expressible as $ax+by$. You've shown that if $d=(a,b)$ then there exist $x$ and $y$ such that $d=(a+nb)x+by$, but not that it's the smallest integer of this form.

You're nearly there, and there are several ways to complete the proof. One would be to assume $e=(a+bn,b)=x_2(a+bn)+y_2b$ and show that $e=xa+yb$ for some $x,y\in \mathbb Z$.

(What you did shows that $(a+nb,b)\leq(a,b)$, and doing it again in the other direction shows $(a+nb,b)\geq (a,b)$, so combining the two facts gives equality.)

Answer 2

If $d$ is a common divisor of $a$ and $b$ then it is also a divisor of $a+nb$.

If $d$ is a common divisor of $a+nb$ and $b$ then it is also a divisor of $a$ (because $a = (a+nb) -nb$).

Therefore the set of common divisors of $\{a,b\}$ is exactly the same as the set of common divisors of $\{a+nb,b\}$. So the maximum value in each set (i.e. the GCDs) are the same.