How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

✓ 9 results · all verified · 3 also independently AI-judged

Every result on this page is machine-checked by a proof checker and read in full by a delegated reviewing agent on the owner's instruction; the judge is an additional, independent cross-model AI review of the proofs. The 6 not AI-judged were verified by owner audit (typically over a confirmed judge false positive), not failures.

Primes and Factorisation: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

None yet.

5 · Examples, counterexamples and false statements

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

$360 = 2^{3} \cdot 3^{2} \cdot 5$ and $84 = 2^{2} \cdot 3 \cdot 7$ , with $\gcd (360, 84) = 12$ and $lcm (360, 84) = 2520$ read off the exponents

Example

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 $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ . For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

$360 = 2^{3} \cdot 3^{2} \cdot 5, 84 = 2^{2} \cdot 3 \cdot 7.$

Reading these against the injective list of primes $p = (2, 3, 5, 7)$ , which contains every prime divisor of both numbers, For $n \geq 1$ and any injective list $p : r \to 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 identifies the exponents as valuations (The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ ):

$p$	$2$	$3$	$5$	$7$
$v_{p} (360)$	$3$	$2$	$1$	$0$
$v_{p} (84)$	$2$	$1$	$0$	$1$
$\min$	$2$	$1$	$0$	$0$
$\max$	$3$	$2$	$1$	$1$

By 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} (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 the minimum row is the valuation vector of $\gcd (360, 84)$ and the maximum row that of $lcm (360, 84)$ , so

$\gcd (360, 84) = 2^{2} \cdot 3 = 12, lcm (360, 84) = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 2520.$

Two independent checks are carried out below: the Euclidean algorithm of The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ returns $12$ from the descent $360 = 4 \cdot 84 + 24$ , $84 = 3 \cdot 24 + 12$ , $24 = 2 \cdot 12 + 0$ ; and $12 \cdot 2520 = 30240 = 360 \cdot 84$ , as Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ requires.

Facts & Assumptions

Given: The integers $360$ , $84$ , $12$ and $2520$ , and the primes $2$ , $3$ , $5$ , $7$ .

[L1]

$Z$ is a commutative ring: multiplication is associative and commutative, $x \cdot 1 = x$ , and multiplication distributes over addition (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).

[L2]

$g^{0} = 1$ and $g^{σ (k)} = g^{k} g$ in $(Z, \cdot, 1)$ ; and $g^{m + n} = g^{m} g^{n}$ (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^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute, Semigroup and monoid, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

[L3]

For $n \geq 1$ and an injective list $p$ of primes containing every prime divisor of $n$ : $n = \prod_{i < r} p_{i}^{v_{p_{i}} (n)}$ , the exponents are determined by $n$ , and $v_{q} (n) = 0$ for a prime $q$ off the list (For $n \geq 1$ and any injective list $p : r \to 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, The fundamental theorem of arithmetic: every integer $n \geq 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_{π (i)}$ for some $π \in Sym (r)$ , Every integer $n \geq 1$ is a finite product of primes: there are $r \in N$ and a list $p : r \to Z$ of primes with $n = \prod_{i < r} p_{i}$ , the case $n = 1$ being the empty product, The $p$ -adic valuation $v_{p} (a)$ of a nonzero integer: the greatest $k \in N$ with $p^{k} ∣ a$ , For a prime $p$ and a nonzero integer $a$ : $p^{v_{p} (a)} ∣ a$ and $p^{v_{p} (a) + 1} ∤ a$ ; $p^{k} ∣ a$ holds exactly for $k \leq v_{p} (a)$ ; $v_{p} (a) \geq 1$ exactly when $p ∣ a$ ; $v_{p} (1) = v_{p} (- 1) = 0$ ; and $v_{p} (p) = 1$ , $v_{p} (a b) = v_{p} (a) + v_{p} (b)$ for nonzero integers $a, b$ , and $v_{p} (a + b) \geq \min {v_{p} (a), v_{p} (b)}$ whenever $a$ , $b$ and $a + b$ are all nonzero).

[L4]

For positive $a, b$ and every prime $p$ : $v_{p} (\gcd (a, b)) = \min {v_{p} (a), v_{p} (b)}$ and $v_{p} (lcm (a, b)) = \max {v_{p} (a), v_{p} (b)}$ ; and a positive integer with those valuations is the $\gcd$ , respectively the $lcm$ (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} (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, Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ , Common multiple, and the least common multiple $lcm (a, b)$ , taken to be $0$ when $a = 0$ or $b = 0$ , Every common divisor of $a$ and $b$ divides $\gcd (a, b)$ ; consequently $d = \gcd (a, b)$ exactly when $d \geq 0$ , $d ∣ a$ , $d ∣ b$ , and every common divisor of $a$ and $b$ divides $d$ — a characterisation that holds at $(a, b) = (0, 0)$ as well).

[L5]

For $a \in Z$ and $b > 0$ there is exactly one pair $(q, r)$ with $a = q b + r$ and $0 \leq r < b$ , and $b ∣ a$ exactly when $r = 0$ (Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L6]

The remainder descent from $(a, b)$ with $b > 0$ terminates and its last nonzero remainder is $\gcd (a, b)$ (The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ ).

[L7]

$\gcd (a, b) lcm (a, b) = ∣ a b ∣$ (Every common multiple of $a$ and $b$ is a multiple of $lcm (a, b)$ , and $\gcd (a, b) \cdot lcm (a, b) = ∣ a b ∣$ ).

[L9]

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

[L8]

An integer $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ); and a divisor $d$ of a nonzero $a$ satisfies $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

Verification

technique · direct

1.1

The two products are correct: $2^{3} = 8$ , $3^{2} = 9$ , and $8 \cdot 9 = 72$ with $72 \cdot 5 = 360$ ; likewise $2^{2} = 4$ , $4 \cdot 3 = 12$ and $12 \cdot 7 = 84$ .

L1L2algebra

1.2

$2$ , $3$ , $5$ and $7$ are prime, and they are pairwise distinct. Each exceeds $1$ ; and a positive divisor $d$ of such a number $a$ satisfies $1 \leq d \leq a$ by [L8], so the candidates are the finitely many integers in that range, and each is settled by its remainder under [L5]: $2 = 1 \cdot 2 + 0$ has only $1$ and $2$ as candidates; for $3$ the extra candidate $2$ gives $3 = 1 \cdot 2 + 1$ ; for $5$ the extra candidates $2, 3, 4$ give remainders $1$ , $2$ , $1$ ; and for $7$ the extra candidates $2, 3, 4, 5, 6$ give remainders $1$ , $1$ , $3$ , $2$ , $1$ . In each case no divisor other than $1$ and the number itself survives.

L1L5L8algebra

2.1

The list $p = (2, 3, 5, 7)$ is injective and consists of primes, and it contains every prime divisor of $360$ and of $84$ . Injectivity and primality are step 1.2. For the covering: if $q$ is prime and $q ∣ 360 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 3 \cdot 5$ , repeated use of [L9] gives $q ∣ 2$ , $q ∣ 3$ or $q ∣ 5$ , and $q$ being a positive divisor of a prime with $q > 1$ forces $q$ to be that prime; likewise $q ∣ 84 = 2 \cdot 2 \cdot 3 \cdot 7$ forces $q \in {2, 3, 7}$ .

step 1.1step 1.2L8L9

3.1

By [L3] applied to $360$ with this list, the exponents in step 1.1 are the valuations: $v_{2} (360) = 3$ , $v_{3} (360) = 2$ , $v_{5} (360) = 1$ , $v_{7} (360) = 0$ .

step 1.1step 2.1L3

3.2

By [L3] applied to $84$ : $v_{2} (84) = 2$ , $v_{3} (84) = 1$ , $v_{5} (84) = 0$ , $v_{7} (84) = 1$ .

step 1.1step 2.1L3

4.1

Taking minima entrywise gives $2, 1, 0, 0$ , and $2^{2} \cdot 3^{1} \cdot 5^{0} \cdot 7^{0} = 4 \cdot 3 = 12$ ; by [L3] the valuations of $12$ against this list are exactly those exponents, so $12$ has the valuation vector of $\gcd (360, 84)$ and therefore equals it by [L4].

step 3.1step 3.2L1L2L3L4

4.2

Taking maxima entrywise gives $3, 2, 1, 1$ , and $2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 72 \cdot 35 = 2520$ ; the same argument gives $lcm (360, 84) = 2520$ .

step 3.1step 3.2L1L2L3L4

5.1

First check, the Euclidean algorithm. $4 \cdot 84 = 336$ and $336 + 24 = 360$ with $0 \leq 24 < 84$ ; $3 \cdot 24 = 72$ and $72 + 12 = 84$ with $0 \leq 12 < 24$ ; $2 \cdot 12 = 24$ and $24 + 0 = 24$ with $0 \leq 0 < 12$ . By the uniqueness in [L5] these are the divisions of the descent, whose last nonzero remainder is $12$ , so $\gcd (360, 84) = 12$ by [L6], agreeing with step 4.1.

step 4.1L1L5L6algebra

5.2

Second check, the product formula. $12 \cdot 2520 = 30240$ and $360 \cdot 84 = 30240$ , and $360 \cdot 84 > 0$ so $∣ 360 \cdot 84 ∣ = 360 \cdot 84$ ; this is [L7], agreeing with steps 4.1 and 4.2.

step 4.1step 4.2L1L7algebra

6.1

The factorisations, the valuation table, and both values of $\gcd$ and $lcm$ are verified, and the two independent checks agree.

step 4.1step 4.2step 5.1step 5.2∎

Remarks

The cross-check is the point of the example. The Euclidean algorithm: for $a \in Z$ and $b > 0$ the remainder descent from $(a, b)$ terminates, and the last nonzero remainder is $\gcd (a, b)$ computes $\gcd (360, 84)$ without ever mentioning a prime, and the exponent recipe computes it without ever performing a division; they return the same integer because 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} (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 proves the recipe identifies the $\gcd$ of Common divisor, and the greatest common divisor $\gcd (a, b)$ , with the convention $\gcd (0, 0) : = 0$ rather than defining a rival.
Which method is practical is a separate question. Factoring $360$ and $84$ is easy because they are small; for large integers the Euclidean algorithm is the only one of the two that runs, since no factorisation is needed. Nothing here claims anything about the cost of either procedure.
The exponent $0$ columns matter. $v_{5} (84) = 0$ and $v_{7} (360) = 0$ are what make the same list serve both numbers, and clause 2 of For $n \geq 1$ and any injective list $p : r \to 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 is the statement that every prime off the list contributes $0$ as well.

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

$2$ is prime, and it is the only even prime: every even integer $n > 2$ is composite

Example

Call an integer even when $2 ∣ n$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ), where $2 : = 1 + 1$ . Then:

