CorollaryStatement: 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.

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

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

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 80 results over 27 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

Euclid's lemma (Wikipedia) (standard reference, not scraped)
Number Theory: In Context — Fundamental Theorem of Arithmetic (standard reference, not scraped)

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