2.2 Euclid’s Lemma and the Fundamental Theorem of Arithmetic

Section 2.1 gave every pair of integers, not both zero, a greatest common divisor, and wrote it as a combination $ax + by$ (Theorem 2.1.1). This section spends that identity. Take $60$ . It splits as $2 \cdot 30$ , as $6 \cdot 10$ , as $4 \cdot 15$ , and every way of splitting it further, until no factor splits again, ends with the same primes $2, 2, 3, 5$ . Sets and Functions, Section 3.2 proved, for the school integers, that every integer at least $2$ has a prime factor, and set the uniqueness of the full splitting aside. Here we prove both, for the integers of Number Systems, Chapter 2. The key is a property of primes that the definition (“no positive divisors except $1$ and itself”) does not obviously give: a prime that divides a product divides one of the factors.

As in Number Systems, Section 2.5, numerals are the natural numbers of those names, and their sums and products may be computed in $\mathbb{N}$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.2.3 (a)).

2.2.1. Euclid’s lemma

The definition of a prime $p$ speaks about the divisors of $p$ . The property we want speaks about the numbers that $p$ divides. Something has to connect the two, and the connection is the Bézout identity of Section 2.1. We first prove a version for any divisor that shares no factor with one of the two numbers multiplied.

Theorem 2.2.1 (Euclid’s Lemma)

Let $a, b, c \in \mathbb{Z}$ . If $a \mid bc$ and $\gcd(a, b) = 1$ , then $a \mid c$ .

Idea. The hypothesis $\gcd(a, b) = 1$ is a statement about common divisors, which is hard to use directly. By Corollary 2.1.2 it is the same as an equation $1 = ax + by$ , and an equation can be multiplied. Multiplying it by $c$ writes $c$ as $acx + bcy$ . The first term is a multiple of $a$ on sight, and the second is one because $bc$ is.

Proof. Suppose $a \mid bc$ and $\gcd(a, b) = 1$ . By Corollary 2.1.2 there are $x, y \in \mathbb{Z}$ with $ax + by = 1$ . Since $a \mid bc$ , there is $k \in \mathbb{Z}$ with $bc = ka$ (Sets and Functions, Definition 1.1.2). Multiplying the identity by $c$ , with (F7), (F9), (F5) and (F6), $c = c(ax + by) = a(cx) + (bc)y = a(cx) + a(ky) = a(cx + ky) .$ Since $cx + ky \in \mathbb{Z}$ , this shows $a \mid c$ .

We call the method of this proof multiply the Bézout identity: from $1 = ax + by$ , multiply by $c$ and read off what divides $c$ . It turns a statement about divisors into an equation, which is where the work can be done.

Each hypothesis has a job. Without $\gcd(a, b) = 1$ the conclusion fails: $4 \mid 2 \cdot 6 = 12$ , but $4 \nmid 6$ , since $6 = 1 \cdot 4 + 2$ leaves a non-zero remainder (uniqueness in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2 (a)); here $\gcd(4, 2) = 2$ . The common factor $2$ of $4$ and $2$ let $4$ divide the product without dividing $6$ .

2.2.2. Lists, products and prime factorizations

To say that a factorization is unique, we must first say what a factorization is. The products $2 \cdot 2 \cdot 3 \cdot 5$ and $3 \cdot 2 \cdot 5 \cdot 2$ are equal and use the same primes, and we want to count them as one. We do so by writing the primes in order, smallest first. A factorization also has a length, and the length may be $0$ : the number $1$ is the product of no primes at all.

Products of lists are defined by the recursion of Sets and Functions, Definition 3.3.1. That definition was made for sequences of real numbers, and we use it as a pattern, as Number Systems, Section 1.4 allows for definitions read on a new number system, with the ordered field $\mathbb{Q}$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 3.2.1) in place of $\mathbb{R}$ . A product of integers is an integer (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 3.1.4), so the products of lists below lie in $\mathbb{Z}$ ; the paragraph “Why the product exists” below checks directly that the recursion runs in $\mathbb{Z}$ .

2.2.3. Small primes

Later arguments need to know that a few small integers are prime in the constructed $\mathbb{Z}$ . Sets and Functions, Section 1.1 checked some of these after Sets and Functions, Definition 1.1.3, for the school integers; that check is not a proof about the ring of Number Systems, Chapter 2, so we redo it here.

Remark. The small-primes remark. The integers $2$ , $3$ , $5$ and $7$ are prime in $\mathbb{Z}$ . Let $p \in \{2, 3, 5, 7\}$ . Then $p \ge 2$ . Let $d$ be a positive divisor of $p$ . Then $1 \le d$ by discreteness (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (c)) and $d \le p$ by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e), so $d$ is one of $1, 2, \dots, p$ : applying discreteness repeatedly (if $d \ne 1$ then $2 \le d$ ; if $d \ne 2$ then $3 \le d$ ; and so on up to $p$ ) leaves no other value. Each $d$ with $1 < d < p$ leaves a non-zero remainder: $\begin{aligned} 3 &= 1 \cdot 2 + 1, \qquad 5 = 2 \cdot 2 + 1 = 1 \cdot 3 + 2 = 1 \cdot 4 + 1, \\ 7 &= 3 \cdot 2 + 1 = 2 \cdot 3 + 1 = 1 \cdot 4 + 3 = 1 \cdot 5 + 2 = 1 \cdot 6 + 1 . \end{aligned}$ (For $p = 2$ there is no such $d$ .) So $d \nmid p$ for these $d$ , by the divisibility test after Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2: $p = kd$ would give $p = kd + 0$ , a second division of $p$ by $d$ , with remainder $0$ , against the uniqueness in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2 (a). Hence the positive divisors of $p$ are $1$ and $p$ , and $p$ is prime.

The later sections of this chapter cite this paragraph as “the small-primes remark”. The same procedure decides, for any given $p \ge 2$ , whether $p$ is prime; the remark after Lemma 2.2.4 shortens it.

Definition 2.2.1 (List, Product of a List, Prime Factorization)