$2$ is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ );
every even integer $n > 2$ is composite.

So $2$ is the only even prime, and every other prime is odd.

Facts & Assumptions

Given: The integer $2 : = 1 + 1$ .

[L1]

$p$ is prime when $p > 1$ and every positive divisor of $p$ is $1$ or $p$ ; an integer $n > 1$ that is not prime is composite (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L2]

If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L3]

$∣ x ∣ = x$ when $x \geq 0$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L4]

Divisibility is reflexive; $d ∣ u$ means $u = d c$ for some $c$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L5]

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

[L6]

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

[L7]

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

Verification

technique · direct

1.1

$0 < 1$ : $1 = ι (1)$ is nonnegative and differs from $0 = ι (0)$ by injectivity of $ι$ . Adding $1$ gives $1 < 1 + 1 = 2$ , so $2 > 1 > 0$ .

L5L6

1.2

There is no integer strictly between $0$ and $1$ : if $0 < x$ then $x = ι (j)$ with $j \neq 0$ , so $1 = σ (0) \leq j$ and hence $1 \leq x$ , because $ι$ preserves the order.

L6L7

2.1

Claim 1. Let $d$ be a positive divisor of $2$ . Since $2 \neq 0$ , [L2] gives $∣ d ∣ \leq ∣ 2 ∣ = 2$ , and $d > 0$ gives $∣ d ∣ = d$ , so $1 \leq d \leq 2$ by step 1.2.

step 1.1step 1.2L2L3L5

2.2

Claim 2. Let $n > 2$ with $2 ∣ n$ . Then $n > 2 > 1$ , so $n > 1$ ; and $2$ is a positive divisor of $n$ with $2 \neq 1$ (by step 1.1) and $2 \neq n$ (since $n > 2$ ).

step 1.1L5

3.1

The only integers $d$ with $1 \leq d \leq 2$ are $1$ and $2$ : if $d \neq 1$ then $1 < d$ , so $1 + 1 \leq d$ by step 1.2 applied to $d - 1 > 0$ , that is $2 \leq d$ , and with $d \leq 2$ antisymmetry gives $d = 2$ . Both $1$ and $2$ do divide $2$ . Hence the only positive divisors of $2$ are $1$ and $2$ , and $2 > 1$ , so $2$ is prime.

step 1.1step 1.2step 2.1L1L4L5

3.2

So $n$ has a positive divisor other than $1$ and $n$ , hence is not prime; being greater than $1$ , it is composite.

step 2.2L1

4.1

Claims 1 and 2 are established, and together they say $2$ is the only even prime: an even prime $n$ satisfies $n > 1$ , hence $2 \leq n$ by step 3.1's argument, and $n > 2$ is excluded because such an $n$ is composite by step 3.2; so $n = 2$ .

step 1.2step 3.1step 3.2L1L5∎

Remarks

"Even" is defined here as divisibility by $2$ , not by a new notion of parity. That is Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ applied at $d = 2$ , so no second vocabulary is introduced, and the odd integers are exactly those with remainder $1$ under Division with remainder in $Z$ : for $a \in Z$ and $b > 0$ there are unique $q, r \in Z$ with $a = q b + r$ and $0 \leq r < b$ .
This is why parity sufficed for the $2$ -adic case elsewhere in the library. The published The $2$ -adic absolute value gives an ultrametric on $Q$ , in which every triangle is isosceles and every point of a ball is a centre ↗ builds the $2$ -adic valuation from parity alone and records that the general $p$ -adic valuation needs primality and unique factorisation. At $p = 2$ "not divisible by $2$ " is a single condition that the division algorithm decides; for a general prime $p$ the corresponding step is Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ .
The smallest prime is $2$ , and there is no smaller one to miss. $1$ and $0$ are excluded by the clause $p > 1$ of Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , and negative integers by the same clause, so the classification here is complete rather than a convention about where to start.

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

No rational squares to $3$ or to $6$ , and none cubes to $2$ : three instances of the rational-root corollary

Example

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 $(Q, \cdot, 1)$ of the field $Q$ (The rationals form a field, Field), and $j : Z \to Q$ , $j (u) = [(u, 1)]$ , is the embedding of The integers embed in the rationals. There is no $x \in Q$ with

$x^{2} = j (3), nor with x^{2} = j (6), nor with x^{3} = j (2) .$

Each is an instance of A rational root of $x^{k} = m$ is an integer: if $k \geq 1$ , $m \in Z$ , $x \in Q$ and $x^{k}$ is the image of $m$ , then $x$ is the image of an integer: such an $x$ would have to be $j (z)$ for an integer $z$ , and the remaining work is to rule out the finitely many integer candidates by size, which is done below.

Facts & Assumptions

Given: The integers $2$ , $3$ , $4$ , $6$ , $8$ , $9$ and the rationals they name under $j$ .

[L1]

