# Better way to prove: $(a, b) = (a, b+ax), \forall x \in \mathbb {Z}$

I need a proof of the given problem in a better way than the approach stated below:

Denote $(a, b)$ by $d$ and $(a, b+ax)$ by $g$. It is clear that $d = ax_0 + by_0, \exists x_0, y_0 \in \mathbb{Z}$.

Can write it as: $d = a(x_0 - xy_0) + (b+ax)y_0$ //adding and subtracting $axy_0$

It follows that $\gcd$ of $a$ and $b + ax$ is also a divisor of d, i.e. $g \mid d$. This can be shown as: let $a = md, b = nd, \exists m,n \in \mathbb{Z}$; so $b+ax = (n + mx)d$, a linear combination again; also $x_0 - xy_0$ is an integer again. So, the l.h.s. ($d$) would be a multiple of $g$.

Now, proving the reverse (in fact the whole approach is the same as used for proving the invariant property of $\gcd$, i.e. it is the same at each step of the Euclidean algorithm) as follows:

$d \mid a, d \mid b => d \mid (a + bx)$, so $d \mid g$, as must divide the $\gcd$ of $a, (a+bx)$.

Hence, $d = \pm g$, and both being $\gcd$, $d = g$.

Although it is a common fact based on properties of linear combinations that any integer multiplied to any original term (whose $\gcd$ is being found out) does not change their $\gcd$. But, if a better proof is available that may use a different approach. The confusion that comes from adding and subtracting $axy_0$ needs either a geometric approach, or linear algebra.

• Any guess why down-voted? I deserve reason, I hope. Without reason, what is the chance I detect my folly. Total confusion! – jiten Dec 4 '17 at 12:13
• I will remove the OP if no answer / reason comes in some time. – jiten Dec 4 '17 at 12:19

Let $a,b, x \in \mathbb Z$, assume that $a$ and $b$ are not both $0$, and let $d_1 = (a,b)$ and $d_2 = (a, b + ax)$. Here $(a,b)$ denotes the greatest common divisor of $a$ and $b$. We want to show that $d_1 = d_2$. We'll do this by showing that $d_1 \mid d_2$ and also $d_2 \mid d_1$.
By definition $d_1 \mid a$ and $d_1 \mid b$. It follows that $d_1 \mid b + ax$. Thus, $d_1 \mid (a, b + ax)$. So we have shown that $d_1 \mid d_2$.
Also by definition, we know that $d_2 \mid a$ and $d_2 \mid b + ax$. It follows that $d_2 \mid b + ax - ax$, or in other words $d_2 \mid b$. Thus, $d_2 \mid (a,b)$. We have shown that $d_2 \mid d_1$.
Therefore, $d_1 = d_2$.