Which part of proving the Fundamental Theorem of Arithmetic specifically requires Euclid's lemma (if p divides ab, then p divides a or p divides b)?
AProving that every integer greater than 1 has at least one prime factorization (existence)
BProving that the prime factorization is unique — that no integer has two genuinely different factorizations
CProving that 1 is not prime
DProving that there are infinitely many primes
Existence is proved by strong induction alone: if n is prime, done; if composite, it has a factor 1 < d < n, and by strong induction both d and n/d have prime factorizations. Uniqueness is the hard part: to show two factorizations must be identical, you need Euclid's lemma — if a prime p appears in one factorization, it divides the product on the other side, and the lemma forces p to equal one of those primes. Without Euclid's lemma, you cannot rule out genuinely different factorizations.
Question 2 Multiple Choice
In the ring Z[√−5], the number 6 factors as both 2 × 3 and (1+√−5)(1−√−5), where all four factors are irreducible. What does this tell us about the Fundamental Theorem of Arithmetic?
AThe theorem is false — 6 itself is a counterexample to unique factorization in the ordinary integers
BThe theorem relies on specific properties of the ordinary integers that do not hold in all number systems
CThe theorem is trivially true because factorizations involving complex numbers don't count
DThis shows that primes and irreducible elements are always the same thing in any ring
This example shows that unique factorization is not a universal truth about all number systems — it depends on the specific structure of the integers, particularly the property that enables Euclid's lemma (which follows from the Euclidean algorithm). In Z[√−5], Euclid's lemma fails, and so does unique factorization. This is why FTA requires a real proof rather than just an appeal to intuition — the intuition that 'of course factorization is unique' is wrong in closely related systems.
Question 3 True / False
The uniqueness of prime factorization in the integers follows from Euclid's lemma: if a prime p divides ab, then p divides a or p divides b.
TTrue
FFalse
Answer: True
Euclid's lemma is the key to the uniqueness proof. Suppose two prime factorizations of n exist. Take any prime p from the first — it divides n, and therefore divides the product in the second factorization. By repeated application of Euclid's lemma, p must divide one of the primes in the second factorization — and since those are prime, p must equal that prime. Continuing this argument shows the two factorizations must contain the same primes with the same multiplicities.
Question 4 True / False
The Fundamental Theorem of Arithmetic is intuitively obvious and doesn't require a non-trivial proof, since it's clear that any number factors into primes in mainly one way.
TTrue
FFalse
Answer: False
Unique factorization is not intuitively obvious — it is false in other algebraic systems that closely resemble the integers. The ring Z[√−5] provides a concrete counterexample where factorization is not unique. The proof requires Euclid's lemma, which in turn requires Bézout's identity from the Euclidean algorithm. These are non-trivial results that depend on specific properties of the integers. Treating FTA as obvious is the most common misconception about the theorem.
Question 5 Short Answer
Why is Euclid's lemma the critical tool for proving uniqueness in the Fundamental Theorem of Arithmetic, and what would go wrong in the proof without it?
Think about your answer, then reveal below.
Model answer: Euclid's lemma states: if a prime p divides a product ab, then p divides a or p divides b. Without it, we cannot connect a prime in one factorization to any prime in a second factorization. The uniqueness proof works by assuming two factorizations exist and showing they must be the same: pick a prime from the first, note it divides the product on the second side, and use Euclid's lemma to force it to equal one of the primes there. Without this lemma, a prime from one factorization might divide the product without dividing any individual factor — and we'd have no way to rule out different factorizations.
The example of Z[√−5] is instructive: in that ring, Euclid's lemma fails, and indeed 6 has two distinct factorizations. The theorem's truth in the ordinary integers is a consequence of the Euclidean algorithm giving us the Bézout identity, which implies Euclid's lemma. The chain of dependence: Euclidean algorithm → Bézout identity → Euclid's lemma → FTA uniqueness.