If $k \geq 1$ , $m \in Z$ , $x \in Q$ and $x^{k} = j (m)$ , then $x = j (z)$ for some $z \in Z$ (A rational root of $x^{k} = m$ is an integer: if $k \geq 1$ , $m \in Z$ , $x \in Q$ and $x^{k}$ is the image of $m$ , then $x$ is the image of an integer).

[L2]

$j$ is injective and preserves addition and multiplication (The integers embed in the rationals); $Q$ is a field, so $(Q, \cdot, 1)$ is a commutative monoid (The rationals form a field, Field, Semigroup and monoid, The rationals as equivalence classes of pairs of integers, Arithmetic on the rationals).

[L3]

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

[L4]

$∣ x ∣ \geq 0$ ; $∣ x ∣ = 0$ exactly when $x = 0$ ; $∣ x y ∣ = ∣ x ∣ ∣ y ∣$ ; $∣ x ∣ = x$ for $x \geq 0$ (The absolute value $∣ a ∣$ of an integer, Absolute value in $Z$ : $∣ a ∣ \geq 0$ ; $∣ a ∣ = 0$ exactly when $a = 0$ ; $∣ - a ∣ = ∣ a ∣$ ; $∣ a b ∣ = ∣ a ∣ ∣ b ∣$ ; $- ∣ a ∣ \leq a \leq ∣ a ∣$ ; and $∣ a ∣ \leq c$ exactly when $- c \leq a \leq c$ ).

[L5]

$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, The integers have no zero divisors; multiplicative cancellation).

[L6]

$ι : N \to Z$ is injective and order preserving with image the nonnegative integers, $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers); $m < k$ exactly when $σ (m) \leq k$ , and $1 = σ (0)$ (Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann), Order on the natural numbers).

Verification

technique · direct

1.1

$0 < 1$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 = σ (0) \leq t$ and $ι$ preserves the order. Consequently $y > c$ implies $y \geq c + 1$ for all integers $y, c$ , by applying this to $y - c$ .

L5L6

1.2

Monotonicity of squaring and cubing on the nonnegative integers: if $0 \leq u \leq w$ then $u^{2} \leq w^{2}$ and $u^{3} \leq w^{3}$ , since $w^{2} - u^{2} = (w - u) (w + u)$ and $w^{3} - u^{3} = (w - u) (w^{2} + w u + u^{2})$ have both factors nonnegative.

L3L5

1.3

Suppose $x \in Q$ has $x^{2} = j (3)$ . By [L1] with $k = 2 \geq 1$ we get $x = j (z)$ for some $z \in Z$ ; then $j (z^{2}) = j (z)^{2} = j (3)$ , so $z^{2} = 3$ by injectivity of $j$ .

L1L2L3

2.1

Now $∣ z ∣^{2} = ∣ z^{2} ∣ = ∣ 3 ∣ = 3$ , and $∣ z ∣ \geq 0$ . If $∣ z ∣ = 0$ then $∣ z ∣^{2} = 0 \neq 3$ ; if $∣ z ∣ = 1$ then $∣ z ∣^{2} = 1 \neq 3$ ; and if $∣ z ∣ \geq 2$ then $∣ z ∣^{2} \geq 2^{2} = 4 > 3$ by step 1.2. Since $∣ z ∣ \geq 0$ and $∣ z ∣ \neq 0$ force $∣ z ∣ \geq 1$ , and $∣ z ∣ \neq 1$ forces $∣ z ∣ \geq 2$ , no value remains, so no such $x$ exists.

step 1.1step 1.2step 1.3L4L5

2.2

Suppose $x^{2} = j (6)$ . As in step 1.3, $x = j (z)$ with $z^{2} = 6$ , so $∣ z ∣^{2} = 6$ . Now $0^{2} = 0$ , $1^{2} = 1$ , $2^{2} = 4$ , and $∣ z ∣ \geq 3$ gives $∣ z ∣^{2} \geq 9 > 6$ ; none of $0$ , $1$ , $4$ is $6$ , and the four ranges are exhaustive by step 1.1. So no such $x$ exists.

step 1.1step 1.2step 1.3L1L2L3L4L5

2.3

Suppose $x^{3} = j (2)$ . As before $x = j (z)$ with $z^{3} = 2$ . If $z \leq 0$ then $z^{3} \leq 0 < 2$ , since $z^{3} = z \cdot z \cdot z$ is a product of three nonpositive factors and is therefore nonpositive. So $z \geq 1$ ; and $1^{3} = 1 \neq 2$ , while $z \geq 2$ gives $z^{3} \geq 2^{3} = 8 > 2$ by step 1.2. No value remains, so no such $x$ exists.

step 1.1step 1.2step 1.3L1L2L3L5

3.1

The three claims are established.

step 2.1step 2.2step 2.3∎

Remarks

A fourth instance was already in the library, proved differently. The published FALSE: some rational number squares to 2 refutes "some rational number squares to $2$ " on the construction pages, by parity alone and long before primes were available here. The case $k = 2$ , $m = 2$ of A rational root of $x^{k} = m$ is an integer: if $k \geq 1$ , $m \in Z$ , $x \in Q$ and $x^{k}$ is the image of $m$ , then $x$ is the image of an integer gives the same conclusion from Euclid's lemma instead, and the two agree.
Nothing here asserts that a real square root of $3$ exists. The statement is entirely about $Q$ : no rational squares to $3$ . That $R$ contains such a number is a separate fact, proved elsewhere in the library from completeness, and it is not used or needed above.
The size argument is the whole of the remaining work. Once the corollary has reduced the question to integers, each case is a finite check, because squaring and cubing are monotone on the nonnegative integers and the candidate values overshoot immediately.

ExampleConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

For every $n \in N$ there are $n$ consecutive composite integers: with $N : = \prod_{j < n} (j + 2)$ , each of $N + 2, \dots, N + n + 1$ is composite

Example

Let $n \in N$ , write $ι : N \to Z$ for the embedding of The naturals embed in the integers, and put

$N : = \prod_{j < n} ι (j + 2),$

the finite product of The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity taken in the commutative monoid $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ; so $N$ is the product of the $n$ integers $2, 3, \dots, n + 1$ , and $N = 1$ when $n = 0$ .

Then $N + ι (j + 2)$ is composite (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ) for every $j < n$ . Those $n$ integers are $N + 2, N + 3, \dots, N + n + 1$ , consecutive because consecutive values of $j$ change the summand by $1$ . So for every $n$ there is a run of $n$ consecutive composite integers.

Facts & Assumptions

Given: $n \in N$ and $N : = \prod_{j < n} ι (j + 2)$ .

[L1]

$\prod_{i < 0} g_{i} = e$ and $\prod_{i < σ (m)} g_{i} = (\prod_{i < m} g_{i}) g_{m}$ ; the value depends only on the entries named (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , Semigroup and monoid).

[L2]

Splitting law: $\prod_{i < m + c} g_{i} = (\prod_{i < m} g_{i}) (\prod_{l < c} g_{m + l})$ (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]

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

[L4]

Divisibility is reflexive and transitive and is linear: $d ∣ u$ and $d ∣ w$ give $d ∣ u + w$ ; $d ∣ u$ means $u = d c$ for some $c$ (Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ , Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L6]

Induction on $N$ (The principle of mathematical induction).

[L7]

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

[L8]

On $N$ : $m + 0 = m$ and $m + σ (k) = σ (m + k)$ , so $σ (k) = k + 1$ ; addition is commutative (Addition of natural numbers, Addition is commutative, The natural numbers $N$ (von Neumann)); $a \leq b$ means $a + c = b$ for some $c$ (Order on the natural numbers); $a < b$ exactly when $σ (a) \leq b$ (Discreteness: $σ (n)$ is the immediate successor); and $j < σ (j)$ , with $i < σ (j)$ exactly when $i \leq j$ (On $N$ the order is membership: $m < n ⟺ m \in n$ ).

