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 ?

for $n= 0$ ? :) – Darío A. Gutiérrez May 23 '18 at 07:33 — Darío A. Gutiérrez, May 23 '18 at 07:33
https://math.stackexchange.com/q/1051887/353218 – Darío A. Gutiérrez May 23 '18 at 11:13 — Darío A. Gutiérrez, May 23 '18 at 11:13

score 3 · Answer 1 · answered May 23 '18 at 09:07

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.

score 2 · Answer 2 · answered May 23 '18 at 07:07

2

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

answered May 23 '18 at 07:07

Especially Lime

40,828

What do you mean by smallest positive integer expresseible as ax+by ? – ReadThyOwnBook May 23 '18 at 07:12
1

@ReadThyOwnBook if you just know that $d=xa+yb$ it doesn't follow that $d=(a,b)$, e.g. $4=6-2$ but $(6,2)=2$. But every number $k$ which you can write as $ax+by$ for some integers $x$ and $y$ is a multiple of $(a,b)$. So if $k=ax+by$ is not the GCD then there is a smaller number $k'$ and two other integers $x',y'$ with $k'=ax'+by'$. – Especially Lime May 23 '18 at 07:31
How do i proceed then ? – ReadThyOwnBook May 23 '18 at 09:30
can you post detailed solution? – ReadThyOwnBook May 25 '18 at 10:47

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

2 Answers2