# Number theory Proof on GCD [closed]

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.

## closed as off-topic by Andrés E. Caicedo, Claude Leibovici, Juniven, Mohammad Riazi-Kermani, GNUSupporter 8964民主女神 地下教會Feb 5 '18 at 15:04

This question appears to be off-topic. The users who voted to close gave these specific reasons:

• "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Mohammad Riazi-Kermani, GNUSupporter 8964民主女神 地下教會
• "This question is not about mathematics, within the scope defined in the help center." – Andrés E. Caicedo, Claude Leibovici, Juniven
If this question can be reworded to fit the rules in the help center, please edit the question.

• If you can show that $e \mid d$, why can't you show that $d \mid e$? It is the same proof! – Trevor Gunn Feb 4 '18 at 19:42
• I tried but for some reason I can't do that one. I could upload my work and show you that I proved $e|d$.I will do it right now. I got to a point where I had $e=d$. – Rose Feb 4 '18 at 19:45
• Please do not use pictures for critical portions of your post. Pictures may not be legible, cannot be searched and are not view-able to some, such as those who use screen readers. – GNUSupporter 8964民主女神 地下教會 Feb 5 '18 at 15:04

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\;$

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