Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$

Definition

Let $p \in \mathbb{Z}$ (The integers as equivalence classes of pairs of naturals), ordered as in Order on the integers, with divisibility as in Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ . Then $p$ is prime when

$p > 1 \qquad \text{and} \qquad d \mid p \ \text{ with } \ d > 0 \ \text{ force } \ d = 1 \ \text{ or } \ d = p .$

In words: $p$ exceeds $1$ , and its only positive divisors are $1$ and $p$ . An integer $n$ with $n > 1$ that is not prime is composite; unfolding the definition, $n$ is composite exactly when $n > 1$ and $n$ has a positive divisor $d$ with $d \ne 1$ and $d \ne n$ .

Numerals. For $k \in \mathbb{N}$ the symbol $k$ inside $\mathbb{Z}$ means $\iota(k)$ , the embedding of The naturals embed in the integers; in particular $0$ and $1$ are the ring constants of Arithmetic on the integers.

Boundary values, stated rather than assumed. $\mathbb{N}$ contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann)) and $\mathbb{Z}$ contains $0$ , $1$ and the negatives, so the small cases are recorded explicitly. The clause $p > 1$ decides all of them at once:

$1$ is not prime, since $1 > 1$ is false, and not composite either, since composite also requires $n > 1$ .
$0$ is not prime, since $0 > 1$ is false. This is decided by the size clause alone and not by counting divisors: every integer divides $0$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ), so the divisor condition is not what rules $0$ out.
Every negative integer is neither prime nor composite, again because $p > 1$ fails. So a prime is in particular positive, and $-2$ , $-3$ , $-5$ are not primes in this library, though each is $-1$ times one.

Thus "prime" and "composite" between them classify exactly the integers greater than $1$ , and nothing else.

The same condition read over all divisors. For $p > 1$ the following are equivalent:

the only positive divisors of $p$ are $1$ and $p$ ;
the only divisors of $p$ are $1$ , $-1$ , $p$ and $-p$ .

That 2 implies 1 is immediate, since of those four only $1$ and $p$ are positive ( $p > 1 > 0$ , so $-1 < 0$ and $-p < 0$ ). For the converse let $d \mid p$ . Since $p > 1$ we have $p \ne 0$ , so $d \ne 0$ by If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$ ; hence the set of divisors of a nonzero integer is bounded above by $|a|$ ; and $|d| \mid p$ , because $|d|$ is $d$ or $-d$ (The absolute value $|a|$ of an integer) and those two divide $p$ together (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ). Also $|d| \ge 0$ and $|d| \ne 0$ (Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ), so $|d| > 0$ and clause 1 gives $|d| = 1$ or $|d| = p$ . If $|d| = 1$ then $d = 1$ or $d = -1$ , by the case split defining $|d|$ ; and if $|d| = p = |p|$ then $d = up$ for a unit $u \in \{1,-1\}$ (For integers $a$ and $b$ the following are equivalent: $a \mid b$ and $b \mid a$ ; $b = ua$ for a unit $u$ ; $|a| = |b|$ . Being associates is an equivalence relation whose class of $a$ is $\{a, -a\}$ , $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ), that is $d = p$ or $d = -p$ . Both readings are used below without further comment.

Why $1$ is excluded, and it is not a matter of taste. The exclusion is forced by the uniqueness half of The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ , proved on this page: if $1$ counted as a prime, a factorisation could be padded with any number of factors $1$ , so lists of different lengths would represent the same integer and no permutation could match them. Existence of a factorisation would survive the change; it is uniqueness alone that fixes the convention, and the explicit witness is recorded on the companion page.

Remarks

The witness for the exclusion of $1$ . The companion page carries it explicitly: If $1$ were admitted as a prime, uniqueness would fail: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ , lists of different lengths that no permutation matches ↗ displays $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$ , three lists of lengths $2$ , $3$ and $4$ that no permutation can match.
No ring vocabulary is used here, deliberately. In a general commutative ring one distinguishes a prime element from an irreducible element, and in $\mathbb{Z}$ the two notions coincide; that dictionary needs the definition of a ring, which this library develops far above this page, so it is not stated here and nothing below depends on it. What is proved here is the arithmetic content of the coincidence: For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ shows that for $p > 1$ the definition above is equivalent to the property that $p \mid ab$ forces $p \mid a$ or $p \mid b$ .
Primality is about $p$ ; coprimality is about a pair. Coprime integers: $\gcd(a,b) = 1$ is the condition $\gcd(a,b) = 1$ on two integers and needs no primality at all — $4$ and $9$ are coprime and neither is prime. The bridge in the other direction is For a prime $p$ and any integer $a$ , $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime, the next item, and it is the only place on this page where primality is converted into coprimality.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

For a prime $p$ and any integer $a$ , $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and let $a \in \mathbb{Z}$ . Then

$\gcd(p,a) \;=\; \begin{cases} p & \text{if } p \mid a, \\ 1 & \text{if } p \nmid a, \end{cases}$

with $\gcd$ as in Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ and divisibility as in Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ . In particular, if $p \nmid a$ then $p$ and $a$ are coprime (Coprime integers: $\gcd(a,b) = 1$ ).

Facts & Assumptions

Given: A prime $p$ , an integer $a$ , and $g := \gcd(p,a)$ (Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L1]

$p > 1$ , and every positive divisor $d$ of $p$ satisfies $d = 1$ or $d = p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L2]

$g \ge 0$ , $g \mid p$ , $g \mid a$ , and every common divisor of $p$ and $a$ divides $g$ (Every common divisor of $a$ and $b$ divides $\gcd(a,b)$ ; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$ , $d \mid a$ , $d \mid b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well, Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L3]

$\gcd(u,v) \ge 1$ unless $u = v = 0$ , in which case $\gcd(u,v) = 0$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$ ; moreover $\gcd(a,0) = |a|$ , $\gcd(a,1) = 1$ , $\gcd(a,a) = |a|$ , and $\gcd(a,b) \ge 1$ unless $a = b = 0$ ).

[L4]

Divisibility is reflexive and transitive: $u \mid u$ for every $u$ , and $d \mid u$ with $u \mid v$ gives $d \mid v$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L5]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L6]

$u$ and $v$ are coprime exactly when $\gcd(u,v) = 1$ (Coprime integers: $\gcd(a,b) = 1$ ).

[L7]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \le y$ together with $x \ne y$ (The integers form a totally ordered ring, Order on the integers).

[L8]

The embedding $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ ; and $0 \ne 1$ in $\mathbb{N}$ (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann), The integers as equivalence classes of pairs of naturals).

[L9]

$\mathbb{Z}$ is a commutative ring: addition is associative and commutative, $x + 0 = x$ , and every $x$ has an additive inverse $-x$ , with $-(-x) = x$ ; we write $u - v$ for $u + (-v)$ (The integers form a commutative ring, Arithmetic on the integers).

Proof

technique · cases

1.1

$0 < 1$ in $\mathbb{Z}$ : $1 = \iota(1)$ lies in the image of $\iota$ , hence $1 \ge 0$ , and $1 \ne 0$ because $\iota$ is injective and $0 \ne 1$ in $\mathbb{N}$ .

L8

1.2

Suppose $p \mid a$ . Then $p$ is a common divisor of $p$ and $a$ , since $p \mid p$ , so $p \mid g$ .

assume-case divL2L4

2.1

$-1 < 0$ : adding $-1$ to both sides of $0 < 1$ preserves the order, giving $-1 < 0$ .

step 1.1L7L9

2.2

$p > 0$ and $p \ne 0$ , so $(p,a) \ne (0,0)$ ; consequently $g \ge 1$ , and in particular $g > 0$ .

step 1.1L1L3L7

3.1

$p \ne 1$ and $p \ne -1$ : the first because $p > 1$ , the second because $-1 < 0 < 1 < p$ and the order is transitive.

step 1.1step 2.1L1L7

3.2

$g$ is a positive divisor of $p$ , so $g = 1$ or $g = p$ .

step 2.2L1L2

4.1

In that case $g \ne 1$ : otherwise $p \mid 1$ , forcing $p = 1$ or $p = -1$ and contradicting step 3.1. So $g = p$ by step 3.2.

assume-case divstep 3.1step 3.2L5

4.2

Suppose instead $p \nmid a$ . Then $g \ne p$ , since $g \mid a$ and $g = p$ would give $p \mid a$ . So $g = 1$ by step 3.2, that is, $p$ and $a$ are coprime.

assume-case nodivstep 3.2L2L6

5.1

Either $p \mid a$ or $p \nmid a$ , and no third possibility exists, so the two cases above are exhaustive and give the stated value of $g$ in each.

step 4.1step 4.2cases-exhaustive∎

Remarks

This is the only place on this page where primality becomes coprimality. Every later appeal to Bézout's identity — Euclid's lemma (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ) first among them — runs through this lemma rather than through the definition of a prime, because the published If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ is stated for coprime integers and uses no primality at all.
The hypothesis that $p$ is prime is used twice, and both uses are essential: once for $p > 1$ , which puts $(p,a)$ outside the pair $(0,0)$ where the $\gcd$ convention lives and excludes $p$ from being a unit, and once for the divisor condition, which is what leaves only the two candidate values $1$ and $p$ . For a composite $p$ the conclusion fails: $\gcd(4,6) = 2$ , which is neither $4$ nor $1$ , while $4 \nmid 6$ .

TheoremStatement: Literature-sourcedProof: Literature-sourcedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and let $a, b \in \mathbb{Z}$ . If $p \mid ab$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ) then

$p \mid a \qquad \text{or} \qquad p \mid b .$

Facts & Assumptions

Given: A prime $p$ and integers $a, b$ with $p \mid ab$ .

[L1]

For a prime $p$ and any integer $u$ : if $p \nmid u$ then $\gcd(p,u) = 1$ (For a prime $p$ and any integer $a$ , $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime, Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L2]

If $\gcd(u,v) = 1$ and $u \mid vw$ then $u \mid w$ , for all integers $u, v, w$ (If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ ).

[L3]

$u$ and $v$ are coprime exactly when $\gcd(u,v) = 1$ (Coprime integers: $\gcd(a,b) = 1$ ).

[L4]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ ; divisibility is reflexive and transitive (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L5]

$\mathbb{Z}$ is a commutative ring; in particular multiplication is commutative and associative (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L6]

$p > 1$ , and every positive divisor of $p$ is $1$ or $p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

Proof

technique · cases

1.1

Suppose $p \mid a$ . Then the disjunction $p \mid a$ or $p \mid b$ holds on its first alternative, and there is nothing further to prove.

assume-case div

1.2

Suppose instead $p \nmid a$ . Then $\gcd(p,a) = 1$ , so $p$ and $a$ are coprime.

assume-case nodivL1L3L6

2.1

Apply [L2] with $u := p$ , $v := a$ and $w := b$ . Its two hypotheses are exactly $\gcd(p,a) = 1$ , which is step 1.2, and $p \mid ab$ , which is given; its conclusion is $p \mid b$ .

assume-case nodivstep 1.2L2L4L5

3.1

Either $p \mid a$ or $p \nmid a$ , so the two cases are exhaustive; in the first $p \mid a$ and in the second $p \mid b$ , which is the assertion.

step 1.1step 2.1cases-exhaustive∎

Remarks

This is a two-line consequence, and that is the point. The work was done one page earlier: If $\gcd(a,b) = 1$ and $a \mid bc$ then $a \mid c$ ; and if $a \mid c$ , $b \mid c$ and $\gcd(a,b) = 1$ then $ab \mid c$ proves that $\gcd(u,v) = 1$ together with $u \mid vw$ forces $u \mid w$ , and its own Remarks record that "no primality is used" in it — the proof is pure Bézout. The summary of the page carrying it says in as many words that "primes, Euclid's lemma and unique factorisation are not proved here; they belong to a later page". This is that page, and the only new ingredient is For a prime $p$ and any integer $a$ , $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime, which converts primality into the coprimality that lemma actually consumes.
The hypothesis cannot be weakened to $p > 1$ . For a composite modulus the conclusion fails, and the published witness is $6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$ : dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails: $6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$ . Its Remarks identify the failure as exactly the failure of coprimality, which is what primality supplies here.
The converse holds too. For $p > 1$ the property proved here characterises primality; that is For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ , next on this page.

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$

Statement

Let $p \in \mathbb{Z}$ with $p > 1$ . The following are equivalent:

$p$ is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ );
for all $a, b \in \mathbb{Z}$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

Facts & Assumptions

Given: An integer $p$ with $p > 1$ .

[L1]

$p$ is prime exactly when $p > 1$ and every positive divisor $d$ of $p$ satisfies $d = 1$ or $d = p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L2]

If $q$ is prime and $q \mid uv$ then $q \mid u$ or $q \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L3]

$u \mid v$ and $v \mid u$ together hold exactly when $|u| = |v|$ , and exactly when $v = wu$ for a unit $w \in \{1,-1\}$ (For integers $a$ and $b$ the following are equivalent: $a \mid b$ and $b \mid a$ ; $b = ua$ for a unit $u$ ; $|a| = |b|$ . Being associates is an equivalence relation whose class of $a$ is $\{a, -a\}$ , $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L4]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L5]

If $xz = yz$ and $z \ne 0$ then $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L6]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ ; divisibility is reflexive (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L7]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , and every $x$ has an additive inverse $-x$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L8]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \le y$ together with $x \ne y$ (The integers form a totally ordered ring, Order on the integers).

[L9]

The embedding $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ ; and $0 \ne 1$ in $\mathbb{N}$ (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

$|x| = x$ when $x \ge 0$ and $|x| = -x$ when $x < 0$ ; $|x| \ge 0$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ).

Proof

technique · direct

1.1

$0 < 1$ : $1 = \iota(1)$ lies in the image of $\iota$ , so $1 \ge 0$ , and $1 \ne 0$ because $\iota$ is injective and $0 \ne 1$ in $\mathbb{N}$ . Adding $-1$ throughout gives $-1 < 0$ .

L7L8L9

1.2

Claim 1 implies claim 2: if $p$ is prime this is exactly [L2].

L2

1.3

Assume claim 2, and let $d$ be a positive divisor of $p$ ; fix $c \in \mathbb{Z}$ with $p = dc$ .

L6choose

2.1

$p > 1 > 0$ , so $p > 0$ and $p \ne 0$ .

step 1.1L8

2.2

Then $p \mid dc$ , since $p \mid p$ and $p = dc$ ; so claim 2 applied with $a := d$ and $b := c$ gives $p \mid d$ or $p \mid c$ .

step 1.3L6

3.1

Suppose $p \mid d$ . Since also $d \mid p$ , [L3] gives $|d| = |p|$ , hence $d = wp$ for a unit $w \in \{1,-1\}$ . If $w = -1$ then $d = -p < 0$ , contradicting $d > 0$ ; so $w = 1$ and $d = p$ .

step 2.1step 1.3step 2.2L3L7L8L10

3.2

Suppose instead $p \mid c$ , and fix $e$ with $c = pe$ . Then $1 \cdot p = p = dc = d(pe) = (de) \cdot p$ , and $p \ne 0$ , so cancellation gives $de = 1$ . Hence $d \mid 1$ , so $d = 1$ or $d = -1$ , and $d > 0 > -1$ leaves $d = 1$ .

step 1.1step 2.1step 1.3step 2.2L4L5L6L7L8

4.1

By step 2.2 one of the two cases occurs, so every positive divisor $d$ of $p$ satisfies $d = 1$ or $d = p$ ; together with the standing hypothesis $p > 1$ this says $p$ is prime, so claim 2 implies claim 1.

step 2.2step 3.1step 3.2L1

5.1

The two implications of steps 1.2 and 4.1 give the equivalence.

step 1.2step 4.1∎

Remarks

Both directions need $p > 1$ , and it is a standing hypothesis rather than part of either claim. Claim 2 alone does not force primality: $p = 1$ satisfies it vacuously, since $1 \mid a$ for every $a$ , and so does $p = 0$ , because $0 \mid ab$ forces $ab = 0$ and hence $a = 0$ or $b = 0$ (The integers have no zero divisors; multiplicative cancellation). Neither is prime, and the clause $p > 1$ of Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ is what excludes them.
The two halves of the equivalence are the two notions a general theory keeps apart. Claim 1 says $p$ cannot be split into smaller positive factors; claim 2 says $p$ , when it divides a product, already divides a factor. In $\mathbb{Z}$ they coincide, and that coincidence is what makes unique factorisation work; the counterexample In the multiplicative monoid $H = \{1, 4, 7, 10, \dots\}$ of positive integers one more than a multiple of $3$ , the element $100$ has two genuinely different factorisations into irreducibles, $4 \cdot 25$ and $10 \cdot 10$ ↗ on the companion page shows what fails in a setting where the analogue of claim 1 holds and the analogue of claim 2 does not.

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

