5
$\begingroup$

Show that if $a$, $b$ are positive integers, then we have: $\gcd(a,b) = \gcd(a + b, \mathrm{lcm}[a,b])$.

5 Answers 5

6

Below are a few proofs. First, here's a couple from my sci.math post on 2001/11/10 enter image description here
For variety here is yet another using $\rm\ (a,b)\ [a,b]\ =\ \color{#c00}{ab}\ \ $ and basic gcd laws:

$\rm\quad (a,b)\ (a\!+\!b,\, [a,b])\, =\, (aa\!+\!ab,\, ab\!+\!bb,\, \color{#c00}{ab})\ =\ (aa,\,bb,\,ab)\, =\, (a,b)^2$

By the way, recall that the key identity in the second proof arose the other day in our discussion of Stieltjes $\rm\ 4\:n+3\ $ generalization of Euclid's proof of infinitely many primes. Here's a slicker proof:

Lemma $\rm\ \ (a\!+\!b,\,ab) = 1 \iff (a,b) = 1$

Proof $\rm\ \ \ (a,b)^2 \subset (a\!+\!b,\,ab) \subset (a,b)\ \ $ since, $ $ e.g. $\rm\ \ a^2 = a(a\!+\!b)-ab\in (a\!+\!b,\,ab)$

So $\rm\ 1\in (a\!+\!b,\, ab)\ \Rightarrow\ 1\in (a,b).\:$ Conversely $\rm\ 1 \in (a,b)\ \Rightarrow\ 1 \in (a,b)^2 \subset (a\!+\!b,\,ab)$

4

Another Dubuquesque attempt; for legibility, write $d=\gcd(a,b)$: \begin{align*} \gcd\Bigl(d(a+b), ab\Bigr) &= \gcd\Bigl(d(a+b), ab, ab\Bigr)\\ &=\gcd\Bigl(d(a+b),\ ab-a(a+b),\ ab-b(a+b)\Bigr)\\ &=\gcd\Bigl(d(a+b),\ a^2,\ b^2\Bigr)\\ &=\gcd\Bigl(d(a+b),\ \gcd(a^2,b^2)\Bigr)\\ &=\gcd\Bigl(d(a+b),\ \gcd(a,b)^2\Bigr)\\ &=\gcd\Bigl(d(a+b),\ d^2\Bigr)\\ &= d\gcd\Bigl(a+b,d\Bigr)\\ &= d\gcd\Bigl(a+b,\gcd(a,b)\Bigr)\\ &= d\gcd(a,b)\\ &= \gcd(a,b)\gcd(a,b). \end{align*}

(Second line uses the fact that $a(a+b)$ and $b(a+b)$ are both multiples of $d(a+b)$).

Now divide through by $\gcd(a,b)$ to get the desired result.

  • 0
    @Bill: If I'm not mistaken, it's the one you labeled "for variety"; at least, that's the identity I was trying to establish when this computation worked.2011-02-12
0

Start by writing a=d a', b=d b', where $d=(a,b)$.

  • 0
    @Kira: You go from $\gcd(a+b,bn)|bn$ and $\gcd(a+b,bn)|a+b$ to $\gcd(a+b,bn)|(a+b)-b$. This does not follow from the linear combination property: you know $\gcd(a+b,bn)$ divides any linear combination of $a+b$ and $bn$, but this is a linear combination of $a+b$ and $b$, not $bn$. So you need to justify that assertion somehow, you haven't done so.2011-02-11
0

Perhaps overkill, but if you accept the 'distribution law' $(x,[y,z])=[(x,y),(x,z)]$ stated at Wikipedia, then it is easy:

$(a+b,[a,b])=[(a+b,a),(a+b,b)]=[(b,a),(a,b)]=(a,b)$

where in the second equality I used the easy fact $(x,y)=(x,y \mod x)$.

-1

$\newcommand{\lcm}{\:\text{lcm}}$Here is an 'divisor-level' proof which basically mirrors Gone's first proof. We can use the following definitions: $\;\gcd(a,b)\;$ and $\;\lcm(a,b)\;$ are the non-negative numbers such that, for all $\;d\;$, $\begin{array} \\ d|\gcd(a,b) & \equiv & d|a \land d|b \\ d|\lcm(a,b) & \equiv & d|a \lor d|b \\ \end{array}$ together with 'divisor extentionality', i.e., $\;s = t \;\equiv\; \langle \forall d :: d|s \equiv d|t \rangle\;$ for non-negative numbers $\;s,t\;$.

We start with the most complex side of this equation, expand the above definitions, and try to simplify: for all $\;d\;$, $\begin{align} & d|\gcd(a+b, \lcm(a,b)) \\ = & \;\;\;\;\;\text{"expand the definitions of $\;\gcd\;$ and $\;\lcm\;$"} \\ & d|(a+b) \;\land\; (d|a \lor d|b)) \\ = & \;\;\;\;\;\text{"distribute $\;\land\;$ over $\;\lor\;$"} \\ & (d|(a+b) \land d|a) \;\lor\; (d|(a+b) \land d|b) \\ = & \;\;\;\;\;\text{"on left hand side, use $\;d|a\;$ to simplify $\;d|(a+b)\;$; similar for right hand side"} \\ & (d|b \land d|a) \;\lor\; (d|a \land d|b) \\ = & \;\;\;\;\;\text{"logic: simplify; reintroduce definition of $\;\gcd\;$"} \\ & d|\gcd(a,b) \\ \end{align}$ which by divisor extensionality proves $\;\gcd(a+b, \lcm(a,b)) = \gcd(a,b)\;$.