Show that if $n$ is any integer, then $\gcd(a+nb,b)=\gcd(a,b)$

Show that if $n$ is any integer, then $\gcd(a+nb,b)=\gcd(a,b)$.

I started out by letting $d=\gcd(a,b)$ and $p=\gcd(a+nb,b)$. I want to show that $p=d$.

So for integers $q_{i} \in \mathbb{Z}$, $i=1,2,3,4$,

$a=dq_{1}$

$b=dq_{2}$

$a+nb=pq_{3}$

$b=pq_{4}$.

Then $nb = pq_{3}-a = pq_{3}-dq_{1}$. So $b=\frac{pq_{3}-dq_{1}}{n}$. What if $n=0$?

Since the question says to show that if $n$ is any integer, does the conclusion I reached imply that the statement is false or did I do something wrong?

It is obvious that $\gcd(a+nb,b)=\gcd(a,b)$ if $n=0$ but then why do my equations above contradict that?

• You could just do the case that $n=0$ separately. It is obvious that $gcd(a+0b, b) = gcd(a,b)$. – Tom Tseng Oct 4 '15 at 1:20
• but even if $n=0$, $a+nb=pq_{3}$ shows that $b=\frac{pq_{3}-a}{n}$ which says that there is no such $b$ so that this works. – Jack Oct 4 '15 at 1:27
• @Tim when $n=0$, then $nb=a-pq_3$ where both sides are $0$, so you can't divide by $n=0$ to say anything about $b$. – yurnero Oct 4 '15 at 1:29

Let's use your notation that involves $d$ and $p$. We have:
• $d|b$ trivially. Moreover, $d|b$ implies $d|nb$. Together with $d|a$, this gives us $d|a+nb$. So $d$ is a common divisor of $b$ and $a$. We infer that $d\leq p$ (in fact $d|p$ but we don't need this.)
• A similar argument shows $p\leq d$.
So we have both $d\leq p$ and $p\leq d$. This means $d=p$.
It is enough to show that common factors of $a+nb,b$ are same as common factors of $a,b$. suppose $d\vert a$ & $d\vert b$ so $d\vert nb \Rightarrow d\vert a+nb$
Likewise, if $d$ is a common factor of $a + nb$ and $b$ then $d\vert (a+nb)-nb=a$ thus $d$ is a common factor of $a$ and $b$ .
Note that If $e\vert x$ & $e\vert y$ then $e\vert mx\pm ny$