If a prime $p$ divides a finite product $\prod_{i<n} a_i$ of integers then $p \mid a_i$ for some $i < n$ ; at $n = 0$ the product is $1$ and the hypothesis cannot hold

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ), let $n \in \mathbb{N}$ , and let $a : \mathbb{N} \to \mathbb{Z}$ , with the finite product $\prod_{i<n} a_i$ taken in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ as in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity. If

$p \;\Big|\; \prod_{i<n} a_i ,$

then $p \mid a_i$ for some $i < n$ .

At $n = 0$ the product is the empty product $1$ , and $p \mid 1$ is impossible for a prime, so the hypothesis is never satisfied there and the assertion is true rather than excluded. Since $\prod_{i<n} a_i$ depends only on $a_0, \dots, a_{n-1}$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity), the statement applies verbatim to a finite list $a : n \to \mathbb{Z}$ .

Facts & Assumptions

Given: A prime $p$ ; the property $P(n)$ : "for every family $a : \mathbb{N} \to \mathbb{Z}$ , if $p \mid \prod_{i<n} a_i$ then $p \mid a_i$ for some $i < n$ ".

[L1]

$(\mathbb{Z},\cdot,1)$ is a commutative monoid, and $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid).

[L2]

In a monoid, $\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(n)} g_i = \bigl(\prod_{i<n} g_i\bigr) \cdot g_n$ ; the value depends only on $g_0, \dots, g_{n-1}$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L3]

If $q$ is prime and $q \mid uv$ then $q \mid u$ or $q \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L4]

$p > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L5]

Induction: a property holding at $0$ and inherited by successors holds at every natural number (The principle of mathematical induction).

[L6]

On $\mathbb{N}$ : $n < \sigma(n)$ , and $m < \sigma(n)$ exactly when $m \le n$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ , The natural numbers $\mathbb{N}$ (von Neumann)).

[L7]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers); $\mathbb{Z}$ is a commutative ring (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L8]

The embedding $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ ; and $0 \ne 1$ in $\mathbb{N}$ (The naturals embed in the integers).

[L9]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

Proof

technique · induction

1.1

$0 < 1$ , since $1 = \iota(1)$ is nonnegative and $1 \ne 0$ by injectivity of $\iota$ ; adding $-1$ gives $-1 < 0$ . Hence $-1 < 0 < 1 < p$ , so $p \ne 1$ and $p \ne -1$ .

L4L7L8

1.2

Let $n \in \mathbb{N}$ and assume $P(n)$ .

ih

1.3

Let $a : \mathbb{N} \to \mathbb{Z}$ and suppose $p \mid \prod_{i<\sigma(n)} a_i$ . By the recursion clause this product equals $\bigl(\prod_{i<n} a_i\bigr) \cdot a_n$ , so [L3] gives $p \mid \prod_{i<n} a_i$ or $p \mid a_n$ .

L1L2L3L9

2.1

$P(0)$ holds: $\prod_{i<0} a_i = 1$ for every family $a$ , and $p \mid 1$ would force $p = 1$ or $p = -1$ , which step 1.1 excludes. So the hypothesis of $P(0)$ is never satisfied and $P(0)$ is true vacuously.

basestep 1.1L1L2

2.2

In the first case step 1.2 supplies $i < n$ with $p \mid a_i$ , and $i < n < \sigma(n)$ gives $i < \sigma(n)$ ; in the second case $i := n$ works, since $n < \sigma(n)$ . Either way some $i < \sigma(n)$ has $p \mid a_i$ , so $P(\sigma(n))$ holds.

step 1.2step 1.3L6

3.1

$P(0)$ holds and $P(n)$ implies $P(\sigma(n))$ for every $n$ , so $P(n)$ holds for every $n \in \mathbb{N}$ .

step 2.1step 2.2L5discharge-induction∎

Remarks

The case $n = 0$ is real and is not an exception. The empty product is $1$ by The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, and a prime never divides $1$ , so the implication holds with a false hypothesis. Stating the corollary from $n = 1$ upwards would be a weaker theorem for no gain, and would have to be repaired at every use.
No commutativity is used. The proof consumes only the recursion clause $\prod_{i<\sigma(n)} a_i = \bigl(\prod_{i<n} a_i\bigr) a_n$ and Euclid's lemma; the monoid is named commutative only because $(\mathbb{Z},\cdot,1)$ is, and because later items on this page do use commutativity.
A prime dividing a product of primes equals one of them. If every $a_i$ is prime and $p \mid \prod_{i<n} a_i$ , then $p \mid a_k$ for some $k$ , and then $p$ is a positive divisor of the prime $a_k$ other than $1$ , so $p = a_k$ by Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ . That one-line consequence is the engine of the uniqueness half of The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime

Statement

Let $n \in \mathbb{Z}$ with $n > 1$ , and put

$S \;:=\; \{\, d \in \mathbb{Z} \;:\; d \mid n \ \text{ and } \ d > 1 \,\}$

(Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ). Then $S$ is nonempty and has a least element $q$ , and $q$ is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ). In particular every integer greater than $1$ has a prime divisor.

Facts & Assumptions

Given: An integer $n$ with $n > 1$ , and the set $S$ above.

[L2]

Divisibility is reflexive and transitive (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L3]

A nonempty set of integers with a lower bound has a unique least element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element).

[L4]

If $d \mid u$ and $u \ne 0$ then $d \ne 0$ and $|d| \le |u|$ (If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$ ; hence the set of divisors of a nonzero integer is bounded above by $|a|$ ).

[L5]

$p$ is prime exactly when $p > 1$ and every positive divisor of $p$ is $1$ or $p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L6]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \le y$ together with $x \ne y$ (The integers form a totally ordered ring, Order on the integers).

[L8]

The embedding $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves addition and order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ (The naturals embed in the integers).

[L9]

On $\mathbb{N}$ : $0 \le k$ for every $k$ , since $0 + k = k$ (Order on the natural numbers); $m < k$ exactly when $\sigma(m) \le k$ (Discreteness: $\sigma(n)$ is the immediate successor); and $1 = \sigma(0)$ (The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

$|x| = x$ when $x \ge 0$ and $|x| = -x$ when $x < 0$ ; $|x| \ge 0$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ).

Proof

technique · direct

1.1

$0 < 1$ in $\mathbb{Z}$ : $1 = \iota(1)$ lies in the image of $\iota$ , so $1 \ge 0$ , and $1 \ne 0$ because $\iota$ is injective and $\iota(0) = 0$ .

L8

1.2

Discreteness: if $x \in \mathbb{Z}$ and $0 < x$ then $1 \le x$ . Indeed $x \ge 0$ , so $x = \iota(k)$ for some $k \in \mathbb{N}$ ; $k \ne 0$ since $\iota(0) = 0 \ne x$ ; hence $0 < k$ in $\mathbb{N}$ , so $1 = \sigma(0) \le k$ , and applying the order-preserving $\iota$ gives $1 = \iota(1) \le \iota(k) = x$ .

L8L9

1.3

$n \in S$ , since $n \mid n$ and $n > 1$ ; so $S$ is nonempty.

L2

1.4

$1$ is a lower bound for $S$ : every $d \in S$ satisfies $d > 1$ , hence $1 \le d$ .

L6

2.1

By [L3] the set $S$ has a unique least element $q$ : that is, $q \mid n$ , $q > 1$ , and $q \le d$ for every $d \in S$ .

step 1.3step 1.4L3

3.1

$n > 1 > 0$ and $q > 1 > 0$ , so $n \ne 0$ and $q \ne 0$ , and $|q| = q$ .

step 1.1step 2.1L6L10

3.2

Let $e$ be a positive divisor of $q$ with $e \ne 1$ . Then $1 \le e$ by step 1.2, and $e \ne 1$ , so $e > 1$ .

step 1.2step 2.1L6

4.1

Also $e \mid q$ and $q \mid n$ , so $e \mid n$ by transitivity; with $e > 1$ this gives $e \in S$ , hence $q \le e$ .

step 2.1step 3.2L2

5.1

On the other hand $e \mid q$ with $q \ne 0$ gives $|e| \le |q| = q$ , and $|e| = e$ because $e > 0$ ; so $e \le q$ . With step 4.1 and antisymmetry, $e = q$ .

step 3.1step 3.2step 4.1L4L6L10

6.1

So every positive divisor of $q$ is $1$ or $q$ , and $q > 1$ : $q$ is prime. Since $q \mid n$ , the integer $n$ has a prime divisor.

step 2.1step 3.2step 5.1L5∎

Remarks

Well-ordering is used through the integer bridge, not directly. The well-ordering principle gives a least element of a nonempty subset of $\mathbb{N}$ , whereas $S$ is a set of integers. A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element is the published lemma that crosses that gap, and its Statement covers the lower-bound case explicitly, so it is what this proof cites.
The bound $q$ is genuinely the least divisor above $1$ , not merely some prime divisor. That is what makes the argument work: minimality is the only reason $q$ has no proper divisor above $1$ , since any such divisor would divide $n$ as well and be smaller.
The hypothesis $n > 1$ cannot be dropped. At $n = 1$ the set $S$ is empty, since $d \mid 1$ forces $d = 1$ or $d = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ) and neither exceeds $1$ ; so $1$ has no prime divisor, which is exactly why the empty product is the right factorisation of $1$ in Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product. At $n = 0$ every integer divides $0$ , so $S$ is the whole set of integers greater than $1$ ; it does have a least element, namely $2$ , but a statement about the divisors of $0$ is of no use below and the lemma is not claimed there.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product

Statement

Write finite products in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , as in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity; a list of primes of length $r$ means a function $p : r \to \mathbb{Z}$ on the von Neumann natural $r = \{0,\dots,r-1\}$ with every $p_i$ prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

Existence. For every $n \in \mathbb{Z}$ with $n \ge 1$ there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with

$n \;=\; \prod_{i<r} p_i .$

At $n = 1$ this holds with $r = 0$ : the empty product is $1$ , so $1$ is a product of primes, of no primes at all, and needs no separate clause.
Every such product is at least $1$ . Conversely, for every $r \in \mathbb{N}$ and every list $p : r \to \mathbb{Z}$ of primes, $\prod_{i<r} p_i \ge 1$ . So the integers of clause 1 are exactly the values of finite products of primes.

Facts & Assumptions

Given: The commutative monoid $(\mathbb{Z},\cdot,1)$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid); the embedding $\iota : \mathbb{N} \to \mathbb{Z}$ of The naturals embed in the integers; and the property $P(k)$ : "if $\iota(k) \ge 1$ then $\iota(k) = \prod_{i<r} p_i$ for some $r \in \mathbb{N}$ and some list $p : r \to \mathbb{Z}$ of primes".

[L1]

$\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(r)} g_i = \bigl(\prod_{i<r} g_i\bigr) \cdot g_r$ ; the value depends only on $g_0,\dots,g_{r-1}$ , so a list $u : r \to M$ determines $\prod_{i<r} u_i$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L2]

Every integer $n > 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime, Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L3]

Strong induction: if for every $k$ the truth of $P$ below $k$ implies $P(k)$ , then $P$ holds everywhere on $\mathbb{N}$ (Strong (complete) induction).

[L4]

Induction: a subset of $\mathbb{N}$ containing $0$ and closed under $\sigma$ is $\mathbb{N}$ (The principle of mathematical induction).

[L5]

$\iota$ is injective, preserves addition, multiplication and order, and its image is exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ (The naturals embed in the integers, The integers as equivalence classes of pairs of naturals).

[L6]

Every prime satisfies $p > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L7]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication (The integers form a totally ordered ring, Order on the integers).

[L8]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot 0 = 0$ , multiplication distributes over addition, and every $x$ has an additive inverse $-x$ , with $-(-x) = x$ and $(-x)y = -(xy)$ ; we write $u - v$ for $u + (-v)$ (The integers form a commutative ring, Arithmetic on the integers).

[L9]

On $\mathbb{N}$ : $0 \le k$ for every $k$ (Order on the natural numbers); $m < k$ exactly when $\sigma(m) \le k$ (Discreteness: $\sigma(n)$ is the immediate successor); $1 = \sigma(0)$ (The natural numbers $\mathbb{N}$ (von Neumann)); and $r < \sigma(r)$ , with $i < \sigma(r)$ exactly when $i \le r$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ).

[L10]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

Proof

technique · induction

1.1

$0 < 1$ in $\mathbb{Z}$ : $1 = \iota(1)$ lies in the image of $\iota$ , so $1 \ge 0$ , and $1 \ne 0$ because $\iota$ is injective and $\iota(0) = 0$ .

L5

1.2

Discreteness: if $x \in \mathbb{Z}$ and $0 < x$ then $1 \le x$ . Indeed $x \ge 0$ , so $x = \iota(k)$ for some $k$ ; $k \ne 0$ since $\iota(0) = 0 \ne x$ ; so $0 < k$ in $\mathbb{N}$ , hence $1 = \sigma(0) \le k$ , and applying the order-preserving $\iota$ gives $1 \le x$ .

L5L9

1.3

Let $k \in \mathbb{N}$ and assume $P(j)$ for every $j < k$ .

ih

2.1

Clause 2. Let $T$ be the set of $r \in \mathbb{N}$ such that $\prod_{i<r} p_i \ge 1$ for every list $p : r \to \mathbb{Z}$ of primes. Then $0 \in T$ , the empty product being $1$ . If $r \in T$ and $p : \sigma(r) \to \mathbb{Z}$ is a list of primes, then $\prod_{i<\sigma(r)} p_i = \bigl(\prod_{i<r} p_i\bigr) p_r$ , where the restriction of $p$ to $r$ is again a list of primes, so the first factor is $\ge 1 > 0$ ; and $p_r > 1 > 0$ ; positives being closed under multiplication the product is $> 0$ , hence $\ge 1$ by step 1.2. So $\sigma(r) \in T$ , and $T = \mathbb{N}$ .

step 1.1step 1.2L1L4L6L7

2.2

$P(0)$ holds vacuously: $\iota(0) = 0$ and $0 \ge 1$ is false, since $0 < 1$ .

basestep 1.1L5

2.3

Suppose $\iota(k) \ge 1$ and write $n := \iota(k)$ ; by totality either $n = 1$ or $n > 1$ . If $n = 1$ , take $r := 0$ : the empty list is a list of primes and $\prod_{i<0} p_i = 1 = n$ , so $P(k)$ holds.

step 1.1L1L7

3.1

Suppose instead $n > 1$ . Fix a prime $q$ with $q \mid n$ and an integer $m$ with $n = qm$ .

step 2.3L2L10choose

4.1

$m > 0$ : $m = 0$ would give $n = q \cdot 0 = 0 < 1$ , and $m < 0$ would give $-m > 0$ , hence $q(-m) > 0$ , that is $-n > 0$ and $n < 0 < 1$ ; both contradict $n \ge 1$ . So $m > 0$ and therefore $m \ge 1$ by step 1.2.

step 1.1step 1.2step 3.1L7L8

5.1

$m < n$ : since $q > 1$ we have $q - 1 > 0$ , and $m > 0$ , so $(q-1)m > 0$ ; and $(q-1)m = qm - m = n - m$ , whence $n - m > 0$ and $m < n$ .

step 3.1step 4.1L6L7L8

6.1

As $m \ge 1 > 0$ , write $m = \iota(j)$ with $j \in \mathbb{N}$ . Then $j < k$ : otherwise $k \le j$ , and $\iota$ preserving the order would give $n = \iota(k) \le \iota(j) = m$ , contradicting step 5.1.

step 4.1step 5.1L5L7

7.1

By step 1.3 applied to $j$ there are $s \in \mathbb{N}$ and a list $p : s \to \mathbb{Z}$ of primes with $m = \prod_{i<s} p_i$ .

step 1.3step 4.1step 6.1

8.1

