21
$\begingroup$

In the integers, it follows almost immediately from the division theorem and the fact that $a \mid x,y \implies a \mid ux + vy$ for any $u, v \in \mathbb{Z}$ that the least common multiple of $a$ and $b$ divides any other common multiple.

In contrast, proving $e\mid a,b \implies e\mid\gcd(a,b)$ seems to be more difficult. In Elementary Number Theory by Jones & Jones, they do not try to prove this fact until establishing Bezout's identity. This Wikipedia page has a proof without Bezout's identity, but it is convoluted to my eyes.

I tried my hand at it, and what I got seems no cleaner:

Proposition: If $e \mid a,b$, then $e \mid \gcd(a,b)$.

Proof: Let $d = \gcd(a,b)$. Then if $e \nmid d$, by the division theorem there's some $q$ and $c$ such that $d = qe + c$ with $0 < c < r$.

We have $a = k_1 d$ and $b = k_2 d$, so by substituting we obtain $a = k_1 (qe + c)$ and $b = k_2 (qe + c)$. Since $e$ divides both $a$ and $b$, it must divide both $k_1 c$ and $k_2 c$ as well. This implies that both $k_1 c$ and $k_2 c$ are common multiples of $c$ and $r$.

Now let $l = \operatorname{lcm}(r, c)$. $l$ divides both $k_1 c$ and $k_2 c$. Since $l = \phi c$ for some $\phi$, we have $\phi | k_1, k_2$, so $d \phi | a, b$.

But we must have $\phi > 1$ otherwise $l = c$, implying $r \mid c$, which could not be the case since $c < r$. So $d \phi$ is a common divisor greater than $d$, which is a contradiction. $\Box$

Question: Is there a cleaner proof I'm missing, or is this seemingly elementary proposition just not very easy to prove without using Bezout's identity?

$\endgroup$
3
  • 3
    $\begingroup$ What exactly is your definition of $\gcd(m,n)$? $\endgroup$ Jun 6, 2017 at 17:37
  • 1
    $\begingroup$ Where did you define $r$? $\endgroup$
    – user428487
    Aug 17, 2017 at 10:59
  • $\begingroup$ But don't we have to prove that the least multiple divides every common multiple? You need this to argue that $l$ divides both $k_1 c$ and $k_2 c$.. ?? $\endgroup$ Aug 31, 2019 at 21:31

5 Answers 5

15
$\begingroup$

One easy and insightful way is to use the proof below. It essentially constructs $\rm\,gcd\,$ from $\rm\,lcm\,$ by employing duality between minimal and maximal elements - see the Remark below. This is essentially how the linked Wikipedia proof works, but there the innate duality is obfuscated by the presentation. Below is a proof structured so that this fundamental duality is brought to the fore.

