Prime and composite integers: $p$ is prime when $p > 1$ and its only positive divisors are $1$ and $p$

Let $p \in \mathbb{Z}$ (The integers as equivalence classes of pairs of naturals), ordered as in Order on the integers, with divisibility as in Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$. Then $p$ is prime when

$p > 1 \qquad \text{and} \qquad d \mid p \ \text{ with } \ d > 0 \ \text{ force } \ d = 1 \ \text{ or } \ d = p .$

In words: $p$ exceeds $1$, and its only positive divisors are $1$ and $p$. An integer $n$ with $n > 1$ that is not prime is composite; unfolding the definition, $n$ is composite exactly when $n > 1$ and $n$ has a positive divisor $d$ with $d \ne 1$ and $d \ne n$.

Numerals. For $k \in \mathbb{N}$ the symbol $k$ inside $\mathbb{Z}$ means $\iota(k)$, the embedding of The naturals embed in the integers; in particular $0$ and $1$ are the ring constants of Arithmetic on the integers.

Boundary values, stated rather than assumed. $\mathbb{N}$ contains $0$ (The natural numbers $\mathbb{N}$ (von Neumann)) and $\mathbb{Z}$ contains $0$, $1$ and the negatives, so the small cases are recorded explicitly. The clause $p > 1$ decides all of them at once:

• $1$ is not prime, since $1 > 1$ is false, and not composite either, since composite also requires $n > 1$.
• $0$ is not prime, since $0 > 1$ is false. This is decided by the size clause alone and not by counting divisors: every integer divides $0$ (Divisibility in $\mathbb{Z}$: $d \mid a$ when $a = dq$ for some integer $q$), so the divisor condition is not what rules $0$ out.
• Every negative integer is neither prime nor composite, again because $p > 1$ fails. So a prime is in particular positive, and $-2$, $-3$, $-5$ are not primes in this library, though each is $-1$ times one.

Thus "prime" and "composite" between them classify exactly the integers greater than $1$, and nothing else.

The same condition read over all divisors. For $p > 1$ the following are equivalent:

1. the only positive divisors of $p$ are $1$ and $p$;
2. the only divisors of $p$ are $1$, $-1$, $p$ and $-p$.

That 2 implies 1 is immediate, since of those four only $1$ and $p$ are positive ($p > 1 > 0$, so $-1 < 0$ and $-p < 0$). For the converse let $d \mid p$. Since $p > 1$ we have $p \ne 0$, so $d \ne 0$ by If $d \mid a$ and $a \ne 0$ then $d \ne 0$ and $|d| \le |a|$; hence the set of divisors of a nonzero integer is bounded above by $|a|$; and $|d| \mid p$, because $|d|$ is $d$ or $-d$ (The absolute value $|a|$ of an integer) and those two divide $p$ together (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$). Also $|d| \ge 0$ and $|d| \ne 0$ (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$), so $|d| > 0$ and clause 1 gives $|d| = 1$ or $|d| = p$. If $|d| = 1$ then $d = 1$ or $d = -1$, by the case split defining $|d|$; and if $|d| = p = |p|$ then $d = up$ for a unit $u \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$), that is $d = p$ or $d = -p$. Both readings are used below without further comment.

Why $1$ is excluded, and it is not a matter of taste. The exclusion is forced by 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)$, proved on this page: if $1$ counted as a prime, a factorisation could be padded with any number of factors $1$, so lists of different lengths would represent the same integer and no permutation could match them. Existence of a factorisation would survive the change; it is uniqueness alone that fixes the convention, and the explicit witness is recorded on the companion page.

• The witness for the exclusion of $1$. The companion page carries it explicitly: If $1$ were admitted as a prime, uniqueness would fail: $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$, lists of different lengths that no permutation matches ↗ displays $6 = 2 \cdot 3 = 1 \cdot 2 \cdot 3 = 1 \cdot 1 \cdot 2 \cdot 3$, three lists of lengths $2$, $3$ and $4$ that no permutation can match.

• No ring vocabulary is used here, deliberately. In a general commutative ring one distinguishes a prime element from an irreducible element, and in $\mathbb{Z}$ the two notions coincide; that dictionary needs the definition of a ring, which this library develops far above this page, so it is not stated here and nothing below depends on it. What is proved here is the arithmetic content of the coincidence: 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$ shows that for $p > 1$ the definition above is equivalent to the property that $p \mid ab$ forces $p \mid a$ or $p \mid b$.

• Primality is about $p$; coprimality is about a pair. Coprime integers: $\gcd(a,b) = 1$ is the condition $\gcd(a,b) = 1$ on two integers and needs no primality at all — $4$ and $9$ are coprime and neither is prime. The bridge in the other direction is For a prime $p$ and any integer $a$, $\gcd(p,a)$ is $p$ when $p \mid a$ and $1$ otherwise; so $p \nmid a$ makes $p$ and $a$ coprime, the next item, and it is the only place on this page where primality is converted into coprimality.