Let $k \in \mathbb{N}$ . A list of length $k$ in $\mathbb{Z}$ is a function $p \colon \{1, \dots, k\} \to \mathbb{Z}$ , written $(p_1, \dots, p_k)$ with $p_i \mathrel{:=} p(i)$ ; for $k = 0$ it is the empty list. Its product $\prod_{i=1}^{k} p_i \in \mathbb{Z}$ is given by the recursion $\prod_{i=1}^{0} p_i = 1 , \qquad \prod_{i=1}^{j+1} p_i = \Bigl( \prod_{i=1}^{j} p_i \Bigr) p_{j+1} \quad \text{for } j < k ,$ where $\prod_{i=1}^{j} p_i$ is the product of the shortened list $(p_1, \dots, p_j)$ .

A prime factorization of $n \in \mathbb{Z}_{>0}$ is a list $(p_1, \dots, p_k)$ such that every entry $p_i$ is prime (Sets and Functions, Definition 1.1.3), the list is non-decreasing ( $i \le j$ implies $p_i \le p_j$ ), and $\prod_{i=1}^{k} p_i = n$ .

In words: a list is a finite sequence of integers, possibly empty; its product starts at $1$ and multiplies by one more entry at each stage; and a prime factorization lists primes in non-decreasing order with the right product.

Why the product exists. Extend the list to a sequence $\bar p$ on $\mathbb{Z}_{>0}$ by $\bar p_i \mathrel{:=} p_i$ for $i \le k$ and $\bar p_i \mathrel{:=} 1$ for $i > k$ . Then Sets and Functions, Theorem 3.3.1, read on $\mathbb{N} = \omega$ through Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Corollary 1.4.3 (b), with $X = \mathbb{Z}$ , starting value $1$ and step $g(j, x) \mathrel{:=} x \bar p_{j+1}$ , gives exactly one function $P \colon \mathbb{N} \to \mathbb{Z}$ with $P_0 = 1$ and $P_{j+1} = P_j \bar p_{j+1}$ ; we set $\prod_{i=1}^{j} p_i \mathrel{:=} P_j$ for $j \le k$ . The “Finite lists” remark after Sets and Functions, Definition 3.3.1 shows that $P_j$ depends only on $p_1, \dots, p_j$ , not on how the list was extended. Its proof is an induction on $j$ that uses only the recursion and the multiplication of the target set, so it runs unchanged in $\mathbb{Q}$ , and, since $\mathbb{Z}$ is closed under multiplication, with target set $\mathbb{Z}$ . In particular $P_j$ is also the product of the shortened list $(p_1, \dots, p_j)$ , which is the displayed recursion. We cite it as the recursion of Definition 2.2.1: it peels the last entry off a product.

Examples.

$(2, 2, 3, 5)$ is a prime factorization of $60$ . Its entries are prime by the small-primes remark above; it is non-decreasing; and the recursion gives the products $1, 2, 4, 12, 60$ .
$(5)$ is a prime factorization of $5$ , with products $1, 5$ . A prime $p$ has the one-entry factorization $(p)$ .
The case of the empty list: the empty list is a prime factorization of $1$ . Its product is $1$ by the first clause of the recursion, and the conditions “every entry is prime” and “non-decreasing” hold vacuously. Without this case the number $1$ would have no factorization, and the theorem below would fail for $n = 1$ ; its existence proof uses this case to rule out $n = 1$ .

Order and primality. Exchange two entries of the first example: $(2, 3, 2, 5)$ has prime entries and product $60$ , but it is not non-decreasing, since positions $2 \le 3$ carry $3 > 2$ . Merge two entries: $(2, 2, 15)$ is non-decreasing with product $60$ , but $15 = 3 \cdot 5$ is not prime.

Why these clauses. Without “non-decreasing”, $60$ would have twelve factorizations, its four primes in every order, and uniqueness could only be stated up to rearrangement, which needs a theory of permutations. Without “prime”, splitting would stop anywhere. And the requirement $p \ge 2$ in Sets and Functions, Definition 1.1.3 is what keeps $(1, 2, 2, 3, 5)$ out: if $1$ counted as a prime, every factorization could be padded with as many $1$ s as we like.

Quick check. Find the prime factorization of $360$ , and check each clause of Definition 2.2.1.

Solution. $(2, 2, 2, 3, 3, 5)$ . Its entries are prime by the small-primes remark above. It is non-decreasing. Its products, by the recursion, are $1, 2, 4, 8, 24, 72, 360$ . By the theorem below there is no other.

2.2.4. Primes dividing products

For a prime, the coprimality that Euclid’s lemma asks for comes almost free: a prime shares no factor with a number unless it divides that number.

Corollary 2.2.2 (A Prime Dividing a Product)

Let $p$ be prime.

(a) For every $a \in \mathbb{Z}$ : $p \mid a$ or $\gcd(p, a) = 1$ .
(b) For all $b, c \in \mathbb{Z}$ : if $p \mid bc$ , then $p \mid b$ or $p \mid c$ .
(c) If $(q_1, \dots, q_l)$ is a list of primes, with $l \in \mathbb{N}$ , and $p \mid \prod_{j=1}^{l} q_j$ , then $p = q_j$ for some $j \in \{1, \dots, l\}$ .

Idea. For (a), the gcd of $p$ and $a$ is a positive divisor of $p$ , so it is $1$ or $p$ , and the second case says $p \mid a$ . Then (b) is Euclid’s lemma in the case $\gcd(p, b) = 1$ of (a). For (c), peel the last prime off the product and apply (b) to the two factors; an induction on the length handles the rest, and a prime that divides a prime is equal to it.

Proof. (a) Since $p \ge 2$ , $(p, a) \ne (0, 0)$ , so $g \mathrel{:=} \gcd(p, a) \ge 1$ (Definition 2.1.2). As a common divisor, $g \mid p$ and $g \mid a$ . So $g$ is a positive divisor of the prime $p$ , and $g = 1$ or $g = p$ (Sets and Functions, Definition 1.1.3). If $g = p$ , then $p \mid a$ .

