Number theory Proof on GCD

Question

If $b\mid c$, prove that $\gcd(a,b)=\gcd(a+c,b)$. Hint let $d=\gcd(a,b)$ and $e=\gcd(a+c,b)$ and show that $d\mid e$ and $e\mid d$.

I already showed that $e\mid d$ but I can't figure out how to show $d\mid e$. I've tried substituting in for $d$ and $e$ but nothing seems to work. I think I'm not understanding a key fact.

Answer 1

You can't assume $x = nl$ and $y = mnl + ml$. Instead your argument should proceed as follows:

If $d = ax + by$ and $e = ax' + by'$ then this shows that $d \le e$ because the gcd of $a$ and $b$ is the smallest positive integer of the form $a \cdot \text{something} + b \cdot\text{something}$. With your method, you won't need this, but if you work a bit harder, you can show that $d \mid e$:

For suppose we write $e = qd+r$ with $0 \le r < d$. Then $$r = e - qd = (ax' + by') - q(ax + by) = a(x'-qx)+b(y'-qy).$$ But $d$ is the smallest positive integer of this form and $0 \le r < d$, so $r$ must be $0$.

Likewise, you can write

$$d = ax + by = (a + c - c)x + by = (a + c)x + b(y - mx),$$

and since $e$ is the smallest postive integer of the form $(a + c) \cdot \text{something} + b \cdot\text{something}$, this shows that $e \le d$.

---

However, you don't have to use Bézout's theorem at all. The greatest common divisor $d$ of $a$ and $b$ is by definition:

1. A common divisor (i.e. $d \mid a$ and $d \mid b$)

2. The greatest divisor with this property (i.e. if $d' \mid a$ and $d' \mid b$ then $d' \le d$ [it is also true that $d' \mid d$])

Using the definition directly, you can show that if $e = \gcd(a + c, b)$ then $e \mid b$ (obvious) and $e \mid c$ (since $e \mid b \mid c$) therefore $e \mid a = (a + c) - c$ (since $e \mid a + c$ and $e \mid c$). Then, by (2.) it follows that $e \le d$.

Likewise, if you show that $d \mid b$ and $d \mid a + c$, (2.) says that $d \le e$.

Answer 2

I propose you the following way: let $\;d\;$ be any divisor of $\;a,\,b\;$ . Since $\;b\,\mid\,c\,$ , then also $\;d\,\mid\,c\;$ , so $\;d\;$ divides $\;a+c\;$ and $\;b\;$ .

OTOH, if $\;t\;$ is any divisor of $\;a+c,\,b\;$ then $\;t\,\mid\,b\,\mid\,c\;$ , so $\;t\;$ divides $\;c\;$ , and thus $\;t\;$ also divides $\;(a+c)-c=a\;$ , and thus finally $\;t\;$ divides $\;a,\,b\;$ .

Fill in details and end the proof, observing that the above is true also for the greatest such $\;d\;$ , on one hand, and OTOH also for the greatest such $\;t\;$