[L9]

Verification

technique · direct

1.1

$0 < 1$ in $Z$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 = σ (0) \leq t$ and $ι$ preserves the order.

L7L8L9

1.2

Fix $j < n$ and put $k : = ι (j + 2)$ . Then $k ∣ N$ : since $j < n$ we have $σ (j) \leq n$ , so $n = σ (j) + c$ for some $c \in N$ , and the splitting law gives $N = (\prod_{i < σ (j)} ι (i + 2)) (\prod_{l < c} ι (σ (j) + l + 2))$ , while $\prod_{i < σ (j)} ι (i + 2) = (\prod_{i < j} ι (i + 2)) k$ . Rearranging by associativity and commutativity, $N = k \cdot B$ for an integer $B$ .

L1L2L4L8L9

2.1

For every $j \in N$ , $ι (j + 2) \geq 2 > 1$ , where $2 : = 1 + 1$ . Indeed $2 = σ (1) = 1 + 1$ in $N$ gives $ι (2) = ι (1) + ι (1) = 1 + 1$ ; and $2 \leq j + 2$ in $N$ because $2 + j = j + 2$ , so $ι (2) \leq ι (j + 2)$ .

step 1.1L7L8L9

2.2

Hence $k ∣ N + k$ , by linearity applied to $k ∣ N$ and $k ∣ k$ .

step 1.2L4

3.1

$N \geq 1$ . Let $T$ be the set of $m \in N$ with $\prod_{i < m} ι (i + 2) \geq 1$ . Then $0 \in T$ , the empty product being $1$ . If $m \in T$ then $\prod_{i < σ (m)} ι (i + 2) = (\prod_{i < m} ι (i + 2)) ι (m + 2)$ has both factors $\geq 1 > 0$ , so the product is positive and hence $\geq 1$ by step 1.1. By induction $T = N$ , so $N \geq 1 > 0$ .

step 1.1step 2.1L1L6L9

4.1

$N + k > k > 1$ , because $N > 0$ ; in particular $N + k > 1$ and $N + k \neq k$ .

step 2.1step 3.1L9

5.1

So $k$ is a positive divisor of $N + k$ with $k \neq 1$ and $k \neq N + k$ , and $N + k > 1$ ; therefore $N + k$ is not prime, and being greater than $1$ it is composite.

step 2.1step 2.2step 4.1L3

6.1

As $j$ runs over $0, 1, \dots, n - 1$ the integers $N + ι (j + 2)$ run over $N + 2, N + 3, \dots, N + n + 1$ , each obtained from the previous by adding $1$ , since $ι (σ (j) + 2) = ι (j + 2) + 1$ . All $n$ of them are composite by step 5.1.

step 5.1L7L8L9∎

Remarks

The factorial is available at this point, and is deliberately not used. The factorial $n!$ and the falling factorial $n^{\underline{k}}$ , defined by recursion in $N$ defines $n!$ by recursion in $N$ , on a page this one may cite. The real-valued copy in For every real $x$ , $x^{k} / k! \to 0$ ↗ is a separate object and is already declared as a forward reference. Neither is a factorial on $Z$ : naming $ι (n!)$ as one would create a dictionary obligation this page cannot discharge. The finite product of The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity in $(Z, \cdot, 1)$ does everything needed, and $N$ is $(n + 1)!$ only in the informal sense.
The case $n = 0$ is real and vacuous. The empty product is $1$ , there is no $j < 0$ , and the claim asserts nothing — correctly, since a run of $0$ consecutive composites is no claim at all.
This says the gaps are unbounded and nothing about where the primes are. It is entirely compatible with Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite: primes keep coming, and yet one can always find a stretch of any prescribed length containing none. No claim is made here about how large $N$ must be, or about the smallest run of a given length.

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

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$

Statement refuted

Refuted claim. Let $(M, \cdot, 1)$ be a commutative monoid (Semigroup and monoid) whose underlying set consists of integers $\geq 1$ , contains $1$ , and is closed under the multiplication of $Z$ (Binary operation on a set; associativity, commutativity, and a subset closed under the operation, Left identity, right identity, and two-sided identity for a binary operation). Call $h \in M$ with $h > 1$ irreducible in $M$ when there are no $u, v \in M$ with $u > 1$ , $v > 1$ and $h = u v$ . Then factorisation into irreducibles of $M$ is unique up to order: if

$\prod_{i < r} h_{i} = \prod_{j < s} h_{j}^{'}$

with every $h_{i}$ and $h_{j}^{'}$ irreducible in $M$ , then $r = s$ and $h_{i}^{'} = h_{π (i)}$ for every $i < r$ , for some $π \in Sym (r)$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition, The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

Witness. Take

$H : = {h \in Z : h \geq 1 and 3 ∣ h - 1} = {1, 4, 7, 10, 13, \dots},$

with the multiplication of $Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ). Then $4$ , $10$ and $25$ are irreducible in $H$ , and

$100 = 4 \cdot 25 = 10 \cdot 10,$

two lists of irreducibles of $H$ that no permutation matches, since $10 \neq 4$ and $10 \neq 25$ .

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The set $H$ above and the integers $4$ , $5$ , $10$ , $25$ , $100$ .

[L1]

A monoid is a set with an associative binary operation and a two-sided identity, and is commutative when the operation is (Semigroup and monoid, Binary operation on a set; associativity, commutativity, and a subset closed under the operation, Left identity, right identity, and two-sided identity for a binary operation).

[L2]

$(Z, \cdot, 1)$ is a commutative monoid ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ); $Z$ is a commutative ring with $x \cdot 1 = x$ and distributivity (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L3]

[L4]

$d ∣ u$ means $u = d c$ for some $c \in Z$ ; divisibility is reflexive and transitive and is linear (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L5]

[L6]

If $d ∣ a$ and $a \neq 0$ then $∣ d ∣ \leq ∣ a ∣$ (If $d ∣ a$ and $a \neq 0$ then $d \neq 0$ and $∣ d ∣ \leq ∣ a ∣$ ; hence the set of divisors of a nonzero integer is bounded above by $∣ a ∣$ ).

[L7]

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); a prime $q$ satisfies $q > 1$ and has only $1$ and $q$ as positive divisors (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ).

[L8]

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

[L9]

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

[L10]

The order on $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); $ι$ is injective and order preserving with image the nonnegative integers (The naturals embed in the integers, The natural numbers $N$ (von Neumann), Order on the natural numbers, Discreteness: $σ (n)$ is the immediate successor).

Counterexample

technique · direct

1.1

$0 < 1$ in $Z$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 \leq y$ because $ι$ preserves the order. Consequently $y > c$ implies $y \geq c + 1$ .

L10

1.2