(b) Let $p \mid bc$ . By (a), $p \mid b$ or $\gcd(p, b) = 1$ . In the second case Theorem 2.2.1, with $a = p$ , gives $p \mid c$ .

(c) We use Logic and Proof, Axiom 4.2.1 (through Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Corollary 1.4.3 (b)) on $l$ , for $P(l)$ : “for every list of primes $(q_1, \dots, q_l)$ , if $p \mid \prod_{j=1}^{l} q_j$ , then $p = q_j$ for some $j \le l$ ”.

Base case $P(0)$ . The empty product is $1$ (the recursion of Definition 2.2.1). If $p \mid 1$ , then $p = 1$ or $p = -1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (g)), and both contradict $p \ge 2$ . So the hypothesis of $P(0)$ never holds, and $P(0)$ is true.

Step. Assume $P(l)$ , and let $(q_1, \dots, q_{l+1})$ be a list of primes with $p \mid \prod_{j=1}^{l+1} q_j$ . By the recursion of Definition 2.2.1, $\prod_{j=1}^{l+1} q_j = \Bigl( \prod_{j=1}^{l} q_j \Bigr) q_{l+1} ,$ where the first factor is the product of the list of primes $(q_1, \dots, q_l)$ . By (b), $p$ divides that first factor or $p \mid q_{l+1}$ . In the first case $P(l)$ gives $j \le l$ with $p = q_j$ . In the second, $p \ge 2 > 0$ is a positive divisor of the prime $q_{l+1}$ , so $p \in \{1, q_{l+1}\}$ , and $p \ne 1$ ; hence $p = q_{l+1}$ . This proves $P(l + 1)$ , and with it the corollary.

Part (b) is the property promised at the start of the section, and it is what makes primes the right atoms for multiplication. It fails for $6$ , which is not prime: $6 \mid 2 \cdot 3$ , but $6 \nmid 2$ and $6 \nmid 3$ , since $0 < 2 < 6$ and $0 < 3 < 6$ rule both out by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e).

The second application of Euclid’s lemma combines two coprime divisors into one.

Proposition 2.2.3 (Coprime Divisors of a Number)

Let $m, n, c \in \mathbb{Z}$ with $m \mid c$ , $n \mid c$ and $\gcd(m, n) = 1$ . Then $mn \mid c$ .

Proof. Write $c = km$ with $k \in \mathbb{Z}$ . Then $n \mid km$ , and $\gcd(n, m) = \gcd(m, n) = 1$ (Definition 2.1.2), so Theorem 2.2.1 gives $n \mid k$ , say $k = ln$ with $l \in \mathbb{Z}$ . Hence $c = (ln)m = l(mn)$ , by (F5) and (F6), and $mn \mid c$ .

The coprimality is needed: $4 \mid 12$ and $6 \mid 12$ , but $24 \nmid 12$ , since a positive divisor of $12$ is at most $12$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e)); here $\gcd(4, 6) = 2$ .

2.2.5. The least divisor is prime

The existence half of unique factorization needs a supply of primes: every integer $n \ge 2$ must have a prime factor. Sets and Functions, Section 3.2 proved this for the school integers by strong induction (Sets and Functions, Theorem 3.2.5). On the constructed $\mathbb{Z}$ the least-element property gives a shorter route: the least divisor bigger than $1$ is already prime.

Lemma 2.2.4 (The Least Divisor Is Prime)

Let $n \in \mathbb{Z}$ with $n \ge 2$ . The set $D \mathrel{:=} \{ d \in \mathbb{Z} : d \ge 2 \text{ and } d \mid n \}$ has a least element, and that element is prime. In particular, $n$ has a prime factor.

Proof. Since $n \ge 2$ and $n \mid n$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (a)), $n \in D$ , so $D$ is non-empty; and $2$ is a lower bound of $D$ by its definition. By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.4, $D$ has a least element $p$ .

Suppose $p$ were not prime. Since $p \ge 2$ , the clause of Sets and Functions, Definition 1.1.3 that fails is the one about divisors: $p$ has a positive divisor $e$ with $e \ne 1$ and $e \ne p$ . Then $e \ge 1$ by discreteness (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (c)), and $e \le p$ by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e). So $1 < e < p$ , and $e \ge 2$ by discreteness again. Also $e \mid p$ and $p \mid n$ give $e \mid n$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (b)). So $e \in D$ and $e < p$ , against the choice of $p$ . Hence $p$ is prime, and $p \mid n$ because $p \in D$ .

Remark. This is Sets and Functions, Theorem 3.2.5 on the constructed $\mathbb{Z}$ , proved by a least element instead of strong induction. It also shortens the primality test of the small-primes remark above. If $p \ge 2$ is not prime, its least divisor $e \ge 2$ is prime by the lemma, so it is not $p$ itself, and $p = ef$ with $f \in \mathbb{Z}$ ; then $f > 0$ (as $e, p > 0$ ), $f \ne 1$ , so $f \ge 2$ and $f \mid p$ , and therefore $e \le f$ by the choice of $e$ . Multiplying by $e > 0$ gives $e \cdot e \le ef = p$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (c), or equality if $e = f$ ). So to prove $p \ge 2$ prime it is enough to check that no $d$ with $d \ge 2$ and $d \cdot d \le p$ divides $p$ . For $11$ only $d = 2, 3$ need checking, since $4 \cdot 4 = 16 > 11$ .

2.2.6. The fundamental theorem

Everything is now in place for the main result of the chapter’s first half.

Theorem 2.2.5 (Fundamental Theorem of Arithmetic)

Every $n \in \mathbb{Z}_{>0}$ has exactly one prime factorization.

Idea. Existence. Take the least $n$ with no factorization. It is at least $2$ , so it has prime factors, and a largest one, $p$ . Then $n = pm$ with $m < n$ , so $m$ has a factorization. Every entry of it divides $n$ , so it is at most $p$ , and appending $p$ at the end keeps the list non-decreasing.

