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.1L7L8L9

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

1.2L2

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

1.3L6choose

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

2.1step 1.1L8

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

2.2step 1.3L6

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

3.1step 2.1step 1.3step 2.2L3L7L8L10

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

3.2step 1.1step 2.1step 1.3step 2.2L4L5L6L7L8

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

4.1step 2.2step 3.1step 3.2L1

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.

5.1step 1.2step 4.1∎

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

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.

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

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

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

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources

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$