$H$ is a commutative monoid under the multiplication of $Z$ . It contains $1$ , since $1 \geq 1$ and $1 - 1 = 0 = 3 \cdot 0$ . It is closed: if $h - 1 = 3 a$ and $h^{'} - 1 = 3 b$ then $h h^{'} - 1 = (3 a + 1) (3 b + 1) - 1 = 3 (3 a b + a + b)$ , so $3 ∣ h h^{'} - 1$ ; and $h, h^{'} \geq 1$ give $h h^{'} \geq 1$ . Associativity, commutativity and the identity are inherited from $Z$ .

L1L2L4L10

1.3

$4$ , $10$ , $25$ and $100$ lie in $H$ : $4 - 1 = 3 = 3 \cdot 1$ , $10 - 1 = 9 = 3 \cdot 3$ , $25 - 1 = 24 = 3 \cdot 8$ and $100 - 1 = 99 = 3 \cdot 33$ , and all four exceed $1$ . And $5 \notin H$ : $5 - 1 = 4 = 1 \cdot 3 + 1$ , whose remainder $1$ is nonzero, so $3 ∤ 4$ by [L5].

L4L5algebra

2.1

Every $h \in H$ with $h > 1$ satisfies $h \geq 4$ . Indeed $h - 1 > 0$ and $h - 1 = 3 t$ for some $t$ , so $t > 0$ and hence $t \geq 1$ by step 1.1, giving $h - 1 \geq 3$ and $h \geq 4$ .

step 1.1L4L10

2.2

$5$ is prime. It exceeds $1$ ; a positive divisor $d$ of $5$ satisfies $1 \leq d \leq 5$ by [L6] and step 1.1, and the intermediate candidates are ruled out by their remainders: $5 = 2 \cdot 2 + 1$ , $5 = 1 \cdot 3 + 2$ and $5 = 1 \cdot 4 + 1$ . So the only positive divisors are $1$ and $5$ .

step 1.1L5L6L7algebra

3.1

$4$ and $10$ are irreducible in $H$ . If $4 = u v$ or $10 = u v$ with $u, v \in H$ both $> 1$ , then $u \geq 4$ and $v \geq 4$ by step 2.1, so $u v \geq 16$ by monotonicity of multiplication by a positive factor; but $16 > 10 > 4$ .

step 2.1L10algebra

3.2

$25$ is irreducible in $H$ . Suppose $25 = u v$ with $u, v \in H$ and $u, v > 1$ . Each of $u$ and $v$ has a prime divisor by [L7]; if $q ∣ u$ then $q ∣ 25 = 5 \cdot 5$ , so $q ∣ 5$ by [L8], and $q$ being a positive divisor of the prime $5$ with $q > 1$ forces $q = 5$ . Hence $5 ∣ u$ , and symmetrically $5 ∣ v$ ; write $u = 5 w$ , $v = 5 y$ .

step 2.1step 2.2L4L7L8

4.1

Then $25 \cdot 1 = 25 = u v = 25 (w y)$ , and $25 \neq 0$ , so $w y = 1$ by cancellation. Since $u = 5 w > 0$ and $5 > 0$ we get $w > 0$ , hence $w \geq 1$ ; likewise $y \geq 1$ ; and $w y = 1$ with both $\geq 1$ forces $w = y = 1$ , since $w \geq 2$ would give $w y \geq 2$ . So $u = v = 5$ , contradicting $5 \notin H$ from step 1.3.

step 1.1step 1.3step 3.2L2L9L10algebra

5.1

The two factorisations. $4 \cdot 25 = 100$ and $10 \cdot 10 = 100$ , and by [L3] the lists $h = (4, 25)$ and $h^{'} = (10, 10)$ of length $2$ have $\prod_{i < 2} h_{i} = (1 \cdot 4) \cdot 25 = 100$ and $\prod_{i < 2} h_{i}^{'} = (1 \cdot 10) \cdot 10 = 100$ . All four entries are irreducible in $H$ by steps 3.1 and 4.1.

step 3.1step 4.1L2L3algebra

6.1

No permutation matches them. For $π \in Sym (2)$ the value $h_{π (0)}$ is $4$ or $25$ , and $h_{0}^{'} = 10$ differs from both. So the refuted claim fails for $M = H$ at the element $100$ , with $r = s = 2$ : the lists have the same length and still no permutation carries one to the other.

step 1.2step 5.1L1∎

Remarks

Existence is not the issue; uniqueness is. Every element of $H$ greater than $1$ does factor into irreducibles of $H$ , by exactly the descent that proves Every integer $n \geq 1$ is a finite product of primes: there are $r \in N$ and a list $p : r \to Z$ of primes with $n = \prod_{i < r} p_{i}$ , the case $n = 1$ being the empty product in $Z$ : a smallest factor above $1$ is irreducible, and the quotient is smaller. What fails in $H$ is the second half of The fundamental theorem of arithmetic: every integer $n \geq 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_{π (i)}$ for some $π \in Sym (r)$ .
What fails is Euclid's lemma. In $H$ , $10$ is irreducible and $100 = 4 \cdot 25$ is a product of two elements of $H$ that $10$ divides inside $H$ , since $100 = 10 \cdot 10$ ; yet $10 ∤ 4$ and $10 ∤ 25$ , because $4 = 0 \cdot 10 + 4$ and $25 = 2 \cdot 10 + 5$ have nonzero remainders. So the analogue of Euclid's lemma: if $p$ is prime and $p ∣ a b$ then $p ∣ a$ or $p ∣ b$ is false in $H$ , and by For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p ∣ a b$ implies $p ∣ a$ or $p ∣ b$ that property, and not indecomposability, is what unique factorisation actually needs.
The example needs nothing beyond $Z$ and divisibility. The classical witness for this phenomenon uses algebraic integers, which are not available at this point in the reading order; $H$ is a subset of $Z$ closed under multiplication, and every claim above is a statement about integers.

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

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

Statement refuted

Refuted claim. The clause $p > 1$ in Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ is an arbitrary convention: replacing it by $p \geq 1$ would leave The fundamental theorem of arithmetic: every integer $n \geq 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_{π (i)}$ for some $π \in Sym (r)$ true as stated.

Write prime $^{*}$ for the modified notion — $p \geq 1$ and the only positive divisors of $p$ are $1$ and $p$ — so that $1$ is prime $^{*}$ and every prime is prime $^{*}$ . The claim under refutation is that for lists of prime $^{*}$ s, $\prod_{i < r} p_{i} = \prod_{j < s} q_{j}$ still forces $r = s$ and $q_{i} = p_{π (i)}$ for some $π \in Sym (r)$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition, The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity).

Witness. The lists $(2, 3)$ , $(1, 2, 3)$ and $(1, 1, 2, 3)$ , of lengths $2$ , $3$ and $4$ , all consist of prime $^{*}$ s and all have product $6$ . So $r = s$ fails already between the first two, and no permutation can exist because the index sets have different sizes.

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $1$ , $2$ , $3$ and $6$ , and the three lists above.

[L1]

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

[L2]

$\prod_{i < 0} g_{i} = e$ and $\prod_{i < σ (m)} g_{i} = (\prod_{i < m} g_{i}) g_{m}$ , in the commutative monoid $(Z, \cdot, 1)$ (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , Semigroup and monoid).

[L3]

$u ∣ 1$ exactly when $u = 1$ or $u = - 1$ ( $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ); $d ∣ a$ means $a = d c$ for some $c$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ ).

[L4]

[L5]

[L6]

If $n \approx m$ with $n, m \in N$ then $n = m$ ; equivalently there is no bijection between two distinct natural numbers (The pigeonhole principle on $N$ , Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Injection, surjection, bijection).

[L7]

A permutation of the von Neumann natural $r$ is a bijection $r \to r$ (The symmetric group $Sym (X)$ : the bijections of a set $X$ under composition); $n = {m : m < n}$ (On $N$ the order is membership: $m < n ⟺ m \in n$ , The natural numbers $N$ (von Neumann)).

[L8]

$Z$ is a commutative ring with $x \cdot 1 = x$ ; its 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); $ι$ is injective and order preserving with image the nonnegative integers (The naturals embed in the integers, Discreteness: $σ (n)$ is the immediate successor, Order on the natural numbers).

[L9]

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

Counterexample

technique · direct

1.1

$0 < 1 < 2 < 3$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 \leq y$ since $ι$ preserves the order.

1.2

All three products are $6$ . By [L2], $\prod_{i < 2} (2, 3)_{i} = (1 \cdot 2) \cdot 3 = 6$ ; $\prod_{i < 3} (1, 2, 3)_{i} = ((1 \cdot 1) \cdot 2) \cdot 3 = 6$ ; and $\prod_{i < 4} (1, 1, 2, 3)_{i} = (((1 \cdot 1) \cdot 1) \cdot 2) \cdot 3 = 6$ .

L2L8algebra

2.1