Uniqueness. Take two factorizations with the same product, $(p_1, \dots, p_k)$ and $(q_1, \dots, q_l)$ . The largest entry $p_k$ divides the product of the $q$ ’s, so by Corollary 2.2.2 (c) it is one of the $q_j$ , and that is at most the largest, $q_l$ . By symmetry $q_l \le p_k$ . So the two last entries are equal; cancel them and induct on the length.

Before reading on: why compare the largest primes, $p_k$ and $q_l$ , and not the first ones?

Proof. Existence. Let $B \mathrel{:=} \{ n \in \mathbb{Z}_{>0} : n \text{ has no prime factorization} \}$ , and suppose $B \ne \emptyset$ . It has the lower bound $0$ , so it has a least element $n$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.4). The empty list is a prime factorization of $1$ , so $n \ne 1$ ; as $n \ge 1$ (discreteness, Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (c)), $n > 1$ , and so $n \ge 2$ by discreteness.

The set $F$ of prime factors of $n$ is non-empty by Lemma 2.2.4. Each $q \in F$ is positive and divides $n > 0$ , so $q \le n$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e)). By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.4, $F$ has a greatest element $p$ . Write $n = mp$ with $m \in \mathbb{Z}$ . If $m \le 0$ , then $mp \le 0$ ( $m = 0$ : Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.3.2 (b); $m < 0$ : $mp < 0 \cdot p = 0$ by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (c)), against $n > 0$ . So $m > 0$ , that is, $m \in \mathbb{Z}_{>0}$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (b)). Moreover $m < n$ : since $p \ge 2$ and $m > 0$ , $n = pm \ge 2m = m + m > m$ , by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (c) (or equality if $p = 2$ ), (F9) with (F7), and (O3).

By the minimality of $n$ , $m \notin B$ : let $(q_1, \dots, q_l)$ be a prime factorization of $m$ . If $l \ge 1$ , the recursion of Definition 2.2.1 gives $m = \bigl(\prod_{j=1}^{l-1} q_j\bigr) q_l$ , so $q_l \mid m$ ; with $m \mid n$ this gives $q_l \mid n$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (b)), so $q_l \in F$ and $q_l \le p$ . As the list is non-decreasing, $q_i \le q_l \le p$ for every $i \le l$ . Now let $(q_1, \dots, q_l, p)$ be the list of length $l + 1$ whose first $l$ entries are those of $(q_1, \dots, q_l)$ and whose last entry is $p$ . Its entries are prime. It is non-decreasing: two positions among the first $l$ compare as before, and every entry is at most $p$ (for $l = 0$ it is the one-entry list $(p)$ , and there is nothing to check). By the recursion its product is $\Bigl( \prod_{j=1}^{l} q_j \Bigr) p = mp = n .$ So $n$ has a prime factorization, against $n \in B$ . Hence $B = \emptyset$ .

Uniqueness. We prove, by Logic and Proof, Axiom 4.2.1 (through Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Corollary 1.4.3 (b)) on $k$ , the statement $P(k)$ : “for every $l \in \mathbb{N}$ , if $(p_1, \dots, p_k)$ and $(q_1, \dots, q_l)$ are non-decreasing lists of primes with $\prod_{i=1}^{k} p_i = \prod_{j=1}^{l} q_j$ , then $l = k$ and $p_i = q_i$ for every $i \le k$ ”. Two prime factorizations of the same $n$ are such lists, so $P(k)$ for every $k$ gives the uniqueness.

First, a non-empty list of primes $(r_1, \dots, r_h)$ does not have product $1$ : by the recursion its product is $\bigl(\prod_{i=1}^{h-1} r_i\bigr) r_h$ , so $r_h$ would divide $1$ , and $r_h = \pm 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (g)) contradicts $r_h \ge 2$ .

Base case $P(0)$ . If $k = 0$ , then $\prod_{j=1}^{l} q_j = 1$ , so $l = 0$ by the previous paragraph, and both lists are empty.

Step. Assume $P(k)$ . Let $(p_1, \dots, p_{k+1})$ and $(q_1, \dots, q_l)$ be non-decreasing lists of primes with the same product $N$ . Since $k + 1 \ge 1$ , $N \ne 1$ , so $l \ge 1$ . By the recursion, $p_{k+1} \mid N = \prod_{j=1}^{l} q_j$ , so Corollary 2.2.2 (c) gives $p_{k+1} = q_j$ for some $j \le l$ , and $q_j \le q_l$ because the $q$ -list is non-decreasing. In the same way $q_l \mid N = \prod_{i=1}^{k+1} p_i$ gives $q_l = p_i \le p_{k+1}$ for some $i \le k + 1$ . So $p_{k+1} \le q_l \le p_{k+1}$ , and $p_{k+1} = q_l$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (i)). By the recursion, $\Bigl( \prod_{i=1}^{k} p_i \Bigr) p_{k+1} = N = \Bigl( \prod_{j=1}^{l-1} q_j \Bigr) p_{k+1} .$ Subtracting, $\bigl(\prod_{i=1}^{k} p_i - \prod_{j=1}^{l-1} q_j\bigr) p_{k+1} = 0$ by (F9) and Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.3.2 (c), and $p_{k+1} \ne 0$ , so the bracket is $0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (f)). The shortened lists $(p_1, \dots, p_k)$ and $(q_1, \dots, q_{l-1})$ are non-decreasing lists of primes with equal products, so $P(k)$ , applied with $l - 1 \in \mathbb{N}$ , gives $l - 1 = k$ and $p_i = q_i$ for $i \le k$ . With $p_{k+1} = q_l = q_{k+1}$ , the two lists have the same length $k + 1$ and the same entries, so they are equal (Sets and Functions, Proposition 2.1.1). This proves $P(k + 1)$ , and the theorem.

Why compare the largest primes? The recursion of Definition 2.2.1 peels off the last factor, so once the two last entries are known to be equal they can be canceled at once, leaving two shortened lists to which $P(k)$ applies. And the comparison “largest with largest” needs only that both lists are non-decreasing. Comparing the first entries would also show $p_1 = q_1$ , but removing a first entry shifts every index, and the recursion says nothing directly about that.

