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





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?

  • 1
    $\begingroup$ You could just do the case that $n=0$ separately. It is obvious that $gcd(a+0b, b) = gcd(a,b)$. $\endgroup$ – Tom Tseng Oct 4 '15 at 1:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Jack Oct 4 '15 at 1:27
  • $\begingroup$ @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$. $\endgroup$ – 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$


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.