Define $p' : \sigma(s) \to \mathbb{Z}$ by $p'_i := p_i$ for $i < s$ and $p'_s := q$ ; every value is prime, and $\prod_{i<\sigma(s)} p'_i = \bigl(\prod_{i<s} p'_i\bigr) \cdot p'_s = m q = q m = n$ , the middle equality because the product over $i < s$ depends only on $p'_0,\dots,p'_{s-1}$ , which agree with $p$ . So $P(k)$ holds with $r := \sigma(s)$ .

step 3.1step 7.1L1L8L9

9.1

Steps 2.3 and 8.1 cover the two possibilities for $n$ , so $P(k)$ follows from the truth of $P$ below $k$ ; with step 2.2 as the case $k = 0$ , strong induction gives $P(k)$ for every $k \in \mathbb{N}$ .

step 2.2step 2.3step 8.1L3

10.1

Finally, any $n \ge 1$ satisfies $n > 0$ , so $n = \iota(k)$ for some $k \in \mathbb{N}$ , and $P(k)$ is clause 1 for that $n$ ; clause 2 is step 2.1.

step 1.1step 2.1step 9.1L5L7discharge-induction∎

Remarks

$1$ is a product of primes here, and this is not a dodge. The empty product is the identity of the monoid by The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, so $r = 0$ gives the value $1$ exactly. Excluding $n = 1$ and starting at $n \ge 2$ would force a special case into every later statement, including The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ , whose uniqueness clause at $r = 0$ is precisely the assertion that only the empty list represents $1$ .
Uniqueness is a separate theorem and is not proved here. Existence needs only a least prime divisor and a descent; uniqueness needs Euclid's lemma. In the multiplicative monoid $H = \{1, 4, 7, 10, \dots\}$ of positive integers one more than a multiple of $3$ , the element $100$ has two genuinely different factorisations into irreducibles, $4 \cdot 25$ and $10 \cdot 10$ ↗ on the companion page exhibits a setting where the existence half holds and the uniqueness half fails, which is what shows the two halves are genuinely independent.
The list is appended to, not prepended to. The successor clause of The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity multiplies on the right, so putting the new prime $q$ at position $s$ costs nothing, whereas putting it at position $0$ would need the splitting law of Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either. Order is irrelevant to the value, by the commutative clause of that theorem, so nothing is lost.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$

Statement

Finite products are taken in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ as in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, and a list of primes of length $r$ is a function $p : r \to \mathbb{Z}$ on the von Neumann natural $r = \{0,\dots,r-1\}$ with every $p_i$ prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

Existence. Every $n \in \mathbb{Z}$ with $n \ge 1$ is $\prod_{i<r} p_i$ for some $r \in \mathbb{N}$ and some list $p$ of primes of length $r$ (Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product).
Uniqueness up to order. Let $p$ and $q$ be lists of primes, of lengths $r$ and $s$ . If

$\prod_{i<r} p_i \;=\; \prod_{j<s} q_j ,$

then $r = s$ , and there is a permutation $\pi \in \operatorname{Sym}(r)$ (The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition) with

$q_i \;=\; p_{\pi(i)} \qquad \text{for every } i < r .$

At $r = 0$ clause 2 says that the only list of primes whose product is $1$ is the empty list, and the permutation condition is vacuous.

Facts & Assumptions

Given: The commutative monoid $(\mathbb{Z},\cdot,1)$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid); and the property $U(r)$ : "for every $s \in \mathbb{N}$ and all lists $p$ , $q$ of primes of lengths $r$ and $s$ with $\prod_{i<r} p_i = \prod_{j<s} q_j$ , one has $r = s$ and $q_i = p_{\pi(i)}$ for all $i < r$ , for some $\pi \in \operatorname{Sym}(r)$ ".

[L1]

$\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(r)} g_i = \bigl(\prod_{i<r} g_i\bigr) \cdot g_r$ ; the value depends only on $g_0,\dots,g_{r-1}$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L2]

Commutative case of generalised associativity: for a commutative monoid, $n \in \mathbb{N}$ , $\pi \in \operatorname{Sym}(n)$ and $h$ with $h_i = g_{\pi(i)}$ for $i < n$ , one has $\prod_{i<n} h_i = \prod_{i<n} g_i$ (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).

[L3]

If a prime $u$ divides $\prod_{j<s} q_j$ then $u \mid q_k$ for some $k < s$ (If a prime $p$ divides a finite product $\prod_{i<n} a_i$ of integers then $p \mid a_i$ for some $i < n$ ; at $n = 0$ the product is $1$ and the hypothesis cannot hold, Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L4]

Every prime $u$ satisfies $u > 1$ , and every positive divisor of a prime $w$ is $1$ or $w$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L5]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ); $d \mid v$ means $v = dc$ for some $c$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L6]

If $xz = yz$ and $z \ne 0$ then $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L7]

$\operatorname{Sym}(X)$ is the set of bijections $X \to X$ under composition, with identity $\mathrm{id}_X$ ; it is closed under composition, and for $a \ne b$ in $X$ the transposition $(a\,b)$ is a permutation of $X$ with $(a\,b) \circ (a\,b) = \mathrm{id}_X$ (The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition, $\operatorname{Sym}(X)$ is a group under composition, and it is non-abelian whenever $X$ has at least three distinct elements, Injection, surjection, bijection).

[L8]

Induction on $\mathbb{N}$ (The principle of mathematical induction).

[L9]

On $\mathbb{N}$ : $n = \{\, m : m < n \,\}$ , $\sigma(n) = n \cup \{n\}$ , $n < \sigma(n)$ , $m < \sigma(n)$ exactly when $m \le n$ , and $n \notin n$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ , The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

Every natural number other than $0$ is a successor (Every nonzero natural number is a successor).

[L11]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $\mathbb{Z}$ is a commutative ring (The integers form a totally ordered ring, Order on the integers, The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L12]

$\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image the nonnegative integers, with $\iota(0) = 0$ , $\iota(1) = 1$ (The naturals embed in the integers).

Proof

technique · induction

1.1

$0 < 1$ : $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ by injectivity of $\iota$ . Hence every prime $u$ satisfies $u > 1 > 0$ , so $u \ne 0$ , $u \ne 1$ and, adding $-1$ to $0 < 1$ , also $u \ne -1$ .

L4L11L12

1.2

If $q$ is a list of primes of length $s \ne 0$ then $q_t \mid \prod_{j<s} q_j$ , where $s = \sigma(t)$ : indeed the product equals $\bigl(\prod_{j<t} q_j\bigr) q_t$ .

L1L5L10

1.3

Let $r \in \mathbb{N}$ and assume $U(r)$ .

ih

1.4

Let $p$ be a list of primes of length $\sigma(r)$ and $q$ one of length $s$ , with $N := \prod_{i<\sigma(r)} p_i = \prod_{j<s} q_j$ . Then $N = \bigl(\prod_{i<r} p_i\bigr) p_r$ , so $p_r \mid N$ .

L1L5

2.1

A prime never divides $1$ : $u \mid 1$ would force $u = 1$ or $u = -1$ , both excluded by step 1.1.

step 1.1L5

2.2

By [L3] there is $k < s$ with $p_r \mid q_k$ . Since $p_r > 1 > 0$ , $p_r$ is a positive divisor of the prime $q_k$ other than $1$ , so $p_r = q_k$ .

step 1.1step 1.4L3L4

3.1

$U(0)$ holds. Let $q$ be a list of primes of length $s$ with $\prod_{i<0} p_i = \prod_{j<s} q_j$ , so $\prod_{j<s} q_j = 1$ . If $s \ne 0$ , then $s = \sigma(t)$ and step 1.2 gives $q_t \mid 1$ , contradicting step 2.1; so $s = 0$ . Then $r = s = 0$ , $\mathrm{id}_{\varnothing} \in \operatorname{Sym}(0)$ since $0 = \varnothing$ , and the condition " $q_i = p_{\pi(i)}$ for all $i < 0$ " is vacuous.

basestep 2.1step 1.2L1L7L9

3.2

$s \ne 0$ : otherwise $N = 1$ and $p_r \mid 1$ , contradicting step 2.1. Write $s = \sigma(t)$ .

step 2.1step 1.4L1L10

4.1

Define $\tau \in \operatorname{Sym}(s)$ by $\tau := \mathrm{id}_s$ if $k = t$ and $\tau := (k\,t)$ otherwise; in both cases $\tau$ is a permutation of $s$ with $\tau \circ \tau = \mathrm{id}_s$ and $\tau(t) = k$ . Note $t < s$ and $k < s$ , so both lie in $s$ .

step 3.2step 2.2L7L9construct

5.1

Put $q'_j := q_{\tau(j)}$ for $j < s$ ; every $q'_j$ is prime, and $\prod_{j<s} q'_j = \prod_{j<s} q_j = N$ by the commutative clause [L2], the monoid $(\mathbb{Z},\cdot,1)$ being commutative.

step 4.1L2

6.1

Also $q'_t = q_{\tau(t)} = q_k = p_r$ , so $N = \prod_{j<\sigma(t)} q'_j = \bigl(\prod_{j<t} q'_j\bigr) q'_t = \bigl(\prod_{j<t} q'_j\bigr) p_r$ .

step 2.2step 4.1step 5.1L1

7.1

Comparing with step 1.4, $\bigl(\prod_{i<r} p_i\bigr) p_r = \bigl(\prod_{j<t} q'_j\bigr) p_r$ , and $p_r \ne 0$ by step 1.1, so cancellation gives $\prod_{i<r} p_i = \prod_{j<t} q'_j$ .

step 1.1step 1.4step 6.1L6

8.1

The restrictions of $p$ to $r$ and of $q'$ to $t$ are lists of primes of lengths $r$ and $t$ , and their products are the two sides of step 7.1, since a finite product depends only on the entries it names. So $U(r)$ applies: $r = t$ , hence $s = \sigma(t) = \sigma(r)$ , and there is $\rho \in \operatorname{Sym}(r)$ with $q'_i = p_{\rho(i)}$ for every $i < r$ .

step 1.3step 7.1L1

9.1

Define $\hat\rho : \sigma(r) \to \sigma(r)$ by $\hat\rho(i) := \rho(i)$ for $i < r$ and $\hat\rho(r) := r$ . Since $\sigma(r) = r \cup \{r\}$ with $r \notin r$ , and $\rho$ is a bijection of $r$ , the map $\hat\rho$ is a bijection of $\sigma(r)$ , that is $\hat\rho \in \operatorname{Sym}(\sigma(r))$ .

step 8.1L7L9construct

10.1

Put $\pi := \hat\rho \circ \tau$ , a permutation of $s = \sigma(r)$ because $\operatorname{Sym}(\sigma(r))$ is closed under composition.

step 4.1step 8.1step 9.1L7

11.1

For $i < \sigma(r)$ we get $q_i = q_{\tau(\tau(i))} = q'_{\tau(i)}$ . If $\tau(i) < r$ then $q'_{\tau(i)} = p_{\rho(\tau(i))} = p_{\hat\rho(\tau(i))} = p_{\pi(i)}$ ; and if $\tau(i) = r = t$ then $q'_{\tau(i)} = q'_t = p_r = p_{\hat\rho(r)} = p_{\pi(i)}$ . Since $\tau(i) < \sigma(r)$ these two possibilities are exhaustive, so $q_i = p_{\pi(i)}$ throughout.

step 4.1step 6.1step 8.1step 9.1step 10.1L9

12.1

Steps 8.1 and 11.1 give $s = \sigma(r)$ and a permutation $\pi \in \operatorname{Sym}(\sigma(r))$ with $q_i = p_{\pi(i)}$ for all $i < \sigma(r)$ , so $U(\sigma(r))$ holds; with step 3.1 as base, induction gives $U(r)$ for every $r \in \mathbb{N}$ , which is clause 2. Clause 1 is Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product.

step 3.1step 8.1step 11.1L8discharge-induction∎

Remarks

"Unique up to order" is spelt out, not gestured at. The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition is available at this point in the library, so the uniqueness clause names a permutation $\pi$ of the von Neumann natural $r$ and asserts an equality for every index, rather than saying the two factorisations "agree up to rearrangement". The letter $\pi$ is used because $\sigma$ is already the successor function on $\mathbb{N}$ throughout this library.
The theorem is stated for $n \ge 1$ . It is not stated for $n \ge 2$ , which would exclude the empty product and gain nothing, and it is not stated for all nonzero $n$ , which is false as it stands because a negative integer is not a product of primes. The signed form is Every nonzero integer $n$ is $u \prod_{i<r} p_i$ with $u \in \{1,-1\}$ and every $p_i$ prime; $u$ and $r$ are determined by $n$ , and the list is determined up to a permutation, where the sign is carried by a unit.
Where each hypothesis is used. Primality of $p_r$ lets If a prime $p$ divides a finite product $\prod_{i<n} a_i$ of integers then $p \mid a_i$ for some $i < n$ ; at $n = 0$ the product is $1$ and the hypothesis cannot hold supply the index $k$ , and also makes $p_r$ a nonzero factor different from $1$ . Primality of the selected $q_k$ is then used separately in step 2.2: the positive divisor $p_r\mid q_k$ , being different from $1$ , must equal $q_k$ . Drop Euclid's lemma and the argument collapses before that comparison — In the multiplicative monoid $H = \{1, 4, 7, 10, \dots\}$ of positive integers one more than a multiple of $3$ , the element $100$ has two genuinely different factorisations into irreducibles, $4 \cdot 25$ and $10 \cdot 10$ ↗ is the witness.
Reading the theorem by exponents. Collecting equal primes turns clause 2 into For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list, which records the multiplicity of each prime as its $p$ -adic valuation. That is the same theorem in different notation, not a further result.

CorollaryStatement: Literature-sourcedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

Every nonzero integer $n$ is $u \prod_{i<r} p_i$ with $u \in \{1,-1\}$ and every $p_i$ prime; $u$ and $r$ are determined by $n$ , and the list is determined up to a permutation

Statement

Let $n \in \mathbb{Z}$ with $n \ne 0$ , and take finite products in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , as in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity.

Existence. There are $u \in \{1,-1\}$ , $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) with

$n \;=\; u \prod_{i<r} p_i .$
Uniqueness. If also $n = u' \prod_{j<s} q_j$ with $u' \in \{1,-1\}$ and $q : s \to \mathbb{Z}$ a list of primes, then $u = u'$ , $r = s$ , and $q_i = p_{\pi(i)}$ for every $i < r$ , for some $\pi \in \operatorname{Sym}(r)$ (The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition).

Facts & Assumptions

Given: A nonzero integer $n$ .

[L1]

Every integer $m \ge 1$ is $\prod_{i<r} p_i$ for some $r \in \mathbb{N}$ and some list $p : r \to \mathbb{Z}$ of primes; and conversely every such product is $\ge 1$ (Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product, The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid).

[L2]

If $\prod_{i<r} p_i = \prod_{j<s} q_j$ for lists of primes, then $r = s$ and $q_i = p_{\pi(i)}$ for all $i < r$ , for some $\pi \in \operatorname{Sym}(r)$ (The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ , The symmetric group $\operatorname{Sym}(X)$ : the bijections of a set $X$ under composition).

[L3]

$|x| = x$ when $x \ge 0$ and $|x| = -x$ when $x < 0$ (The absolute value $|a|$ of an integer); $|x| \ge 0$ , $|x| = 0$ exactly when $x = 0$ , and $|xy| = |x|\,|y|$ (Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ).

[L4]

If $xz = yz$ and $z \ne 0$ then $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L5]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , $x \cdot (-1) = -x$ , and every $x$ has an additive inverse, with $-(-x) = x$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L6]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers).

[L7]

$\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ (The naturals embed in the integers).

[L8]

On $\mathbb{N}$ : $0 \le k$ for every $k$ (Order on the natural numbers); $m < k$ exactly when $\sigma(m) \le k$ (Discreteness: $\sigma(n)$ is the immediate successor); $1 = \sigma(0)$ (The natural numbers $\mathbb{N}$ (von Neumann)).

Proof

technique · direct

1.1

$0 < 1$ , since $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ by injectivity; and if $0 < x$ then $1 \le x$ , because $x = \iota(k)$ with $k \ne 0$ , so $1 = \sigma(0) \le k$ and $\iota$ preserves the order.

L7L8

2.1

$|n| \ge 0$ and $|n| \ne 0$ , so $|n| > 0$ and hence $|n| \ge 1$ .

step 1.1L3L6

2.2

For uniqueness, suppose $n = u P = u' P'$ where $P := \prod_{i<r} p_i$ and $P' := \prod_{j<s} q_j$ and $u, u' \in \{1,-1\}$ . By [L1] both $P \ge 1$ and $P' \ge 1$ , so both are positive and $|P| = P$ , $|P'| = P'$ .

step 1.1L1L3L6

3.1

By [L1] there are $r \in \mathbb{N}$ and a list $p$ of primes of length $r$ with $|n| = \prod_{i<r} p_i$ .

step 2.1L1choose

3.2