Remark. Sets and Functions, Section 3.2 named unique factorization as a fact it did not prove or use, and Sets and Functions, Exercise (B2: Putting a proof in order) lists, as line (vii), a step that cites it and is therefore not available there. On the constructed $\mathbb{Z}$ the fact is now proved, and Exercise R2 of Section 2.4 uses it.

Warning. Uniqueness is not automatic. Let $H \mathrel{:=} \{ 4k + 1 : k \in \mathbb{N} \} = \{1, 5, 9, 13, 17, 21, \dots\}$ . It is closed under multiplication, since $(4k + 1)(4l + 1) = 4(4kl + k + l) + 1$ . Call $h \in H$ with $h > 1$ an $H$ -prime if it is not a product of two elements of $H$ both greater than $1$ . Then $9$ , $21$ and $49$ are $H$ -primes, and $441 = 9 \cdot 49 = 21 \cdot 21$ gives two different factorizations into $H$ -primes. What breaks is Euclid’s lemma: $9$ divides $21 \cdot 21$ inside $H$ , but $9 \nmid 21$ . The proof of Theorem 2.2.1 wrote $1 = ax + by$ , with sums and with negative coefficients, and $H$ is closed under neither. The proof of uniqueness above is only as good as Euclid’s lemma.

2.2.7. Lowest terms

Every rational number is a fraction in many ways: $6/4 = 3/2 = 9/6$ . Number Systems, Section 3.1 found, in its Exercise C1, a least positive denominator by the least-element property, and Sets and Functions, Section 3.2 removed common factors of $2$ only (Sets and Functions, Lemma 3.2.4). With the gcd we can remove every common factor at once, and Euclid’s lemma shows that the result is unique. Recall that after the identification of Number Systems, Section 3.1, $p/q \mathrel{:=} pq^{-1}$ in $\mathbb{Q}$ for $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ , and $p/q = r/s$ holds if and only if $ps = rq$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 3.1.4 (b)).

Proposition 2.2.6 (Lowest Terms)

Let $x \in \mathbb{Q}$ .

(a) There are $p \in \mathbb{Z}$ and $q \in \mathbb{Z}_{>0}$ with $x = p/q$ and $\gcd(p, q) = 1$ , and the pair $(p, q)$ is unique.
(b) If $x = r/s$ with $r \in \mathbb{Z}$ and $s \in \mathbb{Z}_{>0}$ , then $r = tp$ and $s = tq$ for some $t \in \mathbb{Z}_{>0}$ . In particular $q \mid s$ and $q \le s$ : $q$ is the least positive denominator of $x$ .

Idea. For existence, divide numerator and denominator by their gcd $d$ ; the Bézout identity for $d$ , divided by $d$ , is a Bézout identity $1 = px_0 + qy_0$ for the new pair. For (b), cross-multiplying gives $ps = rq$ , so $q \mid ps$ , and Euclid’s lemma removes $p$ . Uniqueness is (b) applied to a second coprime pair.

Proof. Existence in (a). By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 3.1.4 (b), $x = r/s$ for some $r \in \mathbb{Z}$ , $s \in \mathbb{Z}_{>0}$ . Since $s \ne 0$ , $d \mathrel{:=} \gcd(r, s) \ge 1$ , and by Theorem 2.1.1 (d) there are $x_0, y_0 \in \mathbb{Z}$ with $d = rx_0 + sy_0$ . As $d \mid r$ and $d \mid s$ , write $r = dp$ and $s = dq$ with $p, q \in \mathbb{Z}$ . If $q \le 0$ , then $dq \le 0$ (as in the existence proof of Theorem 2.2.5), against $s > 0$ ; so $q \in \mathbb{Z}_{>0}$ . Now $d \cdot 1 = d = (dp)x_0 + (dq)y_0 = d(px_0 + qy_0) ,$ so $d(px_0 + qy_0 - 1) = 0$ , and since $d \ne 0$ , $px_0 + qy_0 = 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (f)). Hence $\gcd(p, q) = 1$ by Corollary 2.1.2. Finally $rq = dpq = p(dq) = ps$ , so $r/s = p/q$ by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 3.1.4 (b), and $x = p/q$ .

(b), for any such pair. Let $x = p/q$ with $\gcd(p, q) = 1$ , and $x = r/s$ with $s > 0$ . By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 3.1.4 (b), $ps = rq$ . So $q \mid ps$ , and $\gcd(q, p) = 1$ , hence $q \mid s$ by Theorem 2.2.1; write $s = tq$ with $t \in \mathbb{Z}$ . Since $s > 0$ and $q > 0$ , $t > 0$ , by the sign argument used for $q$ above. Then $q(pt) = ps = rq$ , so $q(pt - r) = 0$ , and $r = tp$ because $q \ne 0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (f)). As $q$ and $s$ are positive, $q \mid s$ gives $q \le s$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e)).

Uniqueness in (a). Let $(r, s)$ be a second pair with $x = r/s$ , $s > 0$ and $\gcd(r, s) = 1$ . By (b), $r = tp$ and $s = tq$ with $t > 0$ . So $t$ is a common divisor of $r$ and $s$ , and it divides $\gcd(r, s) = 1$ (Theorem 2.1.1 (c), (d)). Hence $t = 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (g), with $t > 0$ ), and $(r, s) = (p, q)$ .

So the least denominator $N(x)$ of Number Systems, Section 3.1’s Exercise C1 is the $q$ of (a), and every other denominator of $x$ is a multiple of it. For example $252/198$ has $\gcd(252, 198) = 18$ (Example (Two runs of the algorithm)), and $252 = 18 \cdot 14$ , $198 = 18 \cdot 11$ , so its lowest terms are $14/11$ .

Remark. The twins in Sets and Functions, Section 3.2 are Sets and Functions, Lemma 3.2.4, which removes only factors of $2$ , and Sets and Functions, Exercise (C2: Lowest terms, used later), which asks for lowest terms in the full sense, for the school $\mathbb{Q}$ . Proposition 2.2.6 is the full statement, with uniqueness, for the constructed $\mathbb{Q}$ .

