Questions: Fundamental Theorem of Arithmetic (Rigorous Proof)

Question 1

The rigorous proof of the Fundamental Theorem of Arithmetic has two independent parts. Which part is genuinely harder and requires Euclid's lemma?

• A. Existence — showing every integer greater than 1 has at least one prime factorization requires Euclid's lemma to prevent circular reasoning
• B. Uniqueness — showing no integer has two different prime factorizations requires Euclid's lemma to transfer divisibility through a product
• C. Both parts require Euclid's lemma equally — it is the fundamental tool throughout the proof
• D. Neither part requires Euclid's lemma; strong induction alone suffices for both

Answer: (B)

Existence is proved by strong induction alone: if n is composite, write n = a × b; since a and b are smaller than n, they have factorizations by induction, and multiplying them gives a factorization of n. No Euclid's lemma needed. Uniqueness is the hard part: suppose p₁p₂⋯pₛ = q₁q₂⋯qₜ; we need to show p₁ equals some qⱼ. Since p₁ divides the product q₁⋯qₜ, Euclid's lemma tells us p₁ must divide some qⱼ — but since qⱼ is prime, p₁ = qⱼ. Without Euclid's lemma, we cannot make this step.

Question 2

In the number system Z[√-5] (integers of the form a + b√-5), the number 6 factors both as 2 × 3 and as (1+√-5)(1-√-5), with none of these factors dividing further. What does this demonstrate?

• A. The Fundamental Theorem of Arithmetic is false — 6 has two factorizations in ordinary integers too
• B. Euclid's lemma fails in Z[√-5], which shows that unique factorization is not automatic — it depends on specific properties of the number system
• C. This is impossible; the Fundamental Theorem applies to all number systems containing the integers
• D. Z[√-5] is not a valid number system, so this counterexample does not apply

Answer: (B)

This example shows that unique factorization is not a universal truth about all number-like systems — it is a specific property of the integers that requires proof. In Z[√-5], 2, 3, (1+√-5), and (1-√-5) are all irreducible (nothing divides them except units and themselves), yet 6 has two genuinely different factorizations. The reason unique factorization fails there is that Euclid's lemma fails: 2 divides (1+√-5)(1-√-5) = 6, but 2 divides neither factor. The integers have properties Z[√-5] lacks.

Question 3

Euclid's lemma — if a prime p divides a product ab, then p divides a or p divides b — is the key step in proving uniqueness of prime factorization.

• T. True
• F. False

Answer: True

Without Euclid's lemma, uniqueness cannot be proved. The argument works by induction: given two factorizations p₁⋯pₛ = q₁⋯qₜ, we know p₁ divides the right side, so by Euclid's lemma applied repeatedly, p₁ must divide some qⱼ. Since qⱼ is prime and p₁ is prime, p₁ = qⱼ. Cancel both and repeat. The entire uniqueness argument is a chain of applications of Euclid's lemma. As the Z[√-5] counterexample shows, without this lemma, uniqueness fails.

Question 4

The existence of a prime factorization for nearly every integer n > 1 is proved by assuming the factorization is unique and then using that uniqueness to show existence.

• T. True
• F. False

Answer: False

Existence and uniqueness are proved independently. Existence uses strong induction: if n is composite, it equals a × b with 1 < a, b < n; by strong induction both a and b have prime factorizations, whose product gives one for n. If n is prime, it is already a product of one prime. No assumption of uniqueness is used anywhere in this argument. The proof structure is: first establish existence (every integer has at least one factorization), then separately prove uniqueness (it has exactly one).

Question 5

Why does Euclid's lemma guarantee that two prime factorizations of the same integer must be identical, and why can't we prove this more directly?

Model answer: Suppose n = p₁p₂⋯pₛ = q₁q₂⋯qₜ. We know p₁ divides the entire product q₁⋯qₜ. By Euclid's lemma, p₁ must divide at least one factor qⱼ. Since qⱼ is prime — divisible only by 1 and itself — and p₁ is also prime, we must have p₁ = qⱼ. Cancel p₁ and qⱼ from both sides and repeat the argument for p₂, and so on. Every prime on the left is matched by an equal prime on the right, so s = t and the factorizations are identical up to order.

The 'more direct' approach fails because divisibility through a product requires Euclid's lemma — there's no shortcut. The lemma is needed to bridge from 'p₁ divides the product' to 'p₁ equals one of the factors.' Without this bridge (as in Z[√-5]), a prime can divide a product without dividing any factor, and uniqueness collapses. Euclid's lemma is not a trivial observation but a theorem that depends on the specific arithmetic of the integers.