Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In the integers, it follows almost immediately from the division theorem and the fact that $a | x,y \implies a | 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|a,b \implies e|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 | a,b$, then $e | 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 = 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 | 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?

share|improve this question
add comment

3 Answers 3

up vote 3 down vote accepted

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 your linked Wikipedia proof works, but there the innate duality is obfuscated by the presentation. Below is a proof structured so that said 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).\ $ 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)$

Thus for $\rm\:c = d\:$ by direction $(\Leftarrow)$ we deduce $\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\: d\ge c,\:$ i.e. $\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.\ $ The innate duality in the proof is clarified by employing the involution $\rm\ x'\! = ab/x\ $ on the divisors of $\rm\:ab.\:$ Note $\rm\:x\mid y\color{#c00}\iff y'\mid x'.\:$ Rewriting the proof using this

$$\begin{eqnarray}\rm 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)\\ \rm i.e.\ \ \ \ 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}\qquad $$

Now the innate duality is clear: $\rm\,\ gcd(a,b)\,=\,lcm(a',b')'$

share|improve this answer
    
Readers can find another involution-based proof in this answer. –  Bill Dubuque Feb 26 at 18:43
add comment

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.)

share|improve this answer
    
$\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.\ $ –  Math Gems Apr 16 '13 at 3:53
    
Whoops. I seem to have misread the Wikipedia article. –  Qiaochu Yuan Apr 16 '13 at 3:55
add comment

It essentially depends on how you define the gcd. Note that gcd is the accronym of greatest common divisor.

This means that the first definition would be: $d=\gcd (a,b)$ is the greatest element (defined up to multiplication by a unit) of the set of all common divisors of $a$ and $b$. Where the partial order is given by divisibility. So if $e$ is a common divisor of $a$ and $b$, it is not greater than $d$, i.e. $e\mid d$.

Note: this definition makes sense for instance in unique factorization domains (in particular Euclidean domains or even principal domains), more generally.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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