2.2.8. Exercises

A. Check your understanding

Exercise (A1)

These questions are about the uniqueness half of the proof of Theorem 2.2.5.

(a) Why must the empty list count as a prime factorization?
(b) Run the induction step on $(p_1, p_2, p_3, p_4) = (2, 2, 3, 5)$ and a second prime factorization $(q_1, \dots, q_l)$ of $60$ . Which equalities does the proof derive, and to which two lists is $P(3)$ applied?
(c) Which line of the proof uses Euclid’s lemma, and through which result?
(d) Where is “non-decreasing” used?
(e) Give the idea of the uniqueness proof in two sentences.

Solution.

(a) Otherwise the number $1$ would have no prime factorization, and the theorem would be false for $n = 1$ . The existence proof uses it to exclude $n = 1$ from $B$ . (The base case $P(0)$ of the uniqueness proof concerns the empty list as a list of primes with product $1$ , which it is in any case.)
(b) The step first gets $l \ge 1$ , since the product is $60 \ne 1$ . Then $p_4 = 5$ divides $\prod q_j$ , so $5 = q_j \le q_l$ for some $j$ ; and $q_l$ divides $60 = 2 \cdot 2 \cdot 3 \cdot 5$ , so $q_l = p_i \le 5$ for some $i$ . Hence $q_l = 5$ . Canceling $5$ gives $\prod_{j=1}^{l-1} q_j = 2 \cdot 2 \cdot 3 = 12$ , and $P(3)$ is applied to $(2, 2, 3)$ and $(q_1, \dots, q_{l-1})$ , which gives $l - 1 = 3$ and $(q_1, q_2, q_3) = (2, 2, 3)$ .
(c) The lines “ $p_{k+1} = q_j$ for some $j$ ” and “ $q_l = p_i$ for some $i$ ”. They cite Corollary 2.2.2 (c), whose step uses (b), which is Theorem 2.2.1 applied with $a = p$ .
(d) In $q_j \le q_l$ and in $p_i \le p_{k+1}$ : the entry found in the other list is at most that list’s last entry.
(e) The largest prime of one factorization divides the other product, so by Euclid’s lemma it is an entry there, hence at most the other’s largest; by symmetry the two largest entries are equal. Canceling them leaves two shorter factorizations with equal products, and induction on the length finishes.

B. Practice

Exercise (B1: Put the proof in order)

The following lines contain a proof of Theorem 2.2.1, shuffled, together with two lines that do not belong. Write the seven correct lines in an order that makes a proof, say which other orders are also admissible, and say why each of the other two lines fails.

(i) Suppose $a \mid bc$ and $\gcd(a, b) = 1$ .
(ii) There are $x, y \in \mathbb{Z}$ with $ax + by = 1$ .

(ii′) Since $\gcd(a, b) = 1$ and $a \mid bc$ , we have $a \mid b$ or $a \mid c$ .
(iii) Multiplying by $c$ : $c = acx + bcy$ .
(iii′) Dividing $1 = ax + by$ by $a$ : $1/a = x + (b/a)y$ .
(iv) $a \mid acx$ , since $acx = a(cx)$ .
(v) Write $bc = ak$ ; then $bcy = a(ky)$ , so $a \mid bcy$ .
(vi) Hence $a \mid acx + bcy$ .
(vii) So $a \mid c$ .

Solution. An admissible order is (i), (ii), (iii), (iv), (v), (vi), (vii):

Suppose $a \mid bc$ and $\gcd(a, b) = 1$ . There are $x, y \in \mathbb{Z}$ with $ax + by = 1$ (Corollary 2.1.2). Multiplying by $c$ : $c = acx + bcy$ . Then $a \mid acx$ , since $acx = a(cx)$ . Write $bc = ak$ ; then $bcy = a(ky)$ , so $a \mid bcy$ . Hence $a \mid acx + bcy$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (c)). So $a \mid c$ .

Line (i) comes first, and (ii) needs its hypothesis $\gcd(a, b) = 1$ . Lines (iii), (iv) and (v) each need only (ii): (iii) multiplies its equation, and (iv) and (v) mention its $x$ and $y$ ; (v) also uses the hypothesis $a \mid bc$ of (i). None of these three uses another of them. Line (vi) needs both (iv) and (v), but not (iii), since $acx + bcy$ is just an expression in $a, b, c, x, y$ . Line (vii) rewrites (vi) through the equation of (iii), so it needs both and comes last. The admissible orders are therefore those that start (i), (ii), end with (vii), and place (vi) after (iv) and (v); there are eight. For example, (i), (ii), (iv), (v), (vi), (iii), (vii) is admissible: (iii) may come anywhere before (vii).

The distractor (ii′) cites a “fact” that is not available as a step for arbitrary $a$ . For a prime $a$ it is Corollary 2.2.2 (b), which is proved from this lemma, so citing it here is circular. For a general integer $a$ the line is the lemma itself in a weaker form, so citing it is circular again; only special cases are available (for $a = \pm 1$ , $a \mid b$ by Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (a), with (d) for $-1$ ), and the proof must work for every $a$ . Either way the line uses what has not been established, which is (N9) of Logic and Proof, Example (What is not allowed).

The distractor (iii′) divides in $\mathbb{Z}$ , where there is no division: $a$ may be $0$ ( $\gcd(0, 1) = 1$ ), and then the line divides by $0$ ; for $a \ne 0$ , $1/a$ is not an integer unless $a = \pm 1$ . Divisibility is defined by multiplication (Sets and Functions, Definition 1.1.2), not by fractions.

Exercise (B2: The least common multiple)

Let $a, b \in \mathbb{Z}_{>0}$ , and let $M \mathrel{:=} \{ m \in \mathbb{Z}_{>0} : a \mid m \text{ and } b \mid m \}$ . Prove that $M$ has a least element $L$ , and that $L \mid c$ for every $c \in \mathbb{Z}$ with $a \mid c$ and $b \mid c$ .

The first part of a proof is given.

