Euclid's Lemma

Euclid's Lemma is the technical core of the proof of the Fundamental Theorem of Arithmetic: to show factorization into primes is unique, one shows that if $p$ divides a product of primes $q_1 q_2 \cdots q_k$, then (by the finite product form above) $p$ must equal one of the $q_i$, since each $q_i$ is prime and $p$'s only divisors of a prime $q_i$ other than $1$ are $q_i$ itself. This single fact, applied repeatedly, forces any two prime factorizations of the same integer to match term-for-term. In abstract algebra, the lemma motivates the distinction between a prime element of a general ring (one satisfying exactly the Euclid's Lemma property: $p \mid ab \implies p\mid a$ or $p\mid b$) and an irreducible element (one that cannot be factored nontrivially). In $\mathbb{Z}$ these two notions coincide, but in more exotic rings — such as $\mathbb{Z}[\sqrt{-5}]$, where $6 = 2\cdot 3 = (1+\sqrt{-5})(1-\sqrt{-5})$ gives two genuinely different factorizations into irreducibles — they do not, and unique factorization fails precisely because the analogue of Euclid's Lemma fails there. In elementary number theory and congruences, the coprime generalization is exactly the cancellation law for modular arithmetic: if $\gcd(m,a)=1$ and $ab \equiv 0 \pmod m$, one may "cancel" a suitably, recovering $b \equiv 0 \pmod m$ whenever $m\mid ab$; this underlies solving linear congruences and is a direct restatement of the coprime form proved above. In cryptography, particularly RSA and related schemes, the arithmetic of coprimality and the structure of $(\mathbb{Z}/n\mathbb{Z})^\times$ rest on exactly this machinery: knowing which elements are invertible modulo $n$, and how prime divisors of $n$ interact with products, traces back to Euclid's Lemma and Bézout's identity working in tandem. In computer science, algorithms for integer factorization, primality testing, and computing modular inverses (the extended Euclidean algorithm) are computational incarnations of the same Bézout coefficients used in the proof above. In combinatorics and analytic number theory, Euclid's Lemma underlies the definition and manipulation of the arithmetic functions (like the Möbius function and Euler's totient) that depend on unique prime factorization for their multiplicative properties.

:::faq[Where does this lemma first break down if we work in a different number system, like the Gaussian integers or $\mathbb{Z}[\sqrt{-5}]$?] In $\mathbb{Z}[i]$ (Gaussian integers), an analogue of Euclid's Lemma still holds because $\mathbb{Z}[i]$ has its own Euclidean algorithm and Bézout identity (it is a Euclidean domain), so unique factorization survives there too. In $\mathbb{Z}[\sqrt{-5}]$, however, there is no division algorithm compatible with the norm, Bézout's identity can fail for the relevant "irreducible" elements, and correspondingly Euclid's Lemma fails: $2$ is irreducible but not prime, since $2 \mid (1+\sqrt{-5})(1-\sqrt{-5}) = 6$ while $2$ divides neither factor. This is the precise mechanism behind the famous failure of unique factorization in that ring.

Ask the tutor: Can you show me, step by step, how Euclid's Lemma is actually used inside the proof of the Fundamental Theorem of Arithmetic's uniqueness part?

Think of divisibility by $p$ as a kind of sieve with holes only of "size $p$." If $ab$ falls entirely through the sieve — that is, $p \mid ab$ — common sense might suggest that $a$ and $b$ could each contribute a partial, fractional share of the divisibility, the way $6 = 2\cdot 3$ divides $12 = 4\cdot 3$ even though $6 \nmid 4$ and $6 \nmid 3$ individually is false here but is true for composite divisors. The content of Euclid's Lemma is that a prime sieve cannot be fooled this way: because $p$ has no nontrivial factors of its own, it cannot split its divisibility duty between $a$ and $b$. All of $p$'s "weight" must land in one factor or the other. The reason this rigidity holds traces back to linear algebra over $\mathbb{Z}$, encoded in Bézout's identity. If $p \nmid a$, then since $p$ is prime, $\gcd(p,a)=1$, so there exist integers $x,y$ with $px + ay = 1$. This equation says the numbers $p$ and $a$ generate all of $\mathbb{Z}$ under integer linear combinations — in particular they generate $1$ itself. Multiplying by $b$ turns the abstract fact "$1$ is reachable" into the concrete fact "$b$ is reachable using multiples of $p$ and multiples of $ab$," and since $p \mid ab$ by hypothesis, this forces $p \mid b$. The figure below shows the two-factor case pictorially: $p$'s divisibility "flows" into $a$ or into $b$, never fractionally split between both, which is exactly what distinguishes primes from composites.

