CorollaryStatement: AI-adaptedProof: AI-generatedprecheck 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.

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$

Statement

Let $p \in 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 Z$ , $p ∣ a b$ implies $p ∣ a$ or $p ∣ b$ (Divisibility in $Z$ : $d ∣ a$ when $a = d q$ 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 ∣ 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$ ).

[L3]

$u ∣ v$ and $v ∣ u$ together hold exactly when $∣ u ∣ = ∣ v ∣$ , and exactly when $v = w u$ for a unit $w \in {1, - 1}$ (For integers $a$ and $b$ the following are equivalent: $a ∣ b$ and $b ∣ a$ ; $b = u a$ for a unit $u$ ; $∣ a ∣ = ∣ b ∣$ . Being associates is an equivalence relation whose class of $a$ is ${a, - a}$ , $(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$ ).

[L4]

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

[L5]

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

[L6]

$d ∣ u$ means $u = d q$ for some $q \in Z$ ; divisibility is reflexive (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: 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 $Z$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \leq y$ together with $x \neq y$ (The integers form a totally ordered ring, Order on the integers).

[L9]

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

[L10]

$∣ x ∣ = x$ when $x \geq 0$ and $∣ x ∣ = - x$ when $x < 0$ ; $∣ 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$ ).

Proof

technique · direct

1.1

$0 < 1$ : $1 = ι (1)$ lies in the image of $ι$ , so $1 \geq 0$ , and $1 \neq 0$ because $ι$ is injective and $0 \neq 1$ in $N$ . Adding $- 1$ throughout gives $- 1 < 0$ .

L7L8L9

1.2

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

1.3

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

L6choose

2.1

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

step 1.1L8

2.2

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

step 1.3L6

3.1

Suppose $p ∣ d$ . Since also $d ∣ p$ , [L3] gives $∣ d ∣ = ∣ p ∣$ , hence $d = w p$ 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 ∣ c$ , and fix $e$ with $c = p e$ . Then $1 \cdot p = p = d c = d (p e) = (d e) \cdot p$ , and $p \neq 0$ , so cancellation gives $d e = 1$ . Hence $d ∣ 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 ∣ a$ for every $a$ , and so does $p = 0$ , because $0 ∣ a b$ forces $a b = 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 $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.

Depends on

Used by

Dependency tree · two levels

52 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Euclid's lemma (Wikipedia) (standard reference, not scraped)
Prime number (Wikipedia) (standard reference, not scraped)
Neil Donaldson, Math 180A notes: Unique factorisation (standard reference, not scraped)

For an integer p>1p>1: pp is prime if and only if, for all integers aa and bb, p∣abp∣ab implies p∣ap∣a or p∣bp∣b