$ab > 0$ by (O4), and $a \mid ab$ , $b \mid ab$ , so $ab \in M$ ; and $0$ is a lower bound of $M$ . By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.4, $M$ has a least element $L$ . Let $c \in \mathbb{Z}$ with $a \mid c$ and $b \mid c$ . By Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2 (a), $c = qL + r$ with $q, r \in \mathbb{Z}$ and $0 \le r < L$ . Since $r = c + (-q)L$ , and $a$ divides $c$ and $L$ , $a \mid r$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (c)); likewise $b \mid r$ .

The last step is blank. Say which method this is, then complete it.

Solution. The method is least positive element, then divide: the remainder lies in the set and is smaller than its least positive element, so it is not positive.

Completion: if $r > 0$ , then $r \in \mathbb{Z}_{>0}$ is a common multiple of $a$ and $b$ , so $r \in M$ , and $r < L$ , against the choice of $L$ . Hence $r = 0$ (as $r \ge 0$ ), and $c = qL$ , that is, $L \mid c$ .

The same argument proved Theorem 2.1.1 (b), with the set of positive combinations in place of $M$ . This is the twin of Sets and Functions, Example (The supremum under divisibility is the least common multiple), now on the constructed $\mathbb{Z}$ .

Exercise (B3: Two factorizations and a gcd)

Find the prime factorizations of $1001$ and of $2^{10} - 1$ , proving that each entry is prime. Then show that $\gcd(1001, 1023) = 11$ in two ways. First, use the factorizations to write $1001 = 11 \cdot 91$ and $1023 = 11 \cdot 93$ : show $\gcd(91, 93) = 1$ , and deduce $\gcd(1001, 1023) = 11$ from a Bézout identity for $91$ and $93$ (Corollary 2.1.2). Second, use the Euclidean algorithm.

Hint: the remark after Lemma 2.2.4 shortens each primality check. Do not use the school rule “the gcd is the product of the shared primes”: this chapter does not prove it.

Solution. Factorizations. $1001 = 7 \cdot 143 = 7 \cdot 11 \cdot 13$ , and $2^{10} - 1 = 1024 - 1 = 1023 = 3 \cdot 341 = 3 \cdot 11 \cdot 31$ . So the prime factorizations are $(7, 11, 13)$ and $(3, 11, 31)$ , both non-decreasing, once the entries are known to be prime. The primes $3$ and $7$ are covered by the small-primes remark above. For $11$ , $13$ and $31$ we use the remark after Lemma 2.2.4: it suffices that no $d \ge 2$ with $d \cdot d \le p$ divides $p$ .

$p = 11$ and $p = 13$ : $d \in \{2, 3\}$ , since $d \ge 4$ gives $d \cdot d \ge 16$ . The divisions $11 = 5 \cdot 2 + 1 = 3 \cdot 3 + 2$ and $13 = 6 \cdot 2 + 1 = 4 \cdot 3 + 1$ leave non-zero remainders.
$p = 31$ : $d \in \{2, 3, 4, 5\}$ , since $d \ge 6$ gives $d \cdot d \ge 36$ . The divisions $31 = 15 \cdot 2 + 1 = 10 \cdot 3 + 1 = 7 \cdot 4 + 3 = 6 \cdot 5 + 1$ leave non-zero remainders.

A non-zero remainder means $d \nmid p$ , by the uniqueness in Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.5.2 (a). By Theorem 2.2.5 these are the only prime factorizations.

The gcd from the factorizations. We have $1001 = 11 \cdot 91$ and $1023 = 11 \cdot 93$ . First, $\gcd(91, 93) = 1$ : a common divisor of $91$ and $93$ divides $93 - 91 = 2$ , so a positive one is $1$ or $2$ (discreteness), and $2 \nmid 91 = 45 \cdot 2 + 1$ . By Corollary 2.1.2, $91x + 93y = 1$ for some $x, y \in \mathbb{Z}$ ; indeed $91 \cdot 46 - 93 \cdot 45 = 4186 - 4185 = 1$ . Multiplying by $11$ , $1001 \cdot 46 - 1023 \cdot 45 = 11 .$ So every common divisor of $1001$ and $1023$ divides $11$ , and a positive one is at most $11$ . Since $11$ is itself a common divisor, $\gcd(1001, 1023) = 11$ .

The gcd by the algorithm (Theorem 2.1.4): $1023 = 1 \cdot 1001 + 22$ , $1001 = 45 \cdot 22 + 11$ , $22 = 2 \cdot 11 + 0$ . The last non-zero remainder is $11$ .

Uses: Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (c) (divides every combination); Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e) (positive divisor is smaller); Definition 2.1.2.

C. Going deeper

Exercise (C1: Chapter check: unique factorization)

Prove that two prime factorizations of the same positive integer are equal: the uniqueness half of Theorem 2.2.5. You may cite Theorem 2.2.1 and Corollary 2.2.2.

Solution. The proof of uniqueness in Theorem 2.2.5 is a complete answer. Its steps, in order: set up $P(k)$ for non-decreasing lists of primes of length $k$ and arbitrary length $l$ , with equal products; base case $k = 0$ , where a non-empty list of primes cannot have product $1$ ; in the step, $l \ge 1$ , then $p_{k+1} = q_j \le q_l$ and $q_l = p_i \le p_{k+1}$ by Corollary 2.2.2 (c) (proved from Euclid’s lemma by induction on the length of the product) and the order of the lists; so $p_{k+1} = q_l$ ; cancel this non-zero factor (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (f)); apply $P(k)$ to the shortened lists.

