0
$\begingroup$

I need to prove that for every three integers $(a,b,c)$, the $\gcd(a-b,b-c) = \gcd(a-b,a-c)$. Assuming that a $a \ne b$.

Having:

$d_1 = \gcd(a-b,b-c)$

$d_2 = \gcd(a-b,a-c)$

How do i prove $d_1 = d_2$?

$\endgroup$
  • $\begingroup$ @ZacharySelk how do i proceed with the proof? $\endgroup$ – David Lilue May 22 '16 at 2:29
  • $\begingroup$ Do you know how to prove $\gcd(m,n) = \gcd(m,n+m)$? $\endgroup$ – Erick Wong May 22 '16 at 3:15
1
$\begingroup$

$$\gcd(a-b,b-c) = \gcd(a-b,a-c) \text{ ?}$$

Suppose $d$ is a common divisor of $a-b$ and $b-c$, i.e. it is a divisor of both of them.

Then for some integers $j$ and $k$, we have $dj=a-b$ and $dk=b-c$.

Hence $d(j+k)=(a-b)+(b-c) = a-c$. So $d$ is a divisor of $a-c$.

Thus every common divisor of $a-b$ and $b-c$ is a common divisor of $a-b$ and $a-c$.

In a similar way, one can show that every common divisor of $a-b$ and $a-c$ is a common divisor of $a-b$ and $b-c$.

Thus the set of all common divisors of $a-b$ and $b-c$ is the same as the set of all common divisors of $a-b$ and $a-c$.

The largest member of that set is the $\gcd$, so the $\gcd$ is the same in both cases.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

$d_2 = \gcd(a-b, a-c) = \gcd(a-b, (a-c)-(a-b)) = \gcd(a-b, b-c) = d_1$. Here, you only need to use the fact that $\gcd(x,y) = \gcd(x,x+y) = \gcd(x,x-y).$

| cite | improve this answer | |
$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.