Taking absolute values, $|n| = |u|\,|P| = P$ and likewise $|n| = |u'|\,|P'| = P'$ , since $|1| = 1$ and $|-1| = 1$ . Hence $P = P'$ .

step 2.2L3L5

4.1

The order is total and $n \ne 0$ , so $n > 0$ or $n < 0$ . If $n > 0$ then $|n| = n$ and $n = 1 \cdot \prod_{i<r} p_i$ ; if $n < 0$ then $|n| = -n$ , so $n = -(-n) = -|n| = (-1) \prod_{i<r} p_i$ . In both cases clause 1 holds, with $u = 1$ and $u = -1$ respectively.

step 3.1L3L5L6

4.2

By [L2] applied to $P = P'$ we get $r = s$ and a permutation $\pi \in \operatorname{Sym}(r)$ with $q_i = p_{\pi(i)}$ for every $i < r$ .

step 3.2L2

4.3

And $u P = u' P$ with $P \ne 0$ , since $P \ge 1 > 0$ ; cancellation gives $u = u'$ .

step 2.2step 3.2L4L6

5.1

Clause 1 is step 4.1 and clause 2 is steps 4.2 and 4.3.

step 4.1step 4.2step 4.3∎

Remarks

This is why Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ can insist on $p > 1$ without loss. The sign of $n$ is carried by the unit $u$ , not by the primes, so admitting negative primes would buy nothing and would break uniqueness, since $(-2)(-3)$ and $2 \cdot 3$ would be different lists with the same product.
The uniqueness of $u$ needs $P \ne 0$ , and that is why the empty product is harmless. At $r = 0$ the statement reads $n = u$ , so the nonzero integers with an empty prime list are exactly $1$ and $-1$ — which is $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ again, from a different direction.
Nothing is claimed at $n = 0$ . Zero is divisible by every prime and is not a product of primes times a unit at all, since every such product is $1$ or $-1$ times a positive integer. It is excluded by hypothesis, not overlooked.

TheoremStatement: AI-adaptedProof: AI-adaptedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

Euclid's theorem: for every $n \in \mathbb{N}$ and every list $p : n \to \mathbb{Z}$ of primes there is a prime not among $p_0, \dots, p_{n-1}$ ; consequently the set of primes is not finite

Statement

Write $P := \{\, x \in \mathbb{Z} : x \text{ is prime} \,\}$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ), and take finite products in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ as in The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity.

For every $n \in \mathbb{N}$ and every list $p : n \to \mathbb{Z}$ of primes there is a prime $q$ with $q \ne p_i$ for every $i < n$ .
Consequently $P$ is not finite: there is no $m \in \mathbb{N}$ with $P \approx m$ (Finite, countably infinite, countable, uncountable, Equinumerous sets, $A \approx B$ and $A \preceq B$ ).

Clause 1 holds at $n = 0$ as well, where the empty product is $1$ and the witness produced by the proof is a prime divisor of $2$ .

Facts & Assumptions

Given: The set $P$ of primes.

[L1]

$\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(n)} g_i = \bigl(\prod_{i<n} g_i\bigr) \cdot g_n$ ; the value depends only on $g_0,\dots,g_{n-1}$ (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid).

[L2]

Splitting law: $\prod_{i<m+k} g_i = \bigl(\prod_{i<m} g_i\bigr) \cdot \bigl(\prod_{l<k} g_{m+l}\bigr)$ for all $m, k \in \mathbb{N}$ (Generalised associativity: in a monoid the product of a finite list does not depend on the bracketing, and in a commutative monoid it does not depend on the order of the factors either).

[L3]

Every finite product of primes is $\ge 1$ (Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product).

[L4]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime).

[L5]

Every prime satisfies $u > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L6]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L7]

Divisibility is reflexive and transitive, and is linear: $d \mid a$ and $d \mid b$ give $d \mid ax + by$ , in particular $d \mid a - b$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L8]

$\mathbb{Z}$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , $x \cdot 1 = x$ , and every $x$ has an additive inverse (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L9]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers); $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, preserves the order, and has as image the nonnegative integers, with $\iota(0) = 0$ , $\iota(1) = 1$ (The naturals embed in the integers, The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

On $\mathbb{N}$ : $j < n$ exactly when $\sigma(j) \le n$ (Discreteness: $\sigma(n)$ is the immediate successor); $a \le b$ means $a + c = b$ for some $c \in \mathbb{N}$ (Order on the natural numbers, Addition of natural numbers); and $n = \{\, m : m < n \,\}$ with $j < \sigma(j)$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ).

[L11]

A function is injective when it identifies no two points, surjective when its image is the whole codomain, and bijective when it is both (Injection, surjection, bijection); $A \approx B$ means a bijection $A \to B$ exists, and $A$ is finite when $A \approx m$ for some $m \in \mathbb{N}$ (Equinumerous sets, $A \approx B$ and $A \preceq B$ , Finite, countably infinite, countable, uncountable).

Proof

technique · contradiction

1.1

$0 < 1$ in $\mathbb{Z}$ , since $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ by injectivity of $\iota$ ; adding $1$ gives $1 < 1 + 1$ .

L9

1.2

Fix $n \in \mathbb{N}$ and a list $p : n \to \mathbb{Z}$ of primes, and put $\Pi := \prod_{i<n} p_i$ and $N := \Pi + 1$ .

L1choose

1.3

Suppose, for contradiction, that $P$ is finite: fix $m \in \mathbb{N}$ and a bijection $g : P \to m$ .

assume-contraL11choose

2.1

$\Pi \ge 1$ by [L3], so $N = \Pi + 1 \ge 1 + 1 > 1$ by compatibility of the order with addition.

step 1.1step 1.2L3L9

2.2

Suppose, for contradiction, that $q = p_j$ for some $j < n$ . Since $j < n$ we have $\sigma(j) \le n$ , so $n = \sigma(j) + c$ for some $c \in \mathbb{N}$ .

assume-contrastep 1.2L10

2.3

Define $f : m \to \mathbb{Z}$ by letting $f(i)$ be the unique $x \in P$ with $g(x) = i$ ; such an $x$ exists because $g$ is surjective and is unique because $g$ is injective. Then $f$ is a list of primes of length $m$ , and $f(g(x)) = x$ for every $x \in P$ .

step 1.3L11construct

3.1

By [L4] there is a prime $q$ with $q \mid N$ .

step 2.1L4choose

3.2

The splitting law then gives $\Pi = \bigl(\prod_{i<\sigma(j)} p_i\bigr) \cdot \bigl(\prod_{l<c} p_{\sigma(j)+l}\bigr)$ , and $\prod_{i<\sigma(j)} p_i = \bigl(\prod_{i<j} p_i\bigr) p_j$ ; by associativity and commutativity $\Pi = p_j \cdot B$ where $B := \bigl(\prod_{i<j} p_i\bigr)\bigl(\prod_{l<c} p_{\sigma(j)+l}\bigr)$ . Hence $p_j \mid \Pi$ , that is $q \mid \Pi$ .

step 2.2L1L2L7L8

4.1

So $q \mid N$ and $q \mid \Pi$ , whence $q \mid N - \Pi = 1$ by linearity, forcing $q = 1$ or $q = -1$ and contradicting $q > 1 > 0 > -1$ . Therefore $q \ne p_i$ for every $i < n$ , which is clause 1.

step 1.1step 1.2step 3.1step 3.2L5L6L7L8L9

5.1

Clause 1 applied to $f$ supplies a prime $q_0$ with $q_0 \ne f(i)$ for every $i < m$ . But $q_0 \in P$ , so $g(q_0) < m$ and $f(g(q_0)) = q_0$ , a contradiction. Hence no such $m$ and $g$ exist and $P$ is not finite, which is clause 2.

step 4.1step 1.3step 2.3L10L11discharge-contradiction∎

Remarks

The theorem does not say $N$ is prime, and reading it that way is a common slip. What is proved is that $N = p_0 \cdots p_{n-1} + 1$ has a prime divisor, and that this divisor is not on the list. The false reading is refuted on the companion page by FALSE: for every finite list $p_0, \dots, p_{n-1}$ of distinct primes, $p_0 \cdots p_{n-1} + 1$ is prime ↗, where $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$ .
Clause 1 is the constructive statement and clause 2 is a consequence of it. Clause 1 says nothing about infinite sets and needs no notion of cardinality; it just extends any finite list. Clause 2 turns that into "not finite" in the sense of Finite, countably infinite, countable, uncountable, and the only input it needs is that a bijection $P \to m$ produces a list enumerating every prime.
This is not a statement about where the primes are. Arbitrarily long runs of composite integers exist (For every $n \in \mathbb{N}$ there are $n$ consecutive composite integers: with $N := \prod_{j<n}(j+2)$ , each of $N+2, \dots, N+n+1$ is composite ↗), so the gaps between consecutive primes are unbounded; the two facts are compatible and neither weakens the other.

DefinitionDefinition: AI-adaptedProof: Not applicablejudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$

Definition

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and let $a \in \mathbb{Z}$ with $a \ne 0$ . Powers $p^{k}$ for $k \in \mathbb{N}$ are the natural powers of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ taken in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ and Semigroup and monoid, so that

$p^{0} = 1, \qquad p^{\sigma(k)} = p^{k} \cdot p \quad (k \in \mathbb{N}).$

Put

$E(p,a) \;:=\; \{\, k \in \mathbb{N} \;:\; p^{k} \mid a \,\}$

(Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ). Then $E(p,a)$ has a greatest element, and the $p$ -adic valuation of $a$ is

$v_p(a) \;:=\; \max E(p,a) \;\in\; \mathbb{N},$

the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ .

Why a greatest element exists. Three facts are needed, and each is proved here rather than assumed.

The set is nonempty. $p^{0} = 1$ and $1 \mid a$ for every $a$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ), so $0 \in E(p,a)$ .

Every power of $p$ exceeds its own exponent. We claim $p^{k} \ge 1$ and $\iota(k) < p^{k}$ for every $k \in \mathbb{N}$ , where $\iota : \mathbb{N} \to \mathbb{Z}$ is the embedding of The naturals embed in the integers. Both are proved by induction (The principle of mathematical induction). At $k = 0$ we have $p^{0} = 1 \ge 1$ and $\iota(0) = 0 < 1 = p^{0}$ , using $0 < 1$ , which holds because $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ by injectivity of $\iota$ . Assume both at $k$ . Since $p > 1$ we have $p - 1 > 0$ , hence $p - 1 \ge 1$ by discreteness of the order on $\mathbb{Z}$ (Discreteness: $\sigma(n)$ is the immediate successor, The naturals embed in the integers: an integer $x > 0$ is $\iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ and $1 \le x$ ). Therefore $p^{\sigma(k)} - p^{k} = p^{k}(p-1) \ge p^{k} \ge 1$ , because $p^{k} \ge 1 > 0$ and positives are closed under multiplication (The integers form a totally ordered ring); so $p^{\sigma(k)} \ge p^{k} + 1 \ge 1 + 1 > 1$ . The same discreteness applied to $p^{k} - \iota(k) > 0$ gives $\iota(k) + 1 \le p^{k}$ , and $\iota(\sigma(k)) = \iota(k) + 1$ because $\sigma(k) = k + 1$ in $\mathbb{N}$ (Addition of natural numbers) and $\iota$ preserves addition; so $\iota(\sigma(k)) \le p^{k} < p^{k} + 1 \le p^{\sigma(k)}$ . The induction is complete.

The set is bounded. Let $k \in E(p,a)$ . Then $p^{k} \mid a$ with $a \ne 0$ , so $|p^{k}| \le |a|$ (If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$ ; hence the set of divisors of a nonzero integer is bounded above by $|a|$ ); and $p^{k} \ge 1 > 0$ gives $|p^{k}| = p^{k}$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ). Combining with the previous paragraph, $\iota(k) < p^{k} \le |a|$ . So the set of integers $\iota[E(p,a)] = \{\, \iota(k) : k \in E(p,a) \,\}$ is nonempty and bounded above by $|a|$ , hence has a unique greatest element (A nonempty set of integers bounded above has a greatest element, and a nonempty set of integers bounded below has a least element). That greatest element lies in the set, so it is $\iota(k_0)$ for some $k_0 \in E(p,a)$ ; and since $\iota$ is injective and preserves the order in both directions, $k_0$ is the greatest element of $E(p,a)$ and is unique. We set $v_p(a) := k_0$ .

$v_p(0)$ is left undefined. Every power of $p$ divides $0$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ), so $E(p,0) = \mathbb{N}$ has no greatest element and the clause above defines nothing. Every statement about $v_p$ in this library therefore carries the hypothesis $a \ne 0$ explicitly. The convention $v_p(0) := \infty$ is not adopted: it would need a value set enlarging $\mathbb{N}$ by a greatest element in which to place $\infty$ , and no such set is available at this point in the reading order. The library does build a totally ordered set with a greatest element — the extended real line, whose greatest element is $+\infty$ — but it is constructed far above this page, and taking the values of $v_p$ there would make a definition about $\mathbb{Z}$ rest on the construction of $\mathbb{R}$ .

Remarks

$v_p(a)$ is a natural number, not an integer. It is a von Neumann natural (The natural numbers $\mathbb{N}$ (von Neumann)), which is exactly what the exponent slot of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ takes, so $p^{v_p(a)}$ is meaningful without any translation. Where a valuation has to be subtracted from another, as in The $p$ -adic valuation extends to the nonzero rationals by $v_p(a/b) := v_p(a) - v_p(b) \in \mathbb{Z}$ , independently of the representation; it satisfies $v_p(xy) = v_p(x) + v_p(y)$ , and $v_p(x+y) \ge \min\{v_p(x), v_p(y)\}$ whenever $x$ , $y$ and $x+y$ are nonzero, the values are first carried into $\mathbb{Z}$ along $\iota$ (The naturals embed in the integers).
These are monoid powers, and deliberately not Integer powers $a^m$ . That definition is stated for an element of the ambient ordered field $\mathbb{R}$ ; using it here would make a statement about $\mathbb{Z}$ rest on the whole construction of the real numbers for no gain. The two agree along the embeddings $\mathbb{Z} \to \mathbb{Q} \to \mathbb{R}$ , since both are defined by the same recursion $x^{0} = 1$ , $x^{\sigma(k)} = x^{k} x$ and the embeddings preserve products and the constant $1$ ; nothing on this page depends on that observation, and it is recorded here only so the reader does not think a second notion of power has been introduced.
The definition is by a maximum, and For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ converts it into the form later proofs use: $p^{v_p(a)} \mid a$ , $p^{v_p(a)+1} \nmid a$ , and $a = p^{v_p(a)} a'$ with $p \nmid a'$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ), let $a \in \mathbb{Z}$ with $a \ne 0$ , and write $v := v_p(a)$ (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ). Powers are the natural powers of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ in the commutative monoid $(\mathbb{Z},\cdot,1)$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ), and $k + 1$ means $\sigma(k)$ . Then:

$p^{k} \ge 1$ for every $k \in \mathbb{N}$ ; in particular $p^{k} > 0$ and $p^{k} \ne 0$ ;
$p^{v} \mid a$ and $p^{v+1} \nmid a$ ;
for $k \in \mathbb{N}$ : $p^{k} \mid a$ if and only if $k \le v$ ;
$a = p^{v} a'$ for some $a' \in \mathbb{Z}$ with $a' \ne 0$ and $p \nmid a'$ ;
$v \ge 1$ if and only if $p \mid a$ ;
$v_p(1) = v_p(-1) = 0$ and $v_p(p) = 1$ .

Facts & Assumptions

Given: A prime $p$ , a nonzero integer $a$ , and $v := v_p(a)$ .

[L1]

$v_p(a)$ is the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ; in particular $p^{v} \mid a$ , and $p^{k} \mid a$ fails for every $k > v$ (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

[L2]

$p^{0} = 1$ and $p^{\sigma(k)} = p^{k} \cdot p$ (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Semigroup and monoid, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L3]

Exponent law in a monoid, for natural exponents: $g^{m+n} = g^{m} g^{n}$ (Exponent laws in a group: $g^{m+n} = g^{m}g^{n}$ and $(g^{m})^{n} = g^{mn}$ for all $m, n \in \mathbb{Z}$ , and $(gh)^{n} = g^{n}h^{n}$ when $g$ and $h$ commute).

[L4]

Divisibility is reflexive and transitive; $d \mid u$ implies $d \mid uc$ ; and $d \mid u$ , $d \mid -u$ , $-d \mid u$ are equivalent (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L5]

$d \mid u$ means $u = dc$ for some $c \in \mathbb{Z}$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L6]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L7]