What a complete answer needs. (10 points) - 2: sets up an induction on the length of one list (or a least counterexample), with the statement quantified over all lengths of the other list, and proves the base case. - 3: shows that the largest (or any chosen) prime of one list divides the other product, and identifies it with an entry of the other list by Euclid’s lemma for products of several factors (cited as Corollary 2.2.2 (c), or proved by induction from Euclid’s lemma). - 2: uses the symmetric step and the non-decreasing order to get equality of the two chosen extreme entries (both largest, or both smallest). - 1: justifies the cancellation by the absence of zero divisors. - 2: applies the induction hypothesis (or minimality) to the shortened lists and concludes equality of length and entries. Slips that lose the step: using the uniqueness of the factorization of a smaller number without an induction or a least counterexample set up; applying Euclid’s lemma for two factors to a product of many with no induction. Canceling a prime without noting that it is non-zero costs 1 point and does not lose the step. A least-counterexample proof on $n$ (the least positive integer with two different factorizations) maps to the same points: its set-up and the case $n = 1$ take the first 2, and “the cofactor $m$ in $n = m p_k$ has only one factorization” takes the last 2. A proof that compares the smallest entries $p_1 = q_1$ earns the same points, provided it proves (for example by induction on the length) that a product equals its first entry times the product of the re-indexed list $(p_2, \dots, p_{k+1})$ , and states the re-indexing of the shortened lists $(p_2, \dots, p_{k+1})$ and $(q_2, \dots, q_l)$ before applying the induction hypothesis; asserting that identity without proof costs the 1 cancellation point.

Exercise (C2: Find the error)

Here is a statement and an argument for it.

Claim. Let $m, n, c \in \mathbb{Z}$ . If $m \mid c$ , $n \mid c$ and $\gcd(m, n) = 1$ , then $mn \mid c$ .

Argument. (1) Write $c = mk$ and $c = nl$ with $k, l \in \mathbb{Z}$ . (2) Then $c^2 = c \cdot c = (mk)(nl) = mn \cdot kl$ . (3) So $mn \mid c^2$ . (4) Hence $mn \mid c$ .

Is the claim true? Does the argument prove it? If not, name the line that fails, explain why, and give a counterexample to the step.

Solution. The claim is true: it is Proposition 2.2.3. The argument does not prove it.

Lines (1)–(3) are correct. The failing line is (4). It rests on a general “fact”: $x \mid c^2$ implies $x \mid c$ . That has not been proved, and it is false, so the line cites nothing: entry (N9) of Logic and Proof, Example (What is not allowed). A counterexample to the step: $x = 4$ , $c = 2$ , with $4 \mid 4 = c^2$ and $4 \nmid 2$ (a positive divisor of $2$ is at most $2$ , Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (e)). There is no counterexample to the conclusion, which is true.

A sign that something is wrong: the argument never uses $\gcd(m, n) = 1$ , and without that hypothesis the claim is false ( $4 \mid 12$ , $6 \mid 12$ , $24 \nmid 12$ ). The repair is the proof of Proposition 2.2.3, which spends the coprimality in Euclid’s lemma.

Exercise (C3: There is no last prime)

Prove that no finite list contains every prime: for every list of primes $(p_1, \dots, p_k)$ , with $k \in \mathbb{N}$ , there is a prime that is not an entry of the list.

Solution (Hint 1). Consider $N \mathrel{:=} \prod_{i=1}^{k} p_i + 1$ , and ask which primes can divide it.

Solution (Hint 2). First prove, by induction on $k$ , that every entry of a list of primes divides its product, and that the product is at least $1$ .

Solution. A lemma on products. For a list of primes $(p_1, \dots, p_k)$ , write $P_j \mathrel{:=} \prod_{i=1}^{j} p_i$ for $j \le k$ . We prove, by Logic and Proof, Axiom 4.2.1 (through Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Corollary 1.4.3 (b)) on $j$ , the statement “if $j \le k$ , then $P_j \ge 1$ and $p_i \mid P_j$ for every $i \le j$ ”. Base $j = 0$ : $P_0 = 1$ (the recursion of Definition 2.2.1), and there are no entries to check. Step: let $j + 1 \le k$ ; then $j \le k$ , so the statement holds for $j$ , and $P_{j+1} = P_j p_{j+1}$ by the recursion. Each $p_i$ with $i \le j$ divides $P_j$ , which divides $P_{j+1}$ , so $p_i \mid P_{j+1}$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (b)); and $p_{j+1} \mid P_{j+1}$ by Sets and Functions, Definition 1.1.2. Since $P_j \ge 1 > 0$ and $p_{j+1} \ge 2 > 0$ , $P_{j+1} > 0 \cdot p_{j+1} = 0$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.4.3 (c), Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.3.2 (b)), so $P_{j+1} \ge 1$ by discreteness (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Theorem 2.4.2 (c)).

The new prime. Let $N \mathrel{:=} P_k + 1$ . Then $N \ge 2$ , so its least divisor $q \ge 2$ is prime (Lemma 2.2.4), and $q \mid N$ . If $q = p_i$ for some $i$ , then $q \mid P_k$ by the lemma, so $q$ divides $N - P_k = 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (c)), and $q = \pm 1$ (Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (g)), against $q \ge 2$ . So $q$ is a prime that is not an entry of the list.

For the empty list, $N = 2$ and $q = 2$ . For $(2, 3, 5, 7)$ , $N = 211$ , which happens to be prime; for $(2, 3, 5, 7, 11, 13)$ , $N = 30031 = 59 \cdot 509$ is not, and the new prime is $59$ . The proof promises a new prime factor of $N$ , not that $N$ itself is prime.

This is the direct proof asked for in part (c) of Logic and Proof, Exercise (C1: Euclid without the contradiction), now on the constructed $\mathbb{Z}$ and including the empty list. Its two school facts are replaced by Lemma 2.2.4 and Number Systems: From $\mathbb{N}$ to $\mathbb{R}$ , Proposition 2.5.1 (c).

What a complete answer needs. (10 points) - 2: defines $N$ as the product plus $1$ and shows $N \ge 2$ , with a reason that the product is positive. - 2: shows that each $p_i$ divides the product, by an induction or a cited result. - 2: produces a prime factor $q$ of $N$ , citing Lemma 2.2.4 or an equivalent. - 3: shows $q$ is not any $p_i$ , since it would divide $1$ . - 1: concludes with the quantifiers in order: for every list there is a prime outside it. Slips that lose the step: claiming that $N$ is prime; assuming “the set of primes is finite” and taking its product without a list (no list, no product).