TheoremStatement: AI-adaptedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)audited 2026-07-28

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.

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

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

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.

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 74 results over 25 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources

Fundamental theorem of arithmetic (Wikipedia) (standard reference, not scraped)
Number Theory: In Context — Fundamental Theorem of Arithmetic (standard reference, not scraped)

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