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.

  • 1
    $\begingroup$ Any guess why down-voted? I deserve reason, I hope. Without reason, what is the chance I detect my folly. Total confusion! $\endgroup$ – jiten Dec 4 '17 at 12:13
  • $\begingroup$ I will remove the OP if no answer / reason comes in some time. $\endgroup$ – 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$.

  • $\begingroup$ Good, but I feel the title of my question should be :better explanation of the given proof, by either geometric or linear algebra approach. $\endgroup$ – jiten Dec 4 '17 at 12:23
  • $\begingroup$ @jiten What's the problem? This proof is clear, and it's hard to imagine a simpler proof that's also robust. $\endgroup$ – PM 2Ring Dec 4 '17 at 12:29
  • $\begingroup$ Agreed, but my issue was different (as stated in my earlier comment); but verbalized wrongly. $\endgroup$ – jiten Dec 4 '17 at 12:32

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.