$1$ is prime $^{*}$ : $1 \geq 1$ , and a positive divisor $d$ of $1$ satisfies $d ∣ 1$ , hence $d = 1$ or $d = - 1$ by [L3], and positivity leaves $d = 1$ , which is $1$ itself.

step 1.1L3L8

2.2

$2$ and $3$ are prime, hence prime $^{*}$ . Each exceeds $1$ ; a positive divisor $d$ of such an $a$ satisfies $1 \leq d \leq a$ by [L4] and step 1.1, and the intermediate candidate for $a = 3$ is settled by $3 = 1 \cdot 2 + 1$ , whose remainder is nonzero. For $a = 2$ there is no intermediate candidate.

step 1.1L1L4L5algebra

3.1

The three lists consist of prime $^{*}$ s, by steps 2.1 and 2.2, and their lengths are $2$ , $3$ and $4$ , which are pairwise distinct natural numbers.

step 2.1step 2.2L8

4.1

So the uniqueness clause fails at its very first assertion: taking $p = (2, 3)$ and $q = (1, 2, 3)$ gives $\prod_{i < 2} p_{i} = \prod_{j < 3} q_{j}$ with $2 \neq 3$ , so " $r = s$ " is false.

step 1.2step 3.1

5.1

Nor could the clause be rescued by dropping " $r = s$ " and asking only for a bijection: a permutation in the sense of [L7] is a bijection between index sets, and by [L6] no bijection exists between the distinct naturals $2$ and $3$ .

step 3.1step 4.1L6L7

6.1

Existence, by contrast, survives the change: $6 = 2 \cdot 3$ is still a factorisation into prime $^{*}$ s, and every $n \geq 1$ still has one by [L9], since every prime is prime $^{*}$ . So it is precisely the uniqueness half that forces the convention $p > 1$ .

step 2.2step 1.2step 5.1L9∎

Remarks

The failure is not a technicality about lists. Under the modified definition an integer would have infinitely many factorisations, one for each number of padding factors $1$ , so no formulation of uniqueness survives: neither "the same length", nor "the same multiset of factors", nor "the same exponent vector", since $1$ would carry an arbitrary exponent.
Existence is what makes the convention a genuine choice rather than a necessity. Both notions give factorisations of every $n \geq 1$ , and the difference shows up only when one asks whether the factorisation is unique. That is exactly the asymmetry Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ appeals to when it excludes $1$ .
$0$ is excluded for a different reason. It is not that $0$ would break uniqueness; it is that $0$ has every positive integer as a divisor, so it fails the divisor clause outright, and a product containing the factor $0$ is $0$ rather than the integer being factored.

False statementConstruction: Literature-sourcedVerification: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

FALSE: for every finite list $p_{0}, \dots, p_{n - 1}$ of distinct primes, $p_{0} \dots p_{n - 1} + 1$ is prime

Statement

False claim: for every $n \in N$ and every injective list $p : n \to Z$ of primes (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ , Injection, surjection, bijection),

$(\prod_{i < n} p_{i}) + 1$

is prime, the product being that of The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity in the commutative monoid $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ .

The true statement is Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite, which concludes only that this integer has a prime divisor not on the list — never that it is itself prime.

Witness: $n = 6$ and $p = (2, 3, 5, 7, 11, 13)$ . Here $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 = 30030$ and

$30031 = 59 \cdot 509,$

so $30031$ has the positive divisor $59$ , which is neither $1$ nor $30031$ : it is composite.

Numerals. For $k \in N$ the symbol $k$ inside $Z$ means $ι (k)$ , the embedding of The naturals embed in the integers.

Facts & Assumptions

Given: The integers $2, 3, 5, 7, 11, 13, 59, 509, 30030, 30031$ .

[L1]

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

[L2]

$\prod_{i < 0} g_{i} = e$ and $\prod_{i < σ (m)} g_{i} = (\prod_{i < m} g_{i}) g_{m}$ (The product $g_{0} g_{1} \dots g_{n - 1}$ of a finite list in a monoid, by recursion, with the empty product ( $n = 0$ ) equal to the identity, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , Semigroup and monoid).

[L3]

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

[L4]

[L6]

$d ∣ a$ means $a = d c$ for some $c$ ; divisibility is transitive (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L7]

$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 (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).

[L8]

$ι$ is injective and order preserving with image the nonnegative integers, $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers); $m < k$ exactly when $σ (m) \leq k$ and $1 = σ (0)$ (Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann), Order on the natural numbers).

Refutation

technique · direct

1.1

$0 < 1$ , and every integer $y > 0$ satisfies $y \geq 1$ ; consequently $y > c$ implies $y \geq c + 1$ .

L7L8

1.2

$59 \cdot 509 = 30031$ : indeed $59 \cdot 500 = 29500$ and $59 \cdot 9 = 531$ , and $29500 + 531 = 30031$ . So $59 ∣ 30031$ .

L6L7algebra

2.1

A composite integer $n$ has a prime divisor $q$ with $q \cdot q \leq n$ . Let $q$ be the least divisor of $n$ exceeding $1$ , which is prime by [L3], and write $n = q m$ . Then $m > 0$ , since $n > 0$ and $q > 0$ ; and $m \neq 1$ , since $m = 1$ would make $n = q$ prime. So $m > 1$ , and $m ∣ n$ , so $m$ is a divisor of $n$ exceeding $1$ and minimality gives $q \leq m$ ; multiplying by $q > 0$ gives $q \cdot q \leq q m = n$ .

step 1.1L1L3L6L7

2.2

$59 \neq 1$ and $59 \neq 30031$ , and $59 > 0$ ; also $30031 > 1$ . So $30031$ has a positive divisor other than $1$ and itself, hence is not prime, and being greater than $1$ it is composite.

step 1.1step 1.2L1L7

3.1

$2$ , $3$ , $5$ , $7$ , $11$ and $13$ are prime. Each exceeds $1$ , so by step 2.1 it suffices to check the primes $q$ with $q \cdot q$ at most the number. For $2$ and $3$ there is none, since the least prime is $2$ and $2 \cdot 2 = 4 > 3$ . For $5$ and $7$ only $q = 2$ qualifies, and $5 = 2 \cdot 2 + 1$ , $7 = 3 \cdot 2 + 1$ . For $11$ and $13$ only $q = 2$ and $q = 3$ qualify, since $4 \cdot 4 = 16 > 13$ , and $11 = 5 \cdot 2 + 1$ , $11 = 3 \cdot 3 + 2$ , $13 = 6 \cdot 2 + 1$ , $13 = 4 \cdot 3 + 1$ . In every case no such divisor exists, so none of the six is composite, and each is therefore prime.

step 2.1L1L4L7algebra

4.1

The six are pairwise distinct, and the list $p = (2, 3, 5, 7, 11, 13)$ is therefore an injective list of primes of length $6$ .

step 3.1L7L8

5.1

$\prod_{i < 6} p_{i} = 30030$ : applying [L2] six times, $1 \cdot 2 = 2$ , $2 \cdot 3 = 6$ , $6 \cdot 5 = 30$ , $30 \cdot 7 = 210$ , $210 \cdot 11 = 2310$ and $2310 \cdot 13 = 30030$ . Hence the integer named by the claim is $30030 + 1 = 30031$ .

step 4.1L2L7algebra

6.1

Steps 4.1, 5.1 and 2.2 exhibit an injective list of primes whose product plus $1$ is composite: the claim is false.

step 4.1step 5.1step 2.2∎

Remarks