Every prime satisfies $p > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L8]

If $xz = yz$ and $z \ne 0$ then $x = y$ ; and a product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

[L9]

On $\mathbb{N}$ : $m \le n$ means $m + c = n$ for some $c$ (Order on the natural numbers); $\sigma(k) = k + 1$ (Addition of natural numbers, The natural numbers $\mathbb{N}$ (von Neumann)); $k < \sigma(k)$ and $m < \sigma(n)$ exactly when $m \le n$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ); $m < n$ exactly when $\sigma(m) \le n$ (Discreteness: $\sigma(n)$ is the immediate successor); and $\le$ is a linear order, so it is antisymmetric and total ( $\le$ is a linear order on $\mathbb{N}$ ).

[L10]

$\mathbb{Z}$ is a commutative ring, its order is total, antisymmetric and transitive and compatible with addition, and $\iota : \mathbb{N} \to \mathbb{Z}$ is injective, order preserving, with image the nonnegative integers and $\iota(0) = 0$ , $\iota(1) = 1$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers, The naturals embed in the integers).

[L11]

Induction on $\mathbb{N}$ : a subset containing $0$ and closed under $\sigma$ is all of $\mathbb{N}$ (The principle of mathematical induction).

Proof

technique · direct

1.1

$p^{1} = p^{\sigma(0)} = p^{0} \cdot p = 1 \cdot p = p$ .

L2L10

1.2

$0 < 1 < p$ in $\mathbb{Z}$ , since $1 = \iota(1)$ is nonnegative and differs from $0$ ; hence $p \ne 0$ , $p \ne 1$ and $p \ne -1$ .

L7L10

1.3

Clause 1. $p^{v} \mid a$ by [L1], and $v < \sigma(v) = v + 1$ , so $p^{v+1} \mid a$ would contradict the maximality of $v$ ; hence $p^{v+1} \nmid a$ .

L1L9

1.4

Clause 2, the other direction. If $p^{k} \mid a$ then $k$ belongs to the set of which $v$ is the greatest element, so $k \le v$ .

L1L9

2.1

Clause 0: $p^{k} \ge 1$ for every $k \in \mathbb{N}$ . The set of such $k$ contains $0$ , since $p^{0} = 1$ ; and if $p^{k} \ge 1$ then $p^{\sigma(k)} = p^{k} p$ has both factors $\ge 1 > 0$ , so the product is positive, hence $\ge 1$ by discreteness of the order on $\mathbb{Z}$ (a positive integer is $\iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ and $1 \le \iota(j)$ ). By induction the set is all of $\mathbb{N}$ , and in particular $p^{k} > 0$ and $p^{k} \ne 0$ .

step 1.1step 1.2L2L9L10L11

2.2

Clause 2, one direction. Let $k \le v$ and write $v = k + c$ with $c \in \mathbb{N}$ . Then $p^{v} = p^{k+c} = p^{k} p^{c}$ , so $p^{k} \mid p^{v}$ ; with $p^{v} \mid a$ and transitivity, $p^{k} \mid a$ .

step 1.3L1L3L4L5L9

2.3

Clause 3. By [L1] fix $a'$ with $a = p^{v} a'$ . Then $a' \ne 0$ , since $a \ne 0$ . If $p \mid a'$ , say $a' = pb$ , then $a = p^{v}(pb) = (p^{v} p) b = p^{v+1} b$ , so $p^{v+1} \mid a$ , contradicting step 1.3. Hence $p \nmid a'$ .

step 1.3L1L2L5L9L10choose

2.4

If $k \ge 1$ then $p \mid p^{k}$ : write $k = 1 + c$ , so $p^{k} = p^{1} p^{c} = p \cdot p^{c}$ .

step 1.1L3L5L9

3.1

Clause 4. If $v \ge 1$ then $p = p^{1} \mid a$ by step 2.2. Conversely if $p \mid a$ then $p^{1} \mid a$ , so $1 \le v$ by step 1.4.

step 1.1step 2.2step 1.4

3.2

$v_p(1) = 0$ . If $p^{k} \mid 1$ with $k \ge 1$ , then $p \mid p^{k} \mid 1$ by step 2.4 and transitivity, so $p = 1$ or $p = -1$ , contradicting step 1.2. So no $k \ge 1$ satisfies $p^{k} \mid 1$ , while $p^{0} = 1 \mid 1$ ; the greatest such $k$ is $0$ .

step 1.2step 2.4L1L2L4L6L9

3.3

$v_p(p) = 1$ . First $p^{1} = p \mid p$ , so $1 \le v_p(p)$ by step 1.4 applied to $a := p$ . Next $p^{2} \nmid p$ , where $2 = \sigma(1)$ : otherwise $p = p^{2}c = p(pc)$ for some $c$ , and cancelling $p \ne 0$ gives $1 = pc$ , so $p \mid 1$ , contradicting step 1.2. Hence $v_p(p) < 2$ by step 2.2, that is $v_p(p) \le 1$ , and antisymmetry gives $v_p(p) = 1$ .

step 1.1step 1.2step 2.2step 1.4L2L5L8L9

4.1

$v_p(-1) = 0$ , because $p^{k} \mid -1$ holds exactly when $p^{k} \mid 1$ , so the two sets of exponents coincide.

step 3.2L1L4

5.1

Clauses 0 to 5 are established.

step 1.3step 2.1step 2.2step 1.4step 2.3step 3.1step 3.2step 4.1step 3.3∎

Remarks

Clause 3 is the working form. Every later proof on this page writes a nonzero integer as $a = p^{v_p(a)} a'$ with $p \nmid a'$ and then argues about $a'$ ; that is how $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero gets additivity, and it is where Euclid's lemma enters.
The hypothesis $a \ne 0$ is carried everywhere because $v_p(0)$ is not defined: every power of $p$ divides $0$ , so there is no greatest exponent (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).
Clause 2 says the exponents form an initial segment, which is what makes "the greatest $k$ with $p^{k} \mid a$ " the same as "the number of times $p$ divides $a$ ". Without it the maximum could in principle skip values.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

$v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and let $a, b \in \mathbb{Z}$ be nonzero, with $v_p$ as in The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ . Then $ab \ne 0$ and

$v_p(ab) \;=\; v_p(a) + v_p(b),$

the sum taken in $\mathbb{N}$ (Addition of natural numbers). If moreover $a + b \ne 0$ , then

$v_p(a+b) \;\ge\; \min\{\, v_p(a),\, v_p(b) \,\},$

the minimum of two natural numbers, which exists because the order on $\mathbb{N}$ is total ( $\le$ is a linear order on $\mathbb{N}$ ).

Facts & Assumptions

Given: A prime $p$ and nonzero integers $a, b$ ; $\alpha := v_p(a)$ and $\beta := v_p(b)$ .

[L1]

For a nonzero $u$ : $p^{v_p(u)} \mid u$ , and $u = p^{v_p(u)} u'$ for some nonzero $u'$ with $p \nmid u'$ ; moreover $p^{k} \mid u$ holds exactly for $k \le v_p(u)$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ , The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

[L2]

Exponent law in a monoid for natural exponents: $g^{m+n} = g^{m} g^{n}$ (Exponent laws in a group: $g^{m+n} = g^{m}g^{n}$ and $(g^{m})^{n} = g^{mn}$ for all $m, n \in \mathbb{Z}$ , and $(gh)^{n} = g^{n}h^{n}$ when $g$ and $h$ commute, Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Semigroup and monoid, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L3]

If $p$ is prime and $p \mid uv$ then $p \mid u$ or $p \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L4]

Divisibility is linear: $d \mid u$ and $d \mid v$ give $d \mid ux + vy$ , in particular $d \mid u + v$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ); $d \mid u$ means $u = dc$ for some $c$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L5]

A product of two nonzero integers is nonzero, and $xz = yz$ with $z \ne 0$ gives $x = y$ (The integers have no zero divisors; multiplicative cancellation).

[L6]

$\mathbb{Z}$ is a commutative ring: multiplication is associative and commutative and $x \cdot 1 = x$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals); its order is total, antisymmetric and transitive (The integers form a totally ordered ring, Order on the integers, The naturals embed in the integers).

[L7]

On $\mathbb{N}$ : $\le$ is a linear order, so any two naturals are comparable and have a minimum ( $\le$ is a linear order on $\mathbb{N}$ ); $m \le n$ means $m + c = n$ for some $c$ (Order on the natural numbers); $\sigma(k) = k + 1$ (Addition of natural numbers, The natural numbers $\mathbb{N}$ (von Neumann)); $m < n$ exactly when $\sigma(m) \le n$ (Discreteness: $\sigma(n)$ is the immediate successor), and $m < \sigma(n)$ exactly when $m \le n$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ).

Proof

technique · direct

1.1

$ab \ne 0$ , so $v_p(ab)$ is defined.

L5

1.2

Fix $a'$ and $b'$ with $a = p^{\alpha} a'$ , $b = p^{\beta} b'$ , both nonzero, and $p \nmid a'$ , $p \nmid b'$ .

L1choose

1.3

Now assume also $a + b \ne 0$ , and put $m := \min\{\alpha,\beta\}$ , which exists because $\le$ is total on $\mathbb{N}$ ; then $m \le \alpha$ and $m \le \beta$ .

L7

2.1

$ab = (p^{\alpha} a')(p^{\beta} b') = (p^{\alpha} p^{\beta})(a' b') = p^{\alpha+\beta}(a'b')$ , using commutativity, associativity and the exponent law.

step 1.2L2L6

2.2

$p \nmid a'b'$ : otherwise [L3] would give $p \mid a'$ or $p \mid b'$ , both excluded by step 1.2.

step 1.2L3

2.3

By [L1], $p^{m} \mid a$ and $p^{m} \mid b$ , so $p^{m} \mid a + b$ by linearity; since $a + b \ne 0$ , [L1] applied to $a+b$ gives $m \le v_p(a+b)$ , which is the second assertion.

step 1.3L1L4

3.1

$p^{\alpha+\beta} \ne 0$ , since $ab \ne 0$ and $ab = p^{\alpha+\beta}(a'b')$ would otherwise be $0$ .

step 1.1step 2.1L6

3.2

$p^{\alpha+\beta} \mid ab$ by step 2.1, so $\alpha + \beta \le v_p(ab)$ .

step 1.1step 2.1L1L4

4.1

Suppose $\alpha + \beta < v_p(ab)$ . Then $\alpha + \beta + 1 \le v_p(ab)$ , so $p^{\alpha+\beta+1} \mid ab$ ; fix $c$ with $ab = p^{\alpha+\beta+1}c = p^{\alpha+\beta}(pc)$ , using the exponent law. Cancelling $p^{\alpha+\beta} \ne 0$ against step 2.1 gives $a'b' = pc$ , that is $p \mid a'b'$ , contradicting step 2.2.

step 2.1step 2.2step 3.1L1L2L4L5L7

5.1

Hence $v_p(ab) = \alpha + \beta$ by totality and antisymmetry of the order on $\mathbb{N}$ , which is the first assertion.

step 3.2step 4.1L7

6.1

Both assertions are established.

step 5.1step 2.3∎

Remarks

Primality is used exactly once, at step 2.2, and it is used through Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ . That is the whole reason the additivity of $v_p$ is a theorem about primes and not about arbitrary integers greater than $1$ : for a composite base the analogue fails, and the companion page of the divisibility page already carries the failure of the product principle ( $6 \mid 4 \cdot 9$ while $6 \nmid 4$ and $6 \nmid 9$ : dividing a product does not force dividing a factor, and the coprimality hypothesis is what fails).
The second clause is an inequality and cannot be an equality. Take $p = 2$ , $a = 2$ , $b = 2$ : then $v_2(a) = v_2(b) = 1$ while $v_2(a+b) = v_2(4) = 2$ . The companion page's worked example computes such valuations explicitly ( $360 = 2^{3} \cdot 3^{2} \cdot 5$ and $84 = 2^{2} \cdot 3 \cdot 7$ , with $\gcd(360,84) = 12$ and $\operatorname{lcm}(360,84) = 2520$ read off the exponents ↗).
The minimum is taken in $\mathbb{N}$ , through $\le$ is a linear order on $\mathbb{N}$ , not through the library's Maximum and minimum of a set, which is stated for real numbers. The values of $v_p$ are natural numbers, so no passage to $\mathbb{R}$ is needed or wanted here.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list

Statement

Powers are the natural powers of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ and finite products those of The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, both taken in the commutative monoid $(\mathbb{Z},\cdot,1)$ of $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ . Call $p : r \to \mathbb{Z}$ an injective list of primes when every $p_i$ is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) and $p_i = p_j$ forces $i = j$ (Injection, surjection, bijection).

Let $n \in \mathbb{Z}$ with $n \ge 1$ and let $p : r \to \mathbb{Z}$ be an injective list of primes such that every prime divisor of $n$ equals $p_i$ for some $i < r$ . Then, with $v_q$ as in The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ :

$\displaystyle n \;=\; \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ;
$v_q(n) = 0$ for every prime $q$ that is not among $p_0,\dots,p_{r-1}$ ;
the exponents are determined by $n$ : if $e : r \to \mathbb{N}$ and $n = \prod_{i<r} p_i^{\,e_i}$ , then $e_j = v_{p_j}(n)$ for every $j < r$ .

Clause 3 needs only injectivity of the list, not the covering hypothesis.

Facts & Assumptions

Given: The commutative monoid $(\mathbb{Z},\cdot,1)$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ , Semigroup and monoid); and the property $Q(r)$ : "for every $n \ge 1$ and every injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ".

[L1]

$\prod_{i<0} g_i = e$ and $\prod_{i<\sigma(t)} g_i = \bigl(\prod_{i<t} g_i\bigr) g_t$ ; the value depends only on the entries named (The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L2]

$g^{0} = e$ and $g^{\sigma(k)} = g^{k} g$ ; and $g^{m+n} = g^{m} g^{n}$ for natural exponents in a monoid (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Exponent laws in a group: $g^{m+n} = g^{m}g^{n}$ and $(g^{m})^{n} = g^{mn}$ for all $m, n \in \mathbb{Z}$ , and $(gh)^{n} = g^{n}h^{n}$ when $g$ and $h$ commute).

[L3]

For a prime $p$ and nonzero $a$ : $p^{k} \ge 1$ for every $k$ , so $p^{k} > 0$ and $p^{k} \ne 0$ ; $a = p^{v_p(a)} a'$ with $a' \ne 0$ and $p \nmid a'$ ; $p^{k} \mid a$ exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = 0$ ; and $v_p(p) = 1$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ , The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

[L4]

For a prime $p$ and nonzero $a, b$ : $ab \ne 0$ and $v_p(ab) = v_p(a) + v_p(b)$ ( $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero).

[L5]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime); every prime $u$ satisfies $u > 1$ , and every positive divisor of a prime $w$ is $1$ or $w$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L6]

Divisibility is reflexive and transitive; $d \mid u$ means $u = dc$ for some $c$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L7]

Induction on $\mathbb{N}$ (The principle of mathematical induction).

[L8]

On $\mathbb{N}$ : $m \le n$ means $m + c = n$ for some $c$ (Order on the natural numbers); $\sigma(k) = k+1$ and addition is commutative (Addition of natural numbers, Addition is commutative, The natural numbers $\mathbb{N}$ (von Neumann)); $t < \sigma(t)$ and $i < \sigma(t)$ exactly when $i \le t$ (On $\mathbb{N}$ the order is membership: $m < n \iff m \in n$ ); $m < n$ exactly when $\sigma(m) \le n$ (Discreteness: $\sigma(n)$ is the immediate successor).

[L9]

$\mathbb{Z}$ is a commutative ring; its order is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication; $\iota : \mathbb{N} \to \mathbb{Z}$ is injective and order preserving with image the nonnegative integers, $\iota(0) = 0$ , $\iota(1) = 1$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers, The naturals embed in the integers).

Proof

technique · induction

1.1

Distinct primes do not divide one another: if $q$ and $w$ are primes with $q \mid w$ , then $q$ is a positive divisor of $w$ (as $q > 1 > 0$ ) other than $1$ , so $q = w$ . Consequently $v_q(w) = 0$ whenever $q \ne w$ are primes.

L3L5L9

1.2

$Q(0)$ holds: an empty list contains no prime, so $n$ has no prime divisor at all; if $n > 1$ it would have one, so $n = 1$ , and $\prod_{i<0} p_i^{\,v_{p_i}(n)} = 1 = n$ .

baseL1L5L9

1.3

