2
$\begingroup$

Every proof of this fact that I've seen relies on guessing a "formula" for the GCD first, such as "the smallest positive integer of the form $ax+by$" or $\frac{ab}{\text{lcm}(a,b)}$. Then one shows that the guess was indeed correct and proves the result. I don't find these proofs very intuitive and I would like to know if there's a simpler proof that doesn't involve guessing what the GCD looks like (this includes the fundamental theorem of arithmetic, which seems like overkill).

The proof should go like this:

The statement is trivially true for $1$ and $(a,b)$ itself. Let $(a,b)=d$. Suppose $\exists c$ such that $1<c<d$, $c \mid a$ and $c \mid b$ but $c \not \mid d$. Since $c<d$, we have $1 \le (c,d) < c$. Suppose $(c,d)=1$. Then $a=dk$ and $c \mid a$ imply $c \mid k$, hence $cd \mid a$. In the same way $cd \mid b$, a contradiction.

Now suppose $1<(c,d)<c$. Then $\frac{c}{(c,d)} > 1$. I would like to show that $\frac{cd}{(c,d)} \mid a$, but here I get stuck. Can it be done with my restrictions? If not, why?

EDIT:

So my original proof only used multiplicative properties of $\Bbb Z$, but I have learned that the very existence of the GCD requires additive properties as well. However, I've found a new proof that doesn't seem to use any additive properties (not even duality with LCM). I believe it is closer to what I was looking for. The reasoning behind this proof relies on additive properties of $\Bbb Z$, but they seem to disappear in my formal proof. What's going on here? How is this proof equivalent to other proofs?

Proof. Let $c$ be a common divisor of $a$ and $b$ ($a<b$) but $c \not \mid d$.

Since $c \not \mid d$, we can't have $a=d$, so $a=kd$ for some $k>1$. Also $a=tc$, for some $t>k$. We have $kd=tc \implies c=\frac kt d$. Observe that $k \not \mid t$, otherwise $d=\frac tk c \implies c \mid d$. Let $v=(k,t)$; then $1 \le v < k$. Of course $(\frac kv, \frac tv)=1$. Now, $$b=k'd=t'c=t' \frac kt d \implies k'=t' \frac kt= t' \frac{k/v}{t/v} \implies t/v \mid t'$$ But then $b= t' \frac kt d = t' \frac {k/v}{t/v} d=\frac {t'}{t/v} \left(\frac kv d \right)$. Also $a=kd=v \left( \frac kv d \right)$. This shows that $\frac kv d > d$ is a common divisor and completes the proof. $\square$

Note that $c \mid \frac kv d$ as well.

This proof is a formalization of the following hand-waving:

suppose that $a=4d=6c$. Then the respective times $d$ and $c$ are contained in any common multiple of $d$ and $c$ must always have a ratio of $2:3$. This means that there must be a factor of $2d$ (and therefore $3c$) in any common multiple. If, for example, $b=5d$, then $b=6c+d$. But $c \mid b$ and $c \mid 6c$ imply $c \mid d$. This is impossible, because $3c=2d \implies 3=2 \frac dc$, a contradiction. This situation arises every time there are two common divisors and neither divides the other.

$\endgroup$
  • 2
    $\begingroup$ How do you define the gcd? $\endgroup$ – Paul K Jun 16 at 18:46
  • $\begingroup$ The greatest common divisor of $a$ and $b$, i.e. $(a,b)$ is a common divisor and if $c$ is another common divisor, then $c \le (a,b)$. $\endgroup$ – The Footprint Jun 16 at 18:49
  • $\begingroup$ See this duplicate. $\endgroup$ – Dietrich Burde Jun 16 at 19:01
  • $\begingroup$ @DietrichBurde doesn't Math Gems's answer assume that GCD=$ab$/LCM ? What if I don't know that? That's why I don't like proofs that guess the form of the GCD first $\endgroup$ – The Footprint Jun 16 at 19:04
  • $\begingroup$ This is a fact, where we don't have to guess the gcd. Also, you cannot avoid using $gcd(a, b)$, since you are using it (see the title, $(a, b)$) for the question. Perhaps I don't understand the question well. I find Bill's proof very good, and I would think it is even good know (and to use) gcd=ab/lcm. $\endgroup$ – Dietrich Burde Jun 16 at 19:06
2
$\begingroup$

This is not so much a direct answer to your question as an indication of how one of the standard approaches might naturally be motivated

Suppose $c|a$ and $c|b$ then $c|ha+kb$ for any integer choice of $h$ and $k$.

It is natural to constrain $c$ as much as possible, and we do this by taking the least positive value of $ha+kb$. Let's call this $f$, so we have $c|f$.

Now let's think about how this relates to $a$. We have $f\le a$ since $1a+0b=a$ and so we can divide $a$ by $f$ to get $a=mf+n$ with $0\le n\lt f\le a$. But $n=a-mf=(1-mh)a-mkb$ can't be a positive value, so must be zero. We therefore have $f|a$. Likewise $f|b$.

We now know that any common factor of $a$ and $b$ divides $f$, and also that $f$ is a common factor.


The tricky part of the proof, which you can do by uniqueness of prime factorisation as well, is to show that any common factor divides the highest common factor. Note that proving uniqueness of prime factorisation uses the additive properties of the integers and doesn't just depend on multiplicative properties.

So you will find that, at least implicit within your argument is an appeal to the additive properties of the integers.

This is quite a subtle point, and is the reason why the most efficient proofs are written the way they are. I agree they can seem a bit like magic, but they can also be motivated, as I have tried to illustrate.

$\endgroup$
  • 2
    $\begingroup$ @TheFootprint No, it doesn't beg. Rather, it deduces it from the dual: that the least common multiple $\ell $ divides every common multiple $\,m,\,$ whose proof is trivial (else $\,m\bmod \ell = m - q\ell$ would be a smaller common multiple). See here for more. $\endgroup$ – Bill Dubuque Jun 16 at 19:51
  • 1
    $\begingroup$ @TheFootprint Yes - $(4a+1)(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1$ and they have an identity in $1$ as well. $\endgroup$ – Mark Bennet Jun 16 at 20:04
  • 2
    $\begingroup$ @TheFootprint Unlike common divisors, the common multiples form an ideal, and that's the structure needed to enable the Euclidean descent at the heart of the matter (closed under subtraction $\Rightarrow$ closed under mod $\Rightarrow$ closed under gcd). Indeed the least element $\ne 0$ of the ideal is the gcd of all elements, so the lcm is the gcd of all common multiples. Dually, the gcd is the lcm of all common divisors. $\endgroup$ – Bill Dubuque Jun 16 at 20:11
  • 2
    $\begingroup$ @TheFootprint The proofs in $\Bbb Z$ all essentially use (Euclidean) Division with (smaller) Remainder (though some hide it by compiling into arithmetical assembly language). The same Euclidean proofs work in any domain enjoying such a division algorithm (Euclidean domains), e.g. univariate polynomials over a field. In domains lacking such division we define $(a,b)$ to be a gcd of $a,b$ if $\,c\mid a,b\iff c\mid (a,b)\,$ and $[a,b]$ is an lcm of $\,a,b\,$ if $\, a,b\mid m\iff [a,b]\mid m$ $\endgroup$ – Bill Dubuque Jun 16 at 20:20
  • 1
    $\begingroup$ @TheFootprint Duality yields ascent on common divisors: if $\,c,d\,$ are common divisors of $\,a,b\,$ then $\,{\rm lcm}(c,d) = cd/(c,d)\,$ is also a common divisor, and a greater one if $\,c,d\,$ are incomparable, i.e. $\,c\nmid d,\ d\nmid c.\,$ Is that equivalent to what you do in your edit? (I haven't had a chance to read it) $\endgroup$ – Bill Dubuque Jun 17 at 15:55
2
$\begingroup$

It is easier to first show:

If $M$ is a common multiple of $a$ and $b$, then it is divisible by $m=\operatorname{lcm}(a,b).$

Proof: Apply the division algorithm: $M=mq+r$ with $0\leq r<m.$ But since $m,M$ are common multiples of $a,b$ then so is $r=M-mq<m.$ If $r\neq 0,$ then there would be a smaller common multiple than $m,$ which contradicts our definition $m=\operatorname{lcm}(a,b).$ So we must have $r=0,$ and hence $m\mid M.$


Now, if $d$ is a common divisor of $a$ and $b$ and $D=\gcd(a,b),$ then by the above, we must have that $D'=\operatorname{lcm}(d,D)$ is a divisor of $a$ and a divisor of $b.$ So it is a common divisor. If $d$ is not a divisor of $D$, then $\operatorname{lcm}(d,D)>D=\gcd(a,b),$ but that's not possible by the definition of $\gcd.$

$\endgroup$
  • 1
    $\begingroup$ I.e. common divisors are closed under LCM and this yields the sought ascent. This and the underlying duality is discussed at length in my comments on Mark's answer (and the posts linked there). $\endgroup$ – Bill Dubuque Jun 17 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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