Re-reading the true theorem shows it never says otherwise. Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite takes $N = \prod_{i < n} p_{i} + 1$ , applies Every integer $n > 1$ has a prime divisor; indeed the least divisor of $n$ that exceeds $1$ is prime to get a prime divisor $q$ of $N$ , and then shows $q$ is not among the $p_{i}$ . Primality of $N$ is never claimed and is never used.
The promise the theorem does make is kept here. $59$ is prime — by step 2.1 the only candidates are the primes $q$ with $q \cdot q \leq 59$ , that is $q \in {2, 3, 5, 7}$ since $8 \cdot 8 = 64 > 59$ , and $59 = 29 \cdot 2 + 1$ , $59 = 19 \cdot 3 + 2$ , $59 = 11 \cdot 5 + 4$ , $59 = 8 \cdot 7 + 3$ all have nonzero remainder — and $59$ is not among $2, 3, 5, 7, 11, 13$ , exactly as Euclid's theorem: for every $n \in N$ and every list $p : n \to Z$ of primes there is a prime not among $p_{0}, \dots, p_{n - 1}$ ; consequently the set of primes is not finite promises. Nothing is claimed here about $509$ .
Smaller lists do not refute the claim. For $n = 0, 1, 2, 3, 4, 5$ with the first primes in order, the six values $2$ , $3$ , $7$ , $31$ , $211$ and $2311$ are classically known to be prime; this item does not verify that, and it is beside the point — one witness suffices, and no amount of small cases could establish a universal claim.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

FALSE: $n^{2} + n + 41$ is prime for every natural number $n$

Statement

False claim: for every $n \in N$ the integer

$ι (n)^{2} + ι (n) + 41$

is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ), where $ι : N \to Z$ is the embedding of The naturals embed in the integers and the square is the natural power of Powers $g^{n}$ : natural exponents in a monoid and integer exponents in a group, with $g^{0} = e$ in the commutative monoid $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ . As usual a numeral $k$ inside $Z$ means $ι (k)$ .

Witness: $n = 40$ . Here

$40^{2} + 40 + 41 = 1600 + 40 + 41 = 1681 = 41 \cdot 41,$

so $1681$ has the positive divisor $41$ , which is neither $1$ nor $1681$ : it is composite, not prime.

The failure is structural rather than accidental: $40^{2} + 40 = 40 \cdot 41$ , so the whole expression is $40 \cdot 41 + 41 = 41 \cdot 41$ .

Facts & Assumptions

Given: The integers $40$ , $41$ and $1681$ .

[L1]

[L2]

$g^{0} = 1$ and $g^{σ (k)} = g^{k} g$ in $(Z, \cdot, 1)$ , so $g^{2} = g \cdot g$ (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^{m n}$ for all $m, n \in Z$ , and $(g h)^{n} = g^{n} h^{n}$ when $g$ and $h$ commute, Semigroup and monoid, $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ ).

[L3]

$d ∣ a$ means $a = d c$ for some $c \in Z$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L5]

[L6]

The order on $Z$ is total, antisymmetric and transitive and is compatible with addition (The integers form a totally ordered ring, Order on the integers); $ι$ is injective and order preserving with image the nonnegative integers, $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers, Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann), Order on the natural numbers).

Refutation

technique · direct

1.1

$0 < 1$ , since $1 = ι (1)$ is nonnegative and differs from $0 = ι (0)$ by injectivity of $ι$ .

1.2

At $n = 40$ the expression equals $41 \cdot 41$ . By [L2], $40^{2} = 40 \cdot 40$ , and distributivity gives $40 \cdot 40 + 40 = 40 \cdot (40 + 1) = 40 \cdot 41$ ; adding $41$ and using distributivity again, $40 \cdot 41 + 41 = (40 + 1) \cdot 41 = 41 \cdot 41$ .

L2L5

1.3

Arithmetically $40 \cdot 40 = 1600$ , $1600 + 40 = 1640$ , $1640 + 41 = 1681$ , and $41 \cdot 41 = 1681$ ; so the value at $n = 40$ is $1681$ .

L5algebra

2.1

$41 ∣ 1681$ , since $1681 = 41 \cdot 41$ ; and $41 > 0$ .

step 1.2step 1.3L3

2.2

$41 \neq 1$ , because $41 - 1 = 40 > 0$ ; and $41 \neq 1681$ , because $1681 - 41 = 1640 > 0$ ; and $1681 > 1$ .

step 1.1step 1.3L6algebra

3.1

So $1681$ has a positive divisor other than $1$ and itself, hence is not prime; being greater than $1$ it is composite. The claim therefore fails at $n = 40$ .

step 2.1step 2.2L1∎

Remarks

Checking small cases proves nothing here, and that is the point of the item. The values at $n = 0, 1, \dots, 39$ are classically known to be prime — this is Euler's polynomial, and the fact is not verified above, since it is not needed for a refutation. A claim that survives forty consecutive tests and fails at the forty-first is exactly the situation a universal statement has to be proved out of, not tested out of.
The witness is not isolated. $n = 41$ fails for the same structural reason: $41^{2} + 41 + 41 = 41 \cdot (41 + 1 + 1) = 41 \cdot 43 = 1763$ , again divisible by $41$ and again neither $1$ nor itself. What both cases exploit is that $41$ divides the constant term, so it divides the whole value whenever it divides $n^{2} + n$ .
The refuted claim is about $N$ , which contains $0$ . At $n = 0$ the value is $41$ , so the claim is not vacuous at its first index; the witness is needed.

False statementConstruction: AI-adaptedVerification: AI-adaptedprecheck passverified 2026-08-03 (gpt-5.6-sol-codex-subscription)Open item page →

FALSE: every Fermat number $2^{2^{n}} + 1$ is prime

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$ in the commutative monoid $(Z, \cdot, 1)$ of $(Z, \cdot, 1)$ is a commutative monoid whose group of units is ${1, - 1}$ ; equivalently $u ∣ 1$ holds exactly for $u = 1$ and $u = - 1$ , and $ι : N \to Z$ is the embedding of The naturals embed in the integers; a numeral $k$ inside $Z$ means $ι (k)$ .

False claim: every Fermat number is prime (Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$ ). That is: for every $m \in N$ which is a power of two — meaning $ι (m) = 2^{k}$ for some $k \in N$ — the integer

$2^{m} + 1$

is prime.

Witness: $k = 5$ , so $m = 32$ and $ι (32) = 2^{5}$ . The integer $2^{32} + 1$ is not prime, because

$641 ∣ 2^{32} + 1,$

while $641$ is neither $1$ nor $2^{32} + 1$ .

Euler's verification is used below rather than a ten-digit division: $641$ is simultaneously $5 \cdot 2^{7} + 1$ and $2^{4} + 5^{4}$ , and those two readings together force $641$ to divide $2^{32} + 1$ . Congruence notation is not available at this point in the library, so every step is written as a divisibility statement with an explicit witness.

Facts & Assumptions

Given: The integers $2$ , $5$ , $641$ and the powers named below.

[L1]

[L2]

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

[L3]

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

[L4]

$d ∣ a$ means $a = d c$ for some $c \in Z$ ; divisibility is reflexive and linear, so $d ∣ a$ and $d ∣ b$ give $d ∣ a - b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ for some integer $q$ , Divisibility is reflexive and transitive on $Z$ , and is linear: if $d ∣ a$ and $d ∣ b$ then $d ∣ a x + b y$ for all integers $x, y$ ; also $d ∣ a$ implies $d ∣ a c$ , $- d ∣ a$ and $d ∣ - a$ ).

[L6]

$Z$ is a commutative ring: addition and multiplication are associative and commutative, $x \cdot 1 = x$ , multiplication distributes over addition, and every $x$ has an additive inverse; we write $u - v$ for $u + (- v)$ (The integers form a commutative ring, Arithmetic on the integers, The integers as equivalence classes of pairs of naturals).

[L7]

The order on $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); $ι$ is injective, preserves addition, multiplication and order, and has as image the nonnegative integers, with $ι (0) = 0$ , $ι (1) = 1$ (The naturals embed in the integers, Discreteness: $σ (n)$ is the immediate successor, The natural numbers $N$ (von Neumann), Order on the natural numbers, Addition of natural numbers).