It is worth stressing what the lemma does not say. It does not say $p \mid a$ and $p\mid b$ cannot both happen (they can — e.g. $p=3$, $a=6$, $b=9$). It says only that at least one must occur; the conclusion is an "or," not an "and," and it is not exclusive. It is also worth noting the direction of implication: the converse "$p\mid a$ or $p \mid b$ implies $p \mid ab$" is the easy direction (true for any integer, prime or not, by basic properties of divisibility), while the lemma asserts the hard direction, and this is exactly the direction that fails for composite $m$.

Example 1 (asymmetric numbers, prime form). Let $p = 13$, $a = 91$, $b = 154$. Compute $ab = 91 \times 154 = 14014$. Check divisibility: $14014 / 13 = 1078$, an integer, so indeed $13 \mid ab$. Now factor each piece: $91 = 7 \times 13$, so $13 \mid a$ directly — and indeed $91/13 = 7$. Meanwhile $154 = 2 \times 7 \times 11$, and $154/13 = 11.846\ldots$, not an integer, so $13 \nmid b$. This is consistent with the lemma: the conclusion is a disjunction, and here it is satisfied through the first disjunct ($13\mid a$) while the second fails — the lemma never promised both. To see the Bézout mechanism explicitly in a case where $p \nmid a$, instead take $p = 13$, $a = 154$, $b = 91$ (just swapping roles). Now $p \nmid a$ since $13 \nmid 154$. We need $\gcd(13,154)=1$: since $13$ is prime and does not divide $154$, indeed $\gcd(13,154)=1$. Find $x,y$ with $13x + 154y = 1$ via the Euclidean algorithm:

Back-substitute: $1 = 11 - 5\cdot 2 = 11 - 5(13 - 11) = 6\cdot 11 - 5\cdot 13 = 6(154 - 11\cdot 13) - 5\cdot 13 = 6\cdot 154 - 71\cdot 13$. So $x = -71$, $y = 6$: check $13(-71) + 154(6) = -923 + 924 = 1$. ✓. Multiply by $b = 91$: $13(-71\cdot 91) + (154\cdot 91)(6) = 91$. Since $154 \cdot 91 = 14014 = 13\times 1078$, this reads $13(-71\cdot 91) + 13(1078\cdot 6) = 91$, i.e. $91 = 13\big((-71)(91) + 1078\cdot 6\big)$. Compute the bracket: $(-71)(91) = -6461$, and $1078 \times 6 = 6468$, sum $= 7$. So $91 = 13 \times 7$ — correct, and this recovers $13 \mid b$ exactly as Step 1 of the proof predicts, entirely mechanically from the Bézout coefficients.

Example 2 (the finite product form with an unbalanced, non-uniform list). Let $p = 5$ and consider the product of four integers $a_1 = 8,\ a_2 = 21,\ a_3 = 40,\ a_4 = 33$. Compute

Step by step: $8\times 21 = 168$; $168 \times 40 = 6720$; $6720 \times 33 = 221760$. Check $221760 / 5 = 44352$, an integer, so $5 \mid a_1a_2a_3a_4$. The finite product form guarantees $5$ divides at least one $a_i$. Inspect each: $8/5$ not integer, $21/5$ not integer, $40/5 = 8$ integer — so $5 \mid a_3$. Indeed the induction in Step 3 of the proof, applied here, would first group as $(8\cdot21\cdot40)\cdot 33$; since $5 \nmid 33$ (as $33/5$ is not an integer), Step 2 forces $5 \mid (8\cdot 21\cdot 40) = 6720$, which is true ($6720/5=1344$). Recursing one level further, group $(8\cdot 21)\cdot 40$: since $5\mid 40$ outright, the induction terminates having correctly located the culprit factor $a_3 = 40$ without ever needing to fully expand which of $8$ or $21$ might be divisible by $5$ (neither is). This illustrates that the inductive proof does not require searching for the right factor by brute force — it peels the product from the right and lets Step 2 make a binary decision at each stage, though the final "witness" factor can occur anywhere in the list, as it does here in the third slot out of four.