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.

For an integer $p > 1$ : $p$ is prime if and only if, for all integers $a$ and $b$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$

Statement

Let $p \in \mathbb{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 \mathbb{Z}$ , $p \mid ab$ implies $p \mid a$ or $p \mid b$ (Divisibility in $\mathbb{Z}$ : $d \mid a$ when $a = dq$ 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 \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$ ).

[L3]

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

[L4]

$u \mid 1$ exactly when $u = 1$ or $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$ ).

[L5]

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

[L6]

$d \mid u$ means $u = dq$ for some $q \in \mathbb{Z}$ ; divisibility is reflexive (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$ ).

[L7]

$\mathbb{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 $\mathbb{Z}$ is total, antisymmetric and transitive and is compatible with addition; $x < y$ means $x \le y$ together with $x \ne y$ (The integers form a totally ordered ring, Order on the integers).

[L9]

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, The natural numbers $\mathbb{N}$ (von Neumann)).

[L10]

$|x| = x$ when $x \ge 0$ and $|x| = -x$ when $x < 0$ ; $|x| \ge 0$ (The absolute value $|a|$ of an integer, Absolute value in $\mathbb{Z}$ : $|a| \ge 0$ ; $|a| = 0$ exactly when $a = 0$ ; $|-a| = |a|$ ; $|ab| = |a|\,|b|$ ; $-|a| \le a \le |a|$ ; and $|a| \le c$ exactly when $-c \le a \le c$ ).

Proof

technique · direct

1.1

$0 < 1$ : $1 = \iota(1)$ lies in the image of $\iota$ , so $1 \ge 0$ , and $1 \ne 0$ because $\iota$ is injective and $0 \ne 1$ in $\mathbb{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 \mathbb{Z}$ with $p = dc$ .

L6choose

2.1

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

step 1.1L8

2.2

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

step 1.3L6

3.1

Suppose $p \mid d$ . Since also $d \mid p$ , [L3] gives $|d| = |p|$ , hence $d = wp$ 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 \mid c$ , and fix $e$ with $c = pe$ . Then $1 \cdot p = p = dc = d(pe) = (de) \cdot p$ , and $p \ne 0$ , so cancellation gives $de = 1$ . Hence $d \mid 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 \mid a$ for every $a$ , and so does $p = 0$ , because $0 \mid ab$ forces $ab = 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 $\mathbb{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

For every integer n>1, nℤ is a maximal ideal of ℤ if and only if n is prime Example

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 84 results over 29 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)
Prime number (Wikipedia) (standard reference, not scraped)
Neil Donaldson, Math 180A notes: Unique factorisation (standard reference, not scraped)

For an integer p>1p > 1p>1: ppp is prime if and only if, for all integers aaa and bbb, p∣abp \mid abp∣ab implies p∣ap \mid ap∣a or p∣bp \mid bp∣b