Let $t \in \mathbb{N}$ and assume $Q(t)$ .

ih

1.4

Let $n \ge 1$ and let $p : \sigma(t) \to \mathbb{Z}$ be an injective list of primes containing every prime divisor of $n$ . Write $\pi := p_t$ , $v := v_{\pi}(n)$ , and fix $n'$ with $n = \pi^{v} n'$ , $n' \ne 0$ and $\pi \nmid n'$ .

L3choose

2.1

For a prime $w$ and $k \in \mathbb{N}$ : $v_w(w^{k}) = k$ , and $v_q(w^{k}) = 0$ for every prime $q \ne w$ . Both sets of $k$ for which these hold contain $0$ , since $w^{0} = 1$ and $v_u(1) = 0$ for every prime $u$ ; and if they hold at $k$ then, $w^{k}$ and $w$ being nonzero, additivity gives $v_w(w^{\sigma(k)}) = v_w(w^{k} w) = v_w(w^{k}) + v_w(w) = k + 1 = \sigma(k)$ and $v_q(w^{\sigma(k)}) = v_q(w^{k}) + v_q(w) = 0 + 0 = 0$ . Induction finishes both.

step 1.1L2L3L4L7L8

2.2

$n' \ge 1$ : $\pi^{v} \ge 1 > 0$ and $n > 0$ , so $n' \le 0$ would make $\pi^{v} n' \le 0 < n$ ; hence $n' > 0$ , and a positive integer is $\ge 1$ because $n' = \iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ .

step 1.4L3L8L9

3.1

Clause 3. Let $p : r \to \mathbb{Z}$ be an injective list of primes, $e : r \to \mathbb{N}$ , and $M := \prod_{i<r} p_i^{\,e_i}$ ; we claim $M \ge 1$ , that $v_{p_j}(M) = e_j$ for every $j < r$ , and that $v_q(M) = 0$ for every prime $q$ off the list. Let $T$ be the set of $r \in \mathbb{N}$ for which this holds for all such $p$ and $e$ . Then $0 \in T$ : the empty product is $1$ , which is $\ge 1$ , has $v_q(1) = 0$ for every prime $q$ , and imposes no condition on indices. Suppose $r \in T$ and let $p : \sigma(r) \to \mathbb{Z}$ be injective with primes and $e : \sigma(r) \to \mathbb{N}$ . Writing $M' := \prod_{i<r} p_i^{\,e_i}$ we have $M = M' \cdot p_r^{\,e_r}$ , with $M' \ge 1 > 0$ and $p_r^{\,e_r} \ge 1 > 0$ , so $M \ge 1 > 0$ and both factors are nonzero; additivity then gives $v_u(M) = v_u(M') + v_u(p_r^{\,e_r})$ for every prime $u$ . Taking $u = p_j$ with $j < r$ gives $e_j + 0 = e_j$ , since $p_j \ne p_r$ by injectivity; taking $u = p_r$ gives $0 + e_r = e_r$ , since $p_r$ is off the list $p_0,\dots,p_{r-1}$ ; and taking a prime $u$ off the whole list gives $0 + 0 = 0$ . So $\sigma(r) \in T$ , and $T = \mathbb{N}$ by induction.

step 2.1L1L3L4L7L8L9

3.2

The restriction $p \restriction t$ is an injective list of primes containing every prime divisor of $n'$ . Indeed if $q$ is prime with $q \mid n'$ then $q \mid n$ , since $n = \pi^{v} n'$ ; so $q = p_i$ for some $i < \sigma(t)$ ; and $q \ne \pi = p_t$ , because $\pi \nmid n'$ ; hence $i \ne t$ , and $i < \sigma(t)$ gives $i \le t$ , so $i < t$ .

step 1.4step 2.2L5L6L8

3.3

For $i < t$ we have $v_{p_i}(n) = v_{p_i}(\pi^{v}) + v_{p_i}(n') = 0 + v_{p_i}(n') = v_{p_i}(n')$ , using additivity on the nonzero factors $\pi^{v}$ and $n'$ , and step 2.1 with $p_i \ne \pi$ , which holds by injectivity since $i < t$ .

step 2.1step 1.4step 2.2L3L4L8

4.1

By step 1.3 applied to $n'$ and $p \restriction t$ : $n' = \prod_{i<t} p_i^{\,v_{p_i}(n')}$ .

step 1.3step 2.2step 3.2

5.1

Therefore $\prod_{i<\sigma(t)} p_i^{\,v_{p_i}(n)} = \bigl(\prod_{i<t} p_i^{\,v_{p_i}(n)}\bigr) \cdot \pi^{\,v_{\pi}(n)} = \bigl(\prod_{i<t} p_i^{\,v_{p_i}(n')}\bigr) \cdot \pi^{v} = n' \pi^{v} = n$ , so $Q(\sigma(t))$ holds.

step 1.4step 4.1step 3.3L1L9

6.1

With step 1.2 as base, induction gives $Q(r)$ for every $r \in \mathbb{N}$ , which is clause 1. Clause 2 follows because a prime $q$ off the list does not divide $n$ — otherwise it would be a prime divisor of $n$ and hence on the list — so $v_q(n) = 0$ ; and clause 3 is step 3.1.

step 3.1step 1.2step 5.1L3L7discharge-induction∎

Remarks

This is The fundamental theorem of arithmetic: every integer $n \ge 1$ is a product of primes, and the factorisation is unique up to order — if $\prod_{i<r} p_i = \prod_{j<s} q_j$ with every $p_i$ and $q_j$ prime, then $r = s$ and $q_i = p_{\pi(i)}$ for some $\pi \in \operatorname{Sym}(r)$ read by exponents rather than by lists, not a further theorem. A list of primes with repetitions becomes an injective list with multiplicities, and the multiplicity of $p_i$ is exactly $v_{p_i}(n)$ ; uniqueness up to a permutation becomes clause 3, that the exponent vector is determined.
There is deliberately no product over all primes. The familiar notation $\prod_p p^{v_p(n)}$ abbreviates a product with finitely many factors different from $1$ , and an indexed product with finite support is not available at this point in the library — The product $g_0 g_1 \cdots g_{n-1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity multiplies a finite list. The honest form quantifies over a finite injective list covering the prime divisors of $n$ and adds clause 2, which says every prime off the list contributes exponent $0$ . Nothing is lost: any two such lists agree on the exponents by clause 3.
Why injectivity is a hypothesis. Without it clause 3 fails outright: with $r = 2$ , $p_0 = p_1 = 2$ and $(e_0,e_1) = (1,1)$ or $(2,0)$ , both products are $4$ , so the exponent vector is not determined. Injectivity is what makes $v_{p_j}$ read off one multiplicity rather than a sum of several.

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

For positive integers $a$ and $b$ : $a \mid b$ if and only if $v_p(a) \le v_p(b)$ for every prime $p$

Statement

Let $a, b \in \mathbb{Z}$ with $a \ge 1$ and $b \ge 1$ , and let $v_p$ be the $p$ -adic valuation of The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ . Then

$a \mid b \qquad \Longleftrightarrow \qquad v_p(a) \le v_p(b) \ \text{ for every prime } p .$

Both valuations are defined, since $a$ and $b$ are nonzero.

Facts & Assumptions

Given: The property $R(k)$ : "for every $b \ge 1$ , if $\iota(k) \ge 1$ and $v_p(\iota(k)) \le v_p(b)$ for every prime $p$ , then $\iota(k) \mid b$ ", where $\iota : \mathbb{N} \to \mathbb{Z}$ is the embedding of The naturals embed in the integers.

[L1]

For a prime $p$ and nonzero $u, v$ : $uv \ne 0$ and $v_p(uv) = v_p(u) + v_p(v)$ ( $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero).

[L2]

For a prime $p$ and nonzero $u$ : $v_p(u) \ge 1$ exactly when $p \mid u$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ , The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

[L3]

Every integer $> 1$ has a prime divisor (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime); every prime satisfies $q > 1$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L4]

Strong induction on $\mathbb{N}$ (Strong (complete) induction).

[L5]

$d \mid u$ means $u = dc$ for some $c$ ; divisibility is reflexive and transitive, and $d \mid u$ implies $d \mid uc$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ , Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ).

[L6]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

[L7]

On $\mathbb{N}$ : $m \le n$ means $m + c = n$ for some $c$ , so $m \le m + n$ always (Order on the natural numbers, Addition of natural numbers); $m + x \le m + y$ holds exactly when $x \le y$ (Order is compatible with addition); $m < n$ exactly when $\sigma(m) \le n$ , and $1 = \sigma(0)$ (Discreteness: $\sigma(n)$ is the immediate successor, The natural numbers $\mathbb{N}$ (von Neumann)).

[L8]

$\mathbb{Z}$ is a commutative ring; its order is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers).

[L9]

$\iota$ is injective, preserves addition, multiplication and order, and has as image exactly the nonnegative integers, with $\iota(0) = 0$ and $\iota(1) = 1$ (The naturals embed in the integers).

Proof

technique · induction

1.1

$0 < 1$ , since $1 = \iota(1)$ is nonnegative and differs from $0 = \iota(0)$ ; and every integer $x > 0$ satisfies $x \ge 1$ , because $x = \iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ and $\iota$ preserves the order.

L7L9

1.2

The forward implication. Suppose $a \mid b$ and fix $c$ with $b = ac$ . Then $c \ne 0$ , since $b \ne 0$ , so [L1] gives $v_p(b) = v_p(a) + v_p(c) \ge v_p(a)$ for every prime $p$ .

L1L5L7L8

1.3

Let $k \in \mathbb{N}$ and assume $R(j)$ for every $j < k$ .

ih

2.1

$R(0)$ holds vacuously: $\iota(0) = 0$ and $0 \ge 1$ is false.

basestep 1.1L9

2.2

Put $a := \iota(k)$ and suppose $a \ge 1$ , and let $b \ge 1$ satisfy $v_p(a) \le v_p(b)$ for every prime $p$ . If $a = 1$ then $a \mid b$ , so assume $a > 1$ .

step 1.1L5L8

3.1

Fix a prime $q$ with $q \mid a$ , and fix $a_1$ with $a = q a_1$ . Then $v_q(a) \ge 1$ , hence $v_q(b) \ge 1$ by hypothesis, so $q \mid b$ ; fix $b_1$ with $b = q b_1$ .

step 2.2L2L3L5choose

4.1

$a_1 \ge 1$ and $b_1 \ge 1$ : they are nonzero because $a$ and $b$ are, and if $a_1 < 0$ then $q a_1 < 0$ contradicting $a > 0$ , so $a_1 > 0$ and hence $a_1 \ge 1$ ; the same argument applies to $b_1$ .

step 1.1step 3.1L6L8

5.1

$a_1 < a$ : since $q > 1$ we have $q - 1 > 0$ , and $a_1 > 0$ , so $a - a_1 = (q-1)a_1 > 0$ .

step 3.1step 4.1L3L8

5.2

For every prime $p$ : $v_p(q) + v_p(a_1) = v_p(a) \le v_p(b) = v_p(q) + v_p(b_1)$ , so $v_p(a_1) \le v_p(b_1)$ by cancellation of $v_p(q)$ in the order of $\mathbb{N}$ .

step 2.2step 3.1step 4.1L1L7

6.1

Write $a_1 = \iota(j)$ ; then $j < k$ , since otherwise $k \le j$ and the order-preserving $\iota$ would give $a \le a_1$ , contradicting step 5.1. By step 1.3 applied to $j$ , together with steps 4.1 and 5.2, $a_1 \mid b_1$ .

step 1.3step 4.1step 5.1step 5.2L9

7.1

Hence $b = q b_1 = q(a_1 c) = (q a_1) c = a c$ for the $c$ with $b_1 = a_1 c$ , so $a \mid b$ and $R(k)$ holds.

step 3.1step 6.1L5L8

8.1

Steps 2.2 and 7.1 cover both possibilities for $a$ , so $R$ at $k$ follows from $R$ below $k$ ; with step 2.1, strong induction gives $R(k)$ for every $k$ . Since a positive integer $a$ is $\iota(k)$ for a unique $k$ , that is the reverse implication, and step 1.2 is the forward one.

step 1.2step 2.1step 2.2step 7.1L4L9discharge-induction∎

Remarks

No canonical factorisation is needed. The reverse implication is often proved by writing both integers over a common list of primes and comparing exponents; the descent used here peels off one prime divisor at a time and needs only additivity of $v_p$ ( $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero) and the existence of a prime divisor. The factorisation route is available too, via For $n \ge 1$ and any injective list $p : r \to \mathbb{Z}$ of primes containing every prime divisor of $n$ , one has $n = \prod_{i<r} p_i^{\,v_{p_i}(n)}$ ; the exponents are determined by $n$ , and $v_q(n) = 0$ for every prime $q$ outside the list, and gives the same statement.
Positivity is a real hypothesis, and only mildly so. $v_p$ is undefined at $0$ , so the pair must avoid it; signs are harmless, since $a \mid b$ is unchanged by replacing either argument by its negative (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ ) and $v_p(-u) = v_p(u)$ for the same reason. The statement is therefore about $|a|$ and $|b|$ in substance.
The valuation criterion is the shape the $\gcd$ and $\operatorname{lcm}$ formulas need, and For positive integers $a$ and $b$ and every prime $p$ : $v_p(\gcd(a,b)) = \min\{v_p(a), v_p(b)\}$ and $v_p(\operatorname{lcm}(a,b)) = \max\{v_p(a), v_p(b)\}$ ; so the exponent-wise greatest common divisor is the $\gcd$ of the divisibility page and not a second notion uses exactly this lemma to check the characterisation of $\gcd$ proved on the divisibility page.

TheoremStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

For positive integers $a$ and $b$ and every prime $p$ : $v_p(\gcd(a,b)) = \min\{v_p(a), v_p(b)\}$ and $v_p(\operatorname{lcm}(a,b)) = \max\{v_p(a), v_p(b)\}$ ; so the exponent-wise greatest common divisor is the $\gcd$ of the divisibility page and not a second notion

Statement

Let $a, b \in \mathbb{Z}$ with $a \ge 1$ and $b \ge 1$ , write $g := \gcd(a,b)$ (Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ) and $\ell := \operatorname{lcm}(a,b)$ (Common multiple, and the least common multiple $\operatorname{lcm}(a,b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ), and let $p$ be any prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ). Then $g \ge 1$ and $\ell \ge 1$ , so all four valuations below are defined (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ), and

$v_p(g) = \min\{\, v_p(a),\, v_p(b) \,\}$ ;
$v_p(\ell) = \max\{\, v_p(a),\, v_p(b) \,\}$ ,

the minimum and maximum being taken in $\mathbb{N}$ , whose order is total ( $\le$ is a linear order on $\mathbb{N}$ ).

The exponent recipe does not define a second notion. If $d \ge 1$ satisfies $v_p(d) = \min\{v_p(a),v_p(b)\}$ for every prime $p$ , then $d = \gcd(a,b)$ ; and if $d \ge 1$ satisfies $v_p(d) = \max\{v_p(a),v_p(b)\}$ for every prime $p$ , then $d = \operatorname{lcm}(a,b)$ .

Facts & Assumptions

Given: Integers $a, b \ge 1$ ; $g := \gcd(a,b)$ , $\ell := \operatorname{lcm}(a,b)$ ; and, for a prime $p$ , $m_p := \min\{v_p(a), v_p(b)\}$ and $M_p := \max\{v_p(a), v_p(b)\}$ .

[L1]

$\gcd(u,v) \ge 1$ unless $u = v = 0$ ; $\gcd(u,v)$ is a common divisor of $u$ and $v$ , and every common divisor of $u$ and $v$ divides it (Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ , $\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$ ; moreover $\gcd(a,0) = |a|$ , $\gcd(a,1) = 1$ , $\gcd(a,a) = |a|$ , and $\gcd(a,b) \ge 1$ unless $a = b = 0$ , Every common divisor of $a$ and $b$ divides $\gcd(a,b)$ ; consequently $d = \gcd(a,b)$ exactly when $d \ge 0$ , $d \mid a$ , $d \mid b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a,b) = (0,0)$ as well).

[L2]

For $u, v$ both nonzero, $\operatorname{lcm}(u,v)$ is the least positive common multiple of $u$ and $v$ ; in particular $u \mid \operatorname{lcm}(u,v)$ and $v \mid \operatorname{lcm}(u,v)$ (Common multiple, and the least common multiple $\operatorname{lcm}(a,b)$ , taken to be $0$ when $a = 0$ or $b = 0$ ).

[L3]

$\gcd(u,v) \cdot \operatorname{lcm}(u,v) = |uv|$ , and every common multiple of $u$ and $v$ is a multiple of $\operatorname{lcm}(u,v)$ (Every common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a,b)$ , and $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |ab|$ ).

[L4]

For positive $u, w$ : $u \mid w$ exactly when $v_q(u) \le v_q(w)$ for every prime $q$ (For positive integers $a$ and $b$ : $a \mid b$ if and only if $v_p(a) \le v_p(b)$ for every prime $p$ ).

[L5]

For a prime $p$ and nonzero $u, w$ : $v_p(uw) = v_p(u) + v_p(w)$ ( $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero).

[L6]

For a prime $p$ and nonzero $u$ : $p^{k} \mid u$ exactly when $k \le v_p(u)$ ; and $p^{k} \ge 1$ for every $k$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ , Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ , Semigroup and monoid, $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L7]

$u \mid w$ and $w \mid u$ hold together exactly when $|u| = |w|$ (For integers $a$ and $b$ the following are equivalent: $a \mid b$ and $b \mid a$ ; $b = ua$ for a unit $u$ ; $|a| = |b|$ . Being associates is an equivalence relation whose class of $a$ is $\{a, -a\}$ ); $|x| = x$ for $x \ge 0$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ).