[L8]

Induction on $N$ (The principle of mathematical induction).

Refutation

technique · direct

1.1

$0 < 1$ , and every integer $y > 0$ satisfies $y \geq 1$ : $y = ι (t)$ with $t \neq 0$ , so $1 \leq y$ because $ι$ preserves the order.

1.2

The small powers, by repeated doubling from [L2]: $2^{1} = 2$ , $2^{2} = 4$ , $2^{3} = 8$ , $2^{4} = 16$ , $2^{5} = 32$ , $2^{6} = 64$ , $2^{7} = 128$ , $2^{8} = 256$ , $2^{9} = 512$ , $2^{10} = 1024$ . Also $5^{2} = 25$ and $5^{4} = 25 \cdot 25 = 625$ .

L2L3L6algebra

2.1

$2^{t} \geq 1$ for every $t \in N$ : the set of such $t$ contains $0$ , since $2^{0} = 1$ , and if $2^{t} \geq 1$ then $2^{σ (t)} = 2^{t} \cdot 2$ has both factors $\geq 1 > 0$ , so the product is positive and hence $\geq 1$ by step 1.1. Induction finishes it.

step 1.1L2L7L8

2.2

$641 = 5 \cdot 2^{7} + 1$ and $641 = 2^{4} + 5^{4}$ : indeed $5 \cdot 128 = 640$ and $640 + 1 = 641$ , while $16 + 625 = 641$ .

step 1.2L6algebra

3.1

Put $u : = 5 \cdot 2^{7}$ , so $u = 640$ and $u + 1 = 641$ ; hence $641 ∣ u + 1$ .

step 2.2L4

3.2

$2^{32} + 1 > 641$ : by [L3], $2^{32} = 2^{10} \cdot 2^{22} = 1024 \cdot 2^{22}$ , and $2^{22} \geq 1 > 0$ , so $2^{32} \geq 1024 > 641$ . Hence $641 \neq 2^{32} + 1$ ; also $641 \neq 1$ and $641 > 0$ , and $2^{32} + 1 > 1$ .

step 2.1step 1.2L3L7algebra

4.1

$u^{4} - 1 = (u + 1) (u^{3} - u^{2} + u - 1)$ , by expanding the right side with distributivity: the terms $- u^{3} + u^{3}$ , $u^{2} - u^{2}$ and $- u + u$ cancel. Hence $641 ∣ u^{4} - 1$ .

step 3.1L2L4L6

5.1

$u^{4} = (5 \cdot 2^{7})^{4} = 5^{4} (2^{7})^{4} = 5^{4} \cdot 2^{28}$ , using [L3] with $5$ and $2^{7}$ commuting and $7 \cdot 4 = 28$ . So $641 ∣ 5^{4} \cdot 2^{28} - 1$ .

step 4.1L3L6

6.1

From step 2.2, $5^{4} = 641 - 2^{4}$ , so $5^{4} \cdot 2^{28} - 1 = (641 - 2^{4}) 2^{28} - 1 = 641 \cdot 2^{28} - 2^{4} 2^{28} - 1 = 641 \cdot 2^{28} - (2^{32} + 1)$ , using $2^{4} 2^{28} = 2^{32}$ from [L3].

step 2.2step 5.1L3L6

7.1

Now $641 ∣ 641 \cdot 2^{28}$ , and $641 ∣ 641 \cdot 2^{28} - (2^{32} + 1)$ by steps 5.1 and 6.1; subtracting, linearity gives $641 ∣ 2^{32} + 1$ .

step 5.1step 6.1L4L6

8.1

So $2^{32} + 1$ has a positive divisor other than $1$ and itself, hence is not prime, and being greater than $1$ it is composite. Since $ι (32) = 2^{5}$ by step 1.2, the natural number $32$ is a power of two and the claim fails there.

step 1.2step 7.1step 3.2L1L7∎

Remarks

The first five Fermat numbers are prime, which is why the claim was believed. For $k = 0, 1, 2, 3, 4$ the values are $3$ , $5$ , $17$ , $257$ and $65537$ , all classically known to be prime; that is not verified here, since the refutation needs only the single witness at $k = 5$ . Fermat conjectured primality for all $k$ ; Euler produced the divisor $641$ .
Why the two readings of $641$ are both needed. $641 = 5 \cdot 2^{7} + 1$ is what makes $641$ divide $5^{4} 2^{28} - 1$ , and $641 = 2^{4} + 5^{4}$ is what converts that into a statement about $2^{32} + 1$ . Either alone says nothing.
Nothing is claimed about the cofactor. The refutation needs only that $641$ is a divisor of $2^{32} + 1$ lying strictly between $1$ and $2^{32} + 1$ ; the complementary factor is neither computed nor analysed here, and its primality is not asserted.

Primes and Factorisation: Examples and Counterexamples

1 · Prerequisites

2 · Summary

3 · Logical flowchart

4 · Definitions, theorems and proofs

5 · Examples, counterexamples and false statements

360=23⋅32⋅5360=23⋅32⋅5 and 84=22⋅3⋅784=22⋅3⋅7, with gcd⁡(360,84)=12gcd(360,84)=12 and lcm⁡(360,84)=2520lcm(360,84)=2520 read off the exponents

Example

Facts & Assumptions

Verification

Remarks

22 is prime, and it is the only even prime: every even integer n>2n>2 is composite

Example

Facts & Assumptions

Verification

Remarks

No rational squares to 33 or to 66, and none cubes to 22: three instances of the rational-root corollary

Example

Facts & Assumptions

Verification

Remarks

For every n∈Nn∈N there are nn consecutive composite integers: with N:=∏j<n(j+2)N:=∏j<n​(j+2), each of N+2,…,N+n+1N+2,…,N+n+1 is composite

Example

Facts & Assumptions

Verification

Remarks

In the multiplicative monoid H={1,4,7,10,… }H={1,4,7,10,…} of positive integers one more than a multiple of 33, the element 100100 has two genuinely different factorisations into irreducibles, 4⋅254⋅25 and 10⋅1010⋅10

Statement refuted

Facts & Assumptions

Counterexample

Remarks

If 11 were admitted as a prime, uniqueness would fail: 6=2⋅3=1⋅2⋅3=1⋅1⋅2⋅36=2⋅3=1⋅2⋅3=1⋅1⋅2⋅3, lists of different lengths that no permutation matches

Statement refuted

Facts & Assumptions

Counterexample

Remarks

FALSE: for every finite list p0,…,pn−1p0​,…,pn−1​ of distinct primes, p0⋯pn−1+1p0​⋯pn−1​+1 is prime

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: n2+n+41n2+n+41 is prime for every natural number nn

Statement

Facts & Assumptions

Refutation

Remarks

FALSE: every Fermat number 22n+122n+1 is prime

Statement

Facts & Assumptions

Refutation

Remarks

Sources

$360 = 2^{3} \cdot 3^{2} \cdot 5$ and $84 = 2^{2} \cdot 3 \cdot 7$ , with $\gcd (360, 84) = 12$ and $lcm (360, 84) = 2520$ read off the exponents

$2$ is prime, and it is the only even prime: every even integer $n > 2$ is composite

No rational squares to $3$ or to $6$ , and none cubes to $2$ : three instances of the rational-root corollary

For every $n \in N$ there are $n$ consecutive composite integers: with $N : = \prod_{j < n} (j + 2)$ , each of $N + 2, \dots, N + n + 1$ is composite

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$

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

FALSE: for every finite list $p_{0}, \dots, p_{n - 1}$ of distinct primes, $p_{0} \dots p_{n - 1} + 1$ is prime

FALSE: $n^{2} + n + 41$ is prime for every natural number $n$

FALSE: every Fermat number $2^{2^{n}} + 1$ is prime