GCD proof – by contradiction?

This question already has an answer here:

  • Greatest common divisor of two relatively primes

    4 answers

Solutions Collecting From Web of "GCD proof – by contradiction?"

Let $c$ be any common divisor of $a+b$ and $a-b$. Then $c$ divides $(a+b)+(a-b)$ and $(a+b)-(a-b)$. So $c$ divides $2a$ and $2b$.

Note that there are integers $x$ and $y$ such that $ax+by=1$ and therefore $(2a)x+(2b)y=2$. It follows that $c$ divides $2$. Thus no number greater than $2$ can divide both $a+b$ and $a-b$.

For completeness, you should show that each of the possibilities $\gcd(a+b,a-b)=1$ and $\gcd(a+b,a-b)=2$ can happen.

Hint $\,\ {\rm mod}\ a\!-\!b\!:\,\ a\equiv b\,\Rightarrow\, \color{#0a0}{a\!+\!b\equiv 2b}\,$ so, by the Euclidean Algorithm $\rm\color{#c00}{(EA)}$

$\qquad (a\!-\!b,\,\color{#0a0}{a\!+\!b})\overset{\rm\color{#c00}{EA}} = (a\!-\!b,\,\color{#0a0}{2b}) = (a\!-\!b,\,2),\ $ by $\ (a\!-\!b,b)\overset{\rm\color{#c00}{EA}}= (a,b)=1,\,$ and Euclid’s Lemma.

Here $\rm\color{#c00}{EA}$ means $\ (m,n)\, =\, (m,n’)\ $ if $\ n’\!\equiv n\pmod m\,\ $ [= descent step of Euclidean Algorithm].

$\begin{eqnarray}{\bf Hint}\ \ \text{determinant of}\,\ \left[ \begin{array}{cr} 1 &\!\! -1\\ 1 & 1\end{array}\right] \left[ \begin{array}{cc} a & x\\ b & y\end{array}\right] &=& \left[ \begin{array}{cc} a\!-\!b &\! x\!-\!y\\ a\!+\!b &\! x\!+\!y\end{array}\right] \\
\Rightarrow\ \ \ 2\!\!\!\!\!\! \smash[b]{\underbrace{(ay – bx)}_{\quad\ \ \large =\,1\ {\rm by\ Bezout}}}\!\!\!\!\!\!\!\!\!\!\!\! &=& (a\!-\!b)(x\!+\!y)-(a\!+b\!)(x\!-\!y)\quad {\bf QED}\\ \\

Remark $\ $ The method generalizes to any linear map $\ (m,n)\mapsto (m,n)A = (am\!+\!bn,cm\!+\!dn)$

$\begin{eqnarray}\phantom{\bf Hint}\ \ \text{determinant of}\,\ \left[ \begin{array}{cr} a&\!\! b\\ c & d\end{array}\right] \left[ \begin{array}{cc} m & x\\ n & y\end{array}\right] &=& \left[ \begin{array}{cc} am\!+\!bn &\! ax\!+b\!y\\ cm\!+\!dn &\! cx\!+\!dy\end{array}\right] \\
\Rightarrow\ \ D\!\!\!\!\!\!\!\!\!\!\! \smash[b]{\underbrace{(my – nx)}_{\quad\ \ \large =\,(m,n)\ {\rm by\ Bezout}}}\!\!\!\!\!\!\!\!\!\!\!\!\!\!\! &=& (am\!+\!bn)(cx\!+d\!y)-(cm\!+\!dn)(ax\!+\!by)\\ \\

Therefore we deduce that $\ (am\!+\!bn,\,cm\!+\!dn)\mid D\ (m,n)\ $ since it divides the rhs so also the lhs. Alternatively, this can also be deduced using Cramer’s Rule, e.g. see this answer. Notice that the question is simply the special case when the determinant $\,D = 2,\,$ and the gcd $\,(m,n) = 1.\,$

$ax+by = 1$ means $2ax+2by = 2$.

Now use $2a=(a+b)+(a-b)$ and $2b=(a+b)-(a-b)$ and reorganize to get a solution to $(a+b)X + (a-b)Y = 2$.

So $\gcd(a+b,a-b)\mid 2$.