[L9]

On $\mathbb{N}$ : the order is total, so any two naturals have a minimum and a maximum ( $\le$ is a linear order on $\mathbb{N}$ ); addition is commutative (Addition is commutative) and cancellative (Addition is cancellative); $m \le n$ means $m + c = n$ for some $c$ (Order on the natural numbers, Addition of natural numbers); $m < n$ exactly when $\sigma(m) \le n$ , and $1 = \sigma(0)$ (Discreteness: $\sigma(n)$ is the immediate successor, The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

$\mathbb{Z}$ is a commutative ring; its order is total, antisymmetric and transitive, is compatible with addition, and positives are closed under multiplication; a product of two nonzero integers is nonzero and cancellation holds (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers, The integers have no zero divisors; multiplicative cancellation).

[L11]

$\iota : \mathbb{N} \to \mathbb{Z}$ is injective and order preserving with image the nonnegative integers, $\iota(0) = 0$ , $\iota(1) = 1$ (The naturals embed in the integers).

Proof

technique · direct

1.1

$0 < 1$ , and every integer $x > 0$ satisfies $x \ge 1$ : $x = \iota(j)$ with $j \ne 0$ , so $1 = \sigma(0) \le j$ and $\iota$ preserves the order.

L9L11

1.2

For naturals $x, y$ the minimum and maximum exist by totality, and $\min\{x,y\} + \max\{x,y\} = x + y$ : if $x \le y$ the left side is $x + y$ , and if $y \le x$ it is $y + x = x + y$ .

L9

2.1

$a > 0$ and $b > 0$ , so $a \ne 0$ , $b \ne 0$ and $(a,b) \ne (0,0)$ ; hence $g \ge 1$ , and $\ell$ is the least positive common multiple of $a$ and $b$ , so $\ell \ge 1$ . All of $a, b, g, \ell$ are nonzero and their valuations are defined.

step 1.1L1L2L10

3.1

$g \mid a$ and $g \mid b$ , so $v_p(g) \le v_p(a)$ and $v_p(g) \le v_p(b)$ by [L4]; hence $v_p(g) \le m_p$ .

step 2.1step 1.2L1L4

3.2

Conversely $m_p \le v_p(a)$ and $m_p \le v_p(b)$ , so $p^{m_p} \mid a$ and $p^{m_p} \mid b$ by [L6]; thus $p^{m_p}$ is a common divisor of $a$ and $b$ and therefore divides $g$ . Since $g \ne 0$ , [L6] applied to $g$ gives $m_p \le v_p(g)$ .

step 2.1step 1.2L1L6

3.3

$ab > 0$ , so $|ab| = ab$ , and [L3] gives $g \ell = ab$ . Applying [L5] to the nonzero pairs $(g,\ell)$ and $(a,b)$ gives $v_p(g) + v_p(\ell) = v_p(ab) = v_p(a) + v_p(b)$ .

step 2.1L3L5L7L10

4.1

Clause 1: $v_p(g) = m_p$ , by antisymmetry of the order on $\mathbb{N}$ .

step 3.1step 3.2L9

5.1

Clause 2: substituting step 4.1 and step 1.2, $m_p + v_p(\ell) = v_p(a) + v_p(b) = m_p + M_p$ , so $v_p(\ell) = M_p$ by cancellation of addition on $\mathbb{N}$ .

step 1.2step 4.1step 3.3L9

5.2

Clause 3, first half. Let $d \ge 1$ satisfy $v_p(d) = m_p$ for every prime $p$ . Then $v_p(d) = v_p(g)$ for every $p$ by step 4.1, so $d \mid g$ and $g \mid d$ by [L4], hence $|d| = |g|$ ; both are positive, so $d = g$ .

step 2.1step 4.1L4L7

6.1

Clause 3, second half, by the same argument with step 5.1 in place of step 4.1: $v_p(d) = M_p = v_p(\ell)$ for every $p$ forces $d \mid \ell$ and $\ell \mid d$ , hence $d = \ell$ .

step 2.1step 5.1L4L7

7.1

Clauses 1, 2 and 3 are established.

step 4.1step 5.1step 5.2step 6.1∎

Remarks

This is the agreement item for the two pages. The exponent-wise recipe $\min$ for $\gcd$ and $\max$ for $\operatorname{lcm}$ is a computation of the $\gcd$ and $\operatorname{lcm}$ defined on the divisibility page, not a rival definition: clause 3 says any positive integer with the right valuations is that $\gcd$ , respectively that $\operatorname{lcm}$ . Nothing here redefines either symbol.
The identity $\min + \max =$ sum recovers the product formula. Adding clauses 1 and 2 gives $v_p(g) + v_p(\ell) = v_p(a) + v_p(b) = v_p(ab)$ for every $p$ , which is $g\ell = |ab|$ of Every common multiple of $a$ and $b$ is a multiple of $\operatorname{lcm}(a,b)$ , and $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = |ab|$ read through valuations. That is a consistency check, and in this proof the implication was used in the other direction: the product formula is what pins $v_p(\ell)$ from above. The independent bound $M_p \le v_p(\ell)$ , from $a \mid \ell$ and $b \mid \ell$ , also follows from [L2] and [L4] and agrees.
Both arguments are restricted to positive integers, and the restriction is not cosmetic. $v_p(0)$ is undefined (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ), so the pair $(0,0)$ — the one where the $\gcd$ convention lives — is out of scope entirely, and a negative argument is handled first by $\gcd(a,b) = \gcd(|a|,|b|)$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$ ; moreover $\gcd(a,0) = |a|$ , $\gcd(a,1) = 1$ , $\gcd(a,a) = |a|$ , and $\gcd(a,b) \ge 1$ unless $a = b = 0$ ).
The minimum and maximum are taken in $\mathbb{N}$ , through the totality of its order ( $\le$ is a linear order on $\mathbb{N}$ ), and not through the library's Maximum and minimum of a set, which is stated for real numbers. Valuations are natural numbers and there is no reason to leave $\mathbb{N}$ .

LemmaStatement: AI-adaptedProof: AI-generatedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

The $p$ -adic valuation extends to the nonzero rationals by $v_p(a/b) := v_p(a) - v_p(b) \in \mathbb{Z}$ , independently of the representation; it satisfies $v_p(xy) = v_p(x) + v_p(y)$ , and $v_p(x+y) \ge \min\{v_p(x), v_p(y)\}$ whenever $x$ , $y$ and $x+y$ are nonzero

Statement

Let $p$ be a prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ). A rational is a class $[(a,b)]$ of pairs of integers with $b \ne 0$ , written $a/b$ (The rationals as equivalence classes of pairs of integers), and $[(a,b)] \ne 0$ holds exactly when $a \ne 0$ (Arithmetic on the rationals). Write $\iota : \mathbb{N} \to \mathbb{Z}$ for the embedding of The naturals embed in the integers and $j : \mathbb{Z} \to \mathbb{Q}$ , $j(k) = [(k,1)]$ , for that of The integers embed in the rationals.

For a nonzero rational $x = [(a,b)]$ set

$v_p(x) \;:=\; \iota\bigl(v_p(a)\bigr) - \iota\bigl(v_p(b)\bigr) \;\in\; \mathbb{Z},$

with $v_p$ on nonzero integers as in The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ . Then:

The value does not depend on the representative, so $v_p$ is a well defined function from the nonzero rationals to $\mathbb{Z}$ .
It extends the integer valuation: $v_p(j(a)) = \iota(v_p(a))$ for every nonzero integer $a$ .
$v_p(xy) = v_p(x) + v_p(y)$ for all nonzero rationals $x, y$ .
$v_p(x+y) \ge \min\{\, v_p(x),\, v_p(y) \,\}$ whenever $x$ , $y$ and $x+y$ are all nonzero, the minimum being taken in the totally ordered $\mathbb{Z}$ .

Unlike its restriction to $\mathbb{Z}$ , this valuation takes integer values, which is why the difference is formed after transporting the two natural numbers into $\mathbb{Z}$ along $\iota$ .

Facts & Assumptions

Given: A prime $p$ ; nonzero rationals with representatives $x = [(a,b)]$ , $y = [(c,d)]$ , where $a, b, c, d \in \mathbb{Z}$ are all nonzero.

[L1]

$[(a,b)] = [(c,d)]$ exactly when $ad = cb$ ; $\mathbb{Q}$ consists of such classes with $b \ne 0$ (The rationals as equivalence classes of pairs of integers).

[L2]

$[(a,b)] + [(c,d)] = [(ad+cb,\, bd)]$ , $[(a,b)] \cdot [(c,d)] = [(ac,\, bd)]$ , $0 = [(0,1)]$ and $1 = [(1,1)]$ (Arithmetic on the rationals); $\mathbb{Q}$ is a field (The rationals form a field, Field).

[L3]

$j(k) = [(k,1)]$ is injective and preserves addition, multiplication and order (The integers embed in the rationals).

[L4]

For a prime $p$ and nonzero integers $u, w$ : $uw \ne 0$ and $v_p(uw) = v_p(u) + v_p(w)$ ; and $v_p(u+w) \ge \min\{v_p(u), v_p(w)\}$ when $u$ , $w$ and $u+w$ are nonzero ( $v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero).

[L5]

$v_p(1) = 0$ (For a prime $p$ and a nonzero integer $a$ : $p^{v_p(a)} \mid a$ and $p^{v_p(a)+1} \nmid a$ ; $p^{k} \mid a$ holds exactly for $k \le v_p(a)$ ; $v_p(a) \ge 1$ exactly when $p \mid a$ ; $v_p(1) = v_p(-1) = 0$ ; and $v_p(p) = 1$ , The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

[L6]

$\iota$ is injective and preserves addition, multiplication and order, with image the nonnegative integers and $\iota(0) = 0$ , $\iota(1) = 1$ (The naturals embed in the integers).

[L7]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation).

[L8]

$\mathbb{Z}$ is a commutative ring: addition and multiplication are associative and commutative, $x + 0 = x$ , and every $x$ has an additive inverse $-x$ , with $-(-x) = x$ and $-(u+w) = (-u)+(-w)$ ; we write $u - w$ for $u + (-w)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L9]

The order on $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition, so $u \le w$ implies $u + z \le w + z$ (The integers form a totally ordered ring, Order on the integers).

[L10]

The order on $\mathbb{N}$ is total, so any two naturals have a minimum; addition on $\mathbb{N}$ is commutative ( $\le$ is a linear order on $\mathbb{N}$ , Addition is commutative, Order on the natural numbers, Addition of natural numbers, The natural numbers $\mathbb{N}$ (von Neumann)).

Proof

technique · direct

1.1

If $x = [(a,b)]$ is a nonzero rational then $a \ne 0$ and $b \ne 0$ , so $v_p(a)$ and $v_p(b)$ are both defined.

L1L2

2.1

Clause 1. Suppose $[(a,b)] = [(c,d)]$ with all four entries nonzero. Then $ad = cb$ , and both sides are nonzero, so [L4] gives $v_p(a) + v_p(d) = v_p(c) + v_p(b)$ in $\mathbb{N}$ . Applying the addition-preserving $\iota$ and rearranging in $\mathbb{Z}$ gives $\iota(v_p(a)) - \iota(v_p(b)) = \iota(v_p(c)) - \iota(v_p(d))$ .

step 1.1L1L4L6L7L8

2.2

Clause 4. Assume $x$ , $y$ and $x+y$ are nonzero. Then $x + y = [(ad+cb,\, bd)]$ with $bd \ne 0$ , and $ad + cb \ne 0$ because $x+y \ne 0$ ; also $ad \ne 0$ and $cb \ne 0$ .

step 1.1L1L2L7

3.1

Clause 2. For a nonzero integer $a$ , $j(a) = [(a,1)]$ , so $v_p(j(a)) = \iota(v_p(a)) - \iota(v_p(1)) = \iota(v_p(a)) - 0 = \iota(v_p(a))$ .

step 2.1L3L5L6L8

3.2

Clause 3. $xy = [(ac, bd)]$ , with $ac \ne 0$ and $bd \ne 0$ , so $v_p(xy) = \iota(v_p(ac)) - \iota(v_p(bd)) = \iota(v_p(a) + v_p(c)) - \iota(v_p(b) + v_p(d))$ .

step 1.1step 2.1L2L4L7

3.3

By [L4], $v_p(ad + cb) \ge \min\{v_p(ad),\, v_p(cb)\} = \min\{v_p(a) + v_p(d),\ v_p(c) + v_p(b)\}$ ; applying the order-preserving injection $\iota$ turns this into the same inequality between the corresponding integers.

step 2.2L4L6L10

4.1

Since $\iota$ preserves addition, that value is $\bigl(\iota(v_p(a)) + \iota(v_p(c))\bigr) - \bigl(\iota(v_p(b)) + \iota(v_p(d))\bigr)$ , which rearranges in the commutative ring $\mathbb{Z}$ to $\bigl(\iota(v_p(a)) - \iota(v_p(b))\bigr) + \bigl(\iota(v_p(c)) - \iota(v_p(d))\bigr) = v_p(x) + v_p(y)$ .

step 3.2L6L8

4.2

Subtracting the integer $\iota(v_p(b)) + \iota(v_p(d)) = \iota(v_p(bd))$ from both sides, which preserves the order, and using that subtraction of a fixed element commutes with taking the smaller of two integers, gives $v_p(x+y) \ge \min\{\iota(v_p(a)) - \iota(v_p(b)),\ \iota(v_p(c)) - \iota(v_p(d))\} = \min\{v_p(x), v_p(y)\}$ .

step 2.2step 3.3L4L6L8L9

5.1

Clauses 1 to 4 are established.

step 2.1step 3.1step 4.1step 4.2∎

Remarks

Relation to the published $2$ -adic example. The published The $2$ -adic absolute value gives an ultrametric on $\mathbb{Q}$ , in which every triangle is isosceles and every point of a ball is a centre ↗ records that the general $p$ -adic machinery is available, but nevertheless develops $p=2$ from parity alone. The present lemma supplies the general algebraic extension: representation-independence is exactly the assertion that $ad=cb$ forces the two candidate values to agree.
Nothing metric is stated here, deliberately. The $p$ -adic absolute value $|x|_p = p^{-v_p(x)}$ and the ultrametric it induces need real powers with integer exponents and the definition of a metric space, all of which live far above this page in the library's order; they are not defined here and nothing on this page depends on them. What is proved is the algebra: a homomorphism from the nonzero rationals under multiplication to $\mathbb{Z}$ under addition, satisfying the ultrametric inequality on valuations.
The values are integers, not naturals. $v_p(1/p) = -1$ , so the extension genuinely leaves $\mathbb{N}$ ; that is why the two integer valuations are transported along $\iota$ before being subtracted. As on $\mathbb{Z}$ , the value at $0$ is left undefined (The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$ ).

CorollaryStatement: AI-adaptedProof: AI-generatedprecheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28Open item page →

A rational root of $x^{k} = m$ is an integer: if $k \ge 1$ , $m \in \mathbb{Z}$ , $x \in \mathbb{Q}$ and $x^{k}$ is the image of $m$ , then $x$ is the image of an integer

Statement