$\rm{\bf Theorem}\quad c\mid a,b\iff c\mid d,\ \ $ for $\rm\ \ d = ab/lcm(a,b).\ $ $\rm\color{#0a0}{Hence}$ $\rm\ d = gcd(a,b)$

$\rm{\bf Proof}\qquad\ \ \, c\mid a,b \iff a,b\mid ab/c \iff lcm(a,b)\mid ab/c \iff c\mid ab/lcm(a,b)$

$\rm\color{#0a0}{Generally}\,$ if $\rm\, c\mid a,b\iff c\mid d\ $ then $\rm\ d = \gcd(a,b)\ $ up to unit factors, i.e. they're associate (this is the definition of a gcd $\rm\,d\,$ of $\rm\,a,b\,$ in an integral domain).

Indeed setting $\rm\:c = d\:$ in direction $(\Leftarrow)$ shows that $\rm\:d\mid a,b,\:$ i.e. $\rm\:d\:$ is a common divisor of $\rm\:a,b.\:$ Conversely, by direction $(\Rightarrow)$ we deduce that $\rm\:d\:$ is divisible by every common divisor $\rm\:c\:$ of $\rm\:a,b,\:$ thus $\rm\:c\mid d\:\Rightarrow\: c\le d,\:$ so $\rm\:d\:$ is a greatest common divisor (both divisibility and magnitude-wise).

Remark $\ $ The proof shows that, in any domain, if $\rm\:lcm(a,b)\:$ exists then $\rm\:gcd(a,b)\:$ exists and $\rm\ gcd(a,b)\,lcm(a,b) = ab\ $ up to unit factors, i.e. they are associate. The innate duality in the proof is clarified by employing the involution $\rm\ x'\! = ab/x\ $ on the divisors of $\rm\:ab.\:$ Let's rewrite the proof using this involution (reflection), as in this answer (and here).

Notice that $\rm\ x\,\mid\, y\:\color{#c00}\iff\: y'\mid x'\,\ $ by $\smash[t]{\,\ \rm\dfrac{y}x = \dfrac{x'}{y'} \ }$ by $\rm\, \ yy' = ab = xx',\ $ so rewriting using this

$\begin{eqnarray}\rm the\ proof\ \ \ c\mid a,b &\iff&\rm b,\,a\mid ab/c &\iff&\rm lcm(b,\,a)\mid ab/c &\iff&\rm c\mid ab/lcm(b,a)\\[.5em] \rm becomes\ \ \ \ c\mid a,b &\color{#c00}\iff&\rm a',b'\mid c' &\iff&\rm lcm(a',b')\mid c' &\color{#c00}\iff&\rm c\mid lcm(a',b')'\end{eqnarray}$

Now the innate duality is clear: $\rm\ gcd(a,b)\,=\,lcm(a',b')'\ $ by the $\rm\color{#0a0}{above}$ gcd characterization.

$\endgroup$
4
  • $\begingroup$ Readers can find another involution-based proof in this answer. $\endgroup$ Feb 26, 2014 at 18:43
  • $\begingroup$ See also here and here. $\endgroup$ Apr 22, 2015 at 15:40
  • $\begingroup$ @BillDubuque A bit late to the party, but I was wondering, doesn't this answer beg the question? In the same line as Proof, second "iff": how do you know that the LCM divides any common multiple? $\endgroup$ Jun 16, 2019 at 19:47
  • 1
    $\begingroup$ @TheFootprint As I explained in your question, this fundamental lcm property has a simple descent proof using Division with (smaller) Remainder (a prototypical proof by Euclidean Descent, when formulated in mod [vs. subtraction] form). So, in effect, we use duality to reduce the gcd proof to this simple lcm proof. $\endgroup$ Jun 16, 2019 at 20:51
6
$\begingroup$

We can gain some insight by seeing what happens for other rings. A GCD domain is an integral domain $D$ such that $\gcd$s exist in the sense that for any $a, b \in D$ there exists an element $\gcd(a, b) \in D$ such that $e | a, e | b \Rightarrow e | \gcd(a, b)$. A Bézout domain is an integral domain satisfying Bézout's identity.

Unsurprisingly, Bézout domains are GCD domains, and the proof is the one you already know. It turns out that the converse is false, so there exist GCD domains which are not Bézout domains; Wikipedia gives a construction.

(But if you're allowing yourself the division algorithm, why the fuss? The path from the division algorithm to Bézout's identity is straightforward. In all of these proofs for $\mathbb{Z}$ the division algorithm is doing most of the work.)

$\endgroup$
2
  • $\begingroup$ $\rm\Bbb Q[x,y]\:$ is a UFD so GCD domain which is not Bezout, since $\rm\:gcd(x,y) = 1\:$ but $\rm\:f\, x+ g\, y = 1\:\Rightarrow\: 0 = 1\:$ by evaluating at $\rm\:x = 0 = y.$ Generally a gcd domain D is Bezout iff $\rm\:gcd(a,b) = 1\:\Rightarrow (a,b) = 1,\:$ i.e. $\rm\: ac + bd = 1\:$ for some $\rm\:c,d\in D.\ $ $\endgroup$
    – Math Gems
    Apr 16, 2013 at 3:53
  • $\begingroup$ Whoops. I seem to have misread the Wikipedia article. $\endgroup$ Apr 16, 2013 at 3:55
5
$\begingroup$

Proof using linear diophantine equations; Note: if $d=\gcd(a,b)$, then there exist integers $x$ and $y$ such that $$d=ax+by$$

Suppose $c\mid a$ and $c\mid b$ and $d=\gcd(a,b)$. Then, by definition of divisibility, $a=cl$ & $b=ck$, for some integers $l$ & $k$. By definition of gcd, $d=ax+by$ for some integers $x$ & $y$. By substitution, $$d=(cl)x + (ck)y =clx + cky =c(lx+ky) =cm$$ by closure, with $m=lx+ky$. Therefore $$d=cm$$ But by definition of divisibility, this implies $c\mid d$ and $m\mid d$ Therefore $c\mid d$.

QED :)

$\endgroup$
2
  • 7
    $\begingroup$ Isn't the statement that there exist $x,y$ with $d=ax+by$ more or less the exact Bezout identity that OP wanted to avoid? $\endgroup$ Feb 27, 2022 at 16:44
  • 1
    $\begingroup$ @Steven Yes, it is, so this is not an answer. $\endgroup$ Mar 31 at 12:17
2
$\begingroup$

You might also use the fact that each natural number can be uniquely represented as a product of prime powers to prove this fact without Bezout's Theorem.

This is called Fundamental Theorem of Arithmetic

For example d=p1^d1*..*pn^dn where p1 to pn are primes. The numbers p1 to pn are called then prime factors of d

Idea of the proof argument: Since gcd(a,b) divides a and b each prime factor of gcd(a,b) has to be a common prime factor of a and b.

For the same reason each prime factor of d has to be a common prime factor of a and b.

And since gcd(a,b) is the greatest common divisor of a,b (by definition), each prime factor of d has to be then a prime factor of gcd(a,b), for if there would be at least one prime factor p of d which isn't a prime factor of gcd(a,b), then the product gcd(a,b)*p would be again a common divisor of both a and b, greater than gcd(a,b), which would be a contradiction.

$\endgroup$
1
$\begingroup$

Just think of the Euclidean algorithm for computing the GCD of two numbers. Let $a, b$ with say $a<b$ be two integers. Then the GCD of $a$ and $b$ is also the GCD of $a$ and $b-a$, and now we can iterate. For intance:

  1. The GCD of $28$ and $8$ is the same as that of $20$ and $8$.
  2. Which is the same as that of $12$ and $8$.
  3. Which is the same as that of $4$ and $8$.
  4. Which is the same as that of $4$ and $4$.
  5. Which is obviously $4$.

Eventually, we must come down to calculating the GCD of a number with itself, since at each stage one of the numbers in our pair stays the same, and the other gets smaller. This has to stop eventually, but as long as the two numbers are distinct we can always subtract the smaller from the larger, so the only way it can stop is if they end up being equal, at which point that number will be the GCD of the original pair.

Now you just have to realize that this same logic applies to any divisor of the two numbers, not jut the greatest one. I could have said "any divisor of $28$ and $8$ is a divisor of $20$ and $8$..." and eventually had "...is a divisor of $4$". Since the number we arrive at at the end is the GCD, any divisor of the two original numbers divides the GCD.

$\endgroup$
2
  • $\begingroup$ i.e. $\ d\mid 28,8\iff d\mid 4,8\iff d\mid 4,0\iff d\mid 4\ $ using the more common remainder (mod) fast reduction steps vs, slower subtractive Euclidean algorithm. $\endgroup$ Mar 31 at 11:36
  • $\begingroup$ For $\,d=4\,$ the direction $(\Leftarrow)$ implies $4$ is common divisor of $28,8,\,$ and the direction $(\Rightarrow)$ implies every common divisor $\,d\,$ of $28,8$ must divide $\,4,\,$ so $\,4\,$ is the greatest common divisor. Said setwise, $\{28,8\}$ and $\{4\}$ have the same set $S$ of common divisors $\,d\,$ so they have the same greatest common divisor, which is the greatest divisor of $4$, i.e. $4.\ \ $ $\endgroup$ Mar 31 at 13:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .