Gauss's theorem and Euclid's lemma

A divisibility cannot be "cancelled" like a fraction. Gauss's theorem says exactly when you are allowed to.

The statement

Gauss's theorem. If a divides b c and a is coprime with b, then a divides c.

The coprimality condition is essential. Without it the statement is false:

6 divides 4 × 3 = 12         but 6 divides neither 4 nor 3
                             (and 6 is coprime with neither 4 nor 3)

The proof, in three lines

It illustrates perfectly what Bézout is for.

a coprime with b   ->   there exist u, v with  a u + b v = 1

Multiply by c:          a c u + b c v = c

- a divides a c u         (obvious)
- a divides b c v         (since a divides bc by assumption)
- so a divides their sum, which is c.                        ∎

This is the typical mechanism: Bézout converts a divisibility assumption into an equality, which is then manipulated algebraically.

Euclid's lemma

The special case where a = p is prime:

If a prime p divides a product b c, then p divides b or p divides c.

Indeed, if p does not divide b, then p is coprime with b (the only divisors of p are 1 and p), and Gauss concludes.

This seemingly innocuous lemma is exactly what is missing to prove the uniqueness of prime factorisation. The fundamental theorem of arithmetic depends on it entirely.

Useful consequences

1. If a and b divide n, and a and b are coprime, then a b divides n.

   Example: n divisible by 3 AND by 5  ->  divisible by 15
            (but divisible by 4 AND by 6 does NOT imply divisible by 24)

2. If a is coprime with b and with c, then a is coprime with b c.

3. If a | c, b | c and a, b are coprime -> LCM(a,b) = a b

The first point is the criterion for divisibility by a product — and its counterexample shows how necessary the condition is: 12 is divisible by 4 and by 6, but not by 24, because 4 and 6 are not coprime.

An example of reasoning

Show that for any integer n, the product n(n+1)(n+2) is divisible by 6.

Among three consecutive integers:
   - at least one is even          ->  the product is divisible by 2
   - exactly one is a multiple of 3 -> the product is divisible by 3

2 and 3 are coprime  ->  the product is divisible by 2 × 3 = 6

Without Gauss's theorem, the last line would not be legitimate.

Summary

• Gauss: a | bc and a coprime with b ⟹ a | c.
• Without the coprimality assumption it is false (6 | 4×3 but 6 ∤ 4, 6 ∤ 3).
• The proof starts from Bézout: au + bv = 1, then multiply by c.
• Euclid's lemma: p prime and p | bc ⟹ p | b or p | c.
• That lemma is what grounds the uniqueness of prime factorisation.
• If coprime a and b both divide n, then ab divides n.