$\mathbb{Q}$ is a field (The rationals form a field, Field), so $(\mathbb{Q},\cdot,1)$ is a commutative monoid and natural powers $x^{k}$ are defined in it by Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ . Write $j : \mathbb{Z} \to \mathbb{Q}$ , $j(u) = [(u,1)]$ , for the embedding of The integers embed in the rationals.

Let $k \in \mathbb{N}$ with $k \ge 1$ , let $m \in \mathbb{Z}$ , and let $x \in \mathbb{Q}$ satisfy

$x^{k} \;=\; j(m).$

Then $x = j(z)$ for some $z \in \mathbb{Z}$ .

Facts & Assumptions

Given: $k \in \mathbb{N}$ with $k \ge 1$ , $m \in \mathbb{Z}$ , and $x \in \mathbb{Q}$ with $x^{k} = j(m)$ .

[L1]

A rational is a class $[(u,w)]$ with $u, w \in \mathbb{Z}$ , $w \ne 0$ , and $[(u,w)] = [(u',w')]$ exactly when $u w' = u' w$ (The rationals as equivalence classes of pairs of integers).

[L2]

$[(u,w)] \cdot [(u',w')] = [(uu', ww')]$ , $0 = [(0,1)]$ , $1 = [(1,1)]$ , and $[(u,w)] \ne 0$ exactly when $u \ne 0$ (Arithmetic on the rationals).

[L3]

$\mathbb{Q}$ is a field: multiplication is associative and commutative on all of $\mathbb{Q}$ with $y \cdot 1 = y$ and $y \cdot 0 = 0$ (The rationals form a field, Field), so $(\mathbb{Q},\cdot,1)$ is a commutative monoid (Semigroup and monoid).

[L4]

$g^{0} = e$ and $g^{\sigma(t)} = g^{t} \cdot g$ in a monoid (Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ ).

[L5]

$j(u) = [(u,1)]$ is injective and preserves addition and multiplication (The integers embed in the rationals).

[L6]

For $d := \gcd(u,w) \ne 0$ there are unique $u/d$ and $w/d$ with $u = d(u/d)$ , $w = d(w/d)$ , and $\gcd(u/d, w/d) = 1$ (If $d = \gcd(a,b)$ is nonzero then $a/d$ and $b/d$ are coprime, Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ , Coprime integers: $\gcd(a,b) = 1$ ).

[L7]

$\gcd(u,w) \ge 1$ unless $u = w = 0$ ( $\gcd$ is symmetric and unchanged by signs: $\gcd(a,b) = \gcd(b,a) = \gcd(|a|,|b|)$ ; moreover $\gcd(a,0) = |a|$ , $\gcd(a,1) = 1$ , $\gcd(a,a) = |a|$ , and $\gcd(a,b) \ge 1$ unless $a = b = 0$ , Common divisor, and the greatest common divisor $\gcd(a,b)$ , with the convention $\gcd(0,0) := 0$ ).

[L8]

If $\gcd(u,w) = 1$ then the set of common divisors of $u$ and $w$ is exactly $\{1,-1\}$ ( $a$ and $b$ are coprime if and only if $ax + by = 1$ for some integers $x, y$ ; and in that case the only common divisors of $a$ and $b$ are $1$ and $-1$ , $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L9]

If $q$ is prime and $q \mid uv$ then $q \mid u$ or $q \mid v$ (Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ ).

[L10]

Every integer $> 1$ has a prime divisor, and every prime $q$ satisfies $q > 1$ (Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime, Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L11]

Divisibility is reflexive and transitive, $d \mid u$ implies $d \mid uc$ , and $d \mid u$ means $u = dc$ for some $c$ (Divisibility is reflexive and transitive on $\mathbb{Z}$ , and is linear: if $d \mid a$ and $d \mid b$ then $d \mid ax + by$ for all integers $x, y$ ; also $d \mid a$ implies $d \mid ac$ , $-d \mid a$ and $d \mid -a$ , Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ for some integer $q$ ).

[L12]

Induction on $\mathbb{N}$ (The principle of mathematical induction); every natural $\ne 0$ is a successor (Every nonzero natural number is a successor); $m < n$ exactly when $\sigma(m) \le n$ , and $1 = \sigma(0)$ (Discreteness: $\sigma(n)$ is the immediate successor, The natural numbers $\mathbb{N}$ (von Neumann), Order on the natural numbers).

[L14]

$u \mid 1$ exactly when $u = 1$ or $u = -1$ ( $(\mathbb{Z}, \cdot, 1)$ is a commutative monoid whose group of units is $\{1, -1\}$ ; equivalently $u \mid 1$ holds exactly for $u = 1$ and $u = -1$ ).

[L13]

A product of two nonzero integers is nonzero (The integers have no zero divisors; multiplicative cancellation); $\mathbb{Z}$ is a commutative ring whose order is total, antisymmetric and transitive (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals, The integers form a totally ordered ring, Order on the integers); $\iota : \mathbb{N} \to \mathbb{Z}$ is injective and order preserving with image the nonnegative integers (The naturals embed in the integers).

Proof

technique · direct

1.1

$0 < 1$ in $\mathbb{Z}$ , and every integer $y > 0$ satisfies $y \ge 1$ : $y = \iota(t)$ with $t \ne 0$ , so $1 = \sigma(0) \le t$ and $\iota$ preserves the order.

L12L13

1.2

For integers $u, w$ with $w \ne 0$ and every $t \in \mathbb{N}$ : $w^{t} \ne 0$ and $[(u,w)]^{t} = [(u^{t}, w^{t})]$ , powers on the left in $\mathbb{Q}$ and on the right in $\mathbb{Z}$ . The set of $t$ for which this holds contains $0$ , since $w^{0} = 1 \ne 0$ and $[(u,w)]^{0} = 1 = [(1,1)] = [(u^{0}, w^{0})]$ ; and if it holds at $t$ then $w^{\sigma(t)} = w^{t} w \ne 0$ and $[(u,w)]^{\sigma(t)} = [(u^{t},w^{t})] \cdot [(u,w)] = [(u^{t}u,\, w^{t}w)] = [(u^{\sigma(t)}, w^{\sigma(t)})]$ . Induction finishes it.

L1L2L4L12L13

1.3

Suppose first $x = 0$ . Since $k \ge 1$ , write $k = \sigma(t)$ ; then $x^{k} = x^{t} \cdot 0 = 0 = j(0)$ , so $j(m) = j(0)$ and $m = 0$ by injectivity of $j$ ; and $x = 0 = j(0)$ is the image of an integer.

L3L4L5L12

1.4

Suppose instead $x \ne 0$ , and write $x = [(a,b)]$ with $b \ne 0$ ; then $a \ne 0$ . If $b < 0$ , replace $(a,b)$ by $(-a,-b)$ , which represents the same rational because $a(-b) = (-a)b$ ; so we may assume $b > 0$ .

L1L2L13choose

2.1

For a prime $q$ , an integer $u$ and $t \ge 1$ : if $q \mid u^{t}$ then $q \mid u$ . Let $S$ be the set of $t$ for which this implication holds; $0 \in S$ vacuously, since $t \ge 1$ fails there. Suppose $t \in S$ and $q \mid u^{\sigma(t)} = u^{t} u$ . By [L9] either $q \mid u^{t}$ or $q \mid u$ ; in the second case we are done, and in the first, if $t \ge 1$ then $t \in S$ gives $q \mid u$ , while if $t = 0$ then $u^{t} = 1$ and $q \mid 1$ is impossible for a prime, since $q > 1 > 0 > -1$ would then be contradicted. So $\sigma(t) \in S$ and $S = \mathbb{N}$ .

step 1.1L4L9L10L12L13L14

2.2

Put $d := \gcd(a,b)$ ; since $a \ne 0$ we have $d \ge 1 > 0$ , so $d \ne 0$ . Put $a_1 := a/d$ and $b_1 := b/d$ , so that $a = d a_1$ , $b = d b_1$ and $\gcd(a_1,b_1) = 1$ .

step 1.1step 1.4L6L7L13

3.1

$a_1 \ne 0$ and $b_1 > 0$ : if $a_1 = 0$ then $a = 0$ , and if $b_1 \le 0$ then $b = d b_1 \le 0$ , both contrary to step 1.4. Moreover $[(a,b)] = [(a_1,b_1)]$ , because $a b_1 = (d a_1) b_1 = a_1 (d b_1) = a_1 b$ .

step 1.4step 2.2L1L13

4.1

By step 1.2, $x^{k} = [(a_1,b_1)]^{k} = [(a_1^{k}, b_1^{k})]$ , and this equals $j(m) = [(m,1)]$ , so $a_1^{k} \cdot 1 = m\, b_1^{k}$ , that is $a_1^{k} = m\, b_1^{k}$ .

step 1.2step 3.1L1L5L13

5.1

Suppose $b_1 > 1$ and fix a prime $q$ with $q \mid b_1$ . Since $k \ge 1$ , write $k = \sigma(t)$ ; then $b_1^{k} = b_1^{t} b_1$ , so $b_1 \mid b_1^{k}$ and hence $q \mid b_1^{k}$ by transitivity. Then $q \mid m\, b_1^{k} = a_1^{k}$ , so $q \mid a_1$ by step 2.1.

step 2.1step 4.1L4L10L11L12

6.1

So $q$ is a common divisor of $a_1$ and $b_1$ , which are coprime, hence $q = 1$ or $q = -1$ by [L8] and [L14]; but $q > 1 > 0 > -1$ , a contradiction. Therefore $b_1 \le 1$ , and $b_1 > 0$ gives $b_1 \ge 1$ , so $b_1 = 1$ .

step 1.1step 2.2step 3.1step 5.1L8L10L13L14

7.1

Hence $x = [(a_1,1)] = j(a_1)$ is the image of an integer; together with step 1.3 this covers both cases.

step 1.3step 3.1step 6.1L5∎

Remarks

The instances live on the companion page. No rational squares to $3$ or to $6$ , and none cubes to $2$ : each is this corollary followed by ruling out the finitely many integer candidates by size, and all three are worked out in No rational squares to $3$ or to $6$ , and none cubes to $2$ : three instances of the rational-root corollary ↗.
The argument lives inside $\mathbb{Q}$ and never enters $\mathbb{R}$ . No $n$ -th root is asserted to exist; the hypothesis is that a rational $x$ already satisfies $x^{k} = j(m)$ , and the conclusion is about its denominator. The powers are monoid powers of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ in $(\mathbb{Q},\cdot,1)$ , not Integer powers $a^m$ , which is stated in the ambient ordered field.
This is a second route to a fact the library already had. The published FALSE: some rational number squares to 2 refutes "some rational number squares to $2$ " by parity alone, on the construction pages, long before primes existed here. The case $k = 2$ , $m = 2$ of this corollary gives the same conclusion by a different argument, and the two agree: a rational squaring to $2$ would have to be an integer $z$ with $z^{2} = 2$ , and $1 < 2 < 4$ leaves no candidate.
Where primality is used. Exactly once, in step 2.1, through Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$ : a prime dividing a power divides the base. For a composite divisor the step fails, which is why the classical proof cannot be run with an arbitrary common factor in place of a prime.

Primes, Euclid's Lemma and the Fundamental Theorem of Arithmetic

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

Prime and composite integers: ppp is prime when p>1p > 1p>1 and its only positive divisors are 111 and ppp

Definition

Remarks

For a prime ppp and any integer aaa, gcd⁡(p,a)\gcd(p,a)gcd(p,a) is ppp when p∣ap \mid ap∣a and 111 otherwise; so p∤ap \nmid ap∤a makes ppp and aaa coprime

Statement

Facts & Assumptions

Proof

Remarks

Euclid's lemma: if ppp is prime and p∣abp \mid abp∣ab then p∣ap \mid ap∣a or p∣bp \mid bp∣b

Statement

Facts & Assumptions

Proof

Remarks

For an integer p>1p > 1p>1: ppp is prime if and only if, for all integers aaa and bbb, p∣abp \mid abp∣ab implies p∣ap \mid ap∣a or p∣bp \mid bp∣b

Statement

Facts & Assumptions

Proof

Remarks

If a prime ppp divides a finite product ∏i<nai\prod_{i<n} a_i∏i<n​ai​ of integers then p∣aip \mid a_ip∣ai​ for some i<ni < ni<n; at n=0n = 0n=0 the product is 111 and the hypothesis cannot hold

Statement

Facts & Assumptions

Proof

Remarks

Every integer n>1n > 1n>1 has a prime divisor; indeed the least divisor of nnn that exceeds 111 is prime

Statement

Facts & Assumptions

Proof

Remarks

Every integer n≥1n \ge 1n≥1 is a finite product of primes: there are r∈Nr \in \mathbb{N}r∈N and a list p:r→Zp : r \to \mathbb{Z}p:r→Z of primes with n=∏i<rpin = \prod_{i<r} p_in=∏i<r​pi​, the case n=1n = 1n=1 being the empty product

Statement

Facts & Assumptions

Proof

Remarks

Statement

Facts & Assumptions

Proof

Remarks

Every nonzero integer nnn is u∏i<rpiu \prod_{i<r} p_iu∏i<r​pi​ with u∈{1,−1}u \in \{1,-1\}u∈{1,−1} and every pip_ipi​ prime; uuu and rrr are determined by nnn, and the list is determined up to a permutation

Statement

Facts & Assumptions

Proof

Remarks

Euclid's theorem: for every n∈Nn \in \mathbb{N}n∈N and every list p:n→Zp : n \to \mathbb{Z}p:n→Z of primes there is a prime not among p0,…,pn−1p_0, \dots, p_{n-1}p0​,…,pn−1​; consequently the set of primes is not finite

Statement

Facts & Assumptions

Proof

Remarks

The ppp-adic valuation vp(a)v_p(a)vp​(a) of a nonzero integer: the greatest k∈Nk \in \mathbb{N}k∈N with pk∣ap^{k} \mid apk∣a

Definition

Remarks

Statement

Facts & Assumptions

Proof

Remarks

vp(ab)=vp(a)+vp(b)v_p(ab) = v_p(a) + v_p(b)vp​(ab)=vp​(a)+vp​(b) for nonzero integers a,ba, ba,b, and vp(a+b)≥min⁡{vp(a),vp(b)}v_p(a+b) \ge \min\{v_p(a), v_p(b)\}vp​(a+b)≥min{vp​(a),vp​(b)} whenever aaa, bbb and a+ba+ba+b are all nonzero

Statement

Facts & Assumptions

Proof

Remarks

Statement

Facts & Assumptions

Proof

Remarks

For positive integers aaa and bbb: a∣ba \mid ba∣b if and only if vp(a)≤vp(b)v_p(a) \le v_p(b)vp​(a)≤vp​(b) for every prime ppp

Statement

Facts & Assumptions

Proof

Remarks

Statement

Facts & Assumptions

Proof

Remarks

Statement

Facts & Assumptions

Proof

Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$

For a prime $p$ and any integer $a$ , $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime

Euclid's lemma: if $p$ is prime and $p \mid ab$ then $p \mid a$ or $p \mid b$

For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$

If a prime $p$ divides a finite product $\prod_{i<n} a_i$ of integers then $p \mid a_i$ for some $i < n$ ; at $n = 0$ the product is $1$ and the hypothesis cannot hold

Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime

Every integer $n \ge 1$ is a finite product of primes: there are $r \in \mathbb{N}$ and a list $p : r \to \mathbb{Z}$ of primes with $n = \prod_{i<r} p_i$ , the case $n = 1$ being the empty product

Every nonzero integer $n$ is $u \prod_{i<r} p_i$ with $u \in \{1,-1\}$ and every $p_i$ prime; $u$ and $r$ are determined by $n$ , and the list is determined up to a permutation

Euclid's theorem: for every $n \in \mathbb{N}$ and every list $p : n \to \mathbb{Z}$ of primes there is a prime not among $p_0, \dots, p_{n-1}$ ; consequently the set of primes is not finite

The $p$ -adic valuation $v_p(a)$ of a nonzero integer: the greatest $k \in \mathbb{N}$ with $p^{k} \mid a$

$v_p(ab) = v_p(a) + v_p(b)$ for nonzero integers $a, b$ , and $v_p(a+b) \ge \min\{v_p(a), v_p(b)\}$ whenever $a$ , $b$ and $a+b$ are all nonzero

For positive integers $a$ and $b$ : $a \mid b$ if and only if $v_p(a) \le v_p(b)$ for every prime $p$

A rational root of $x^{k} = m$ is an integer: if $k \ge 1$ , $m \in \mathbb{Z}$ , $x \in \mathbb{Q}$ and $x^{k}$ is the image of $m$ , then $x$ is the image of an integer