Engineering / Mathematics — Integer Foundations
Divisibility and Primality
Divisibility of integers, the definition of primes and composites, and the basic properties that support every later result in elementary number theory.
Executive summary
Divisibility is the primitive relation of number theory. Everything else — congruence, factorisation, the structure of the integers modulo n — is defined in terms of it.
The definition is deceptively simple, and the properties that follow are elementary, but they are the foundation on which unique factorisation and the entire theory of the integers rests.
Learning objectives
- State the divisibility relation precisely and derive its basic properties.
- Distinguish primes, composites and units correctly, including edge cases.
- Explain why 1 is excluded from the primes.
01The divisibility relation
Divides
For integers a and b, we say a divides b, written a | b, if there exists an integer c with b = ac.
We then call a a divisor of b, and b a multiple of a.
Note what the definition does not require. It does not require a to be non-zero, and it does not require either number to be positive. This matters at the edges: every integer divides 0, since 0 = a · 0, while 0 divides only itself.
- Reflexive:
a | afor every a. - Transitive: if
a | bandb | cthena | c. - Linear: if
a | banda | cthena | (bx + cy)for all integers x, y. - Bounding: if
a | bandb ≠ 0then|a| ≤ |b|.
02Units, primes and composites
An integer whose only divisors are ±1 and itself, up to sign, is the atomic object of the theory. Getting the definition right requires care about two exceptional cases.
Unit, prime, composite
A unit is an integer dividing 1; in Z the units are exactly ±1.
An integer n > 1 is prime if its only positive divisors are 1 and n.
An integer n > 1 that is not prime is composite; equivalently n = ab with 1 < a, b < n.
The number 0 is neither prime nor composite: it is greater than no positive bound and is divisible by everything.
03Every integer above one has a prime divisor
Existence of a prime divisor
Every integer n > 1 has at least one prime divisor.
Proof sketch. Consider the set of divisors of n exceeding 1. It is non-empty, since n belongs to it, so by well-ordering it has a least element p. If p were composite it would have a divisor strictly between 1 and p, which would also divide n and contradict minimality. So p is prime.
This is the first genuine theorem of the subject and its proof is the template for many that follow: take the least element of a non-empty set of positive integers, and derive a contradiction from the assumption that it is not atomic.
The immediate corollary — every integer greater than 1 is a product of primes — follows by induction, and is the existence half of the fundamental theorem of arithmetic. The uniqueness half is substantially harder and requires the theory of greatest common divisors.
04Euclid's theorem on the infinitude of primes
Infinitude of primes
There are infinitely many primes.
Proof sketch. Suppose the primes were exactly p₁, ..., pₖ. Form N = p₁···pₖ + 1. Then N > 1, so it has a prime divisor p. But p is one of the listed primes, so p divides the product, and since it also divides N it divides their difference, which is 1 — impossible.
The result says nothing about how densely primes occur. That question — how many primes lie below a given bound — is the subject of the distribution of primes stream, and its answer required nineteenth-century analysis rather than Euclid's elementary argument.
05Frequently asked questions
Why does every integer divide zero?
Because 0 = a · 0 for any a, so the definition is satisfied with c = 0. This is not a degenerate special case to be patched around; it is what makes the set of multiples of a into an ideal, which is the structure that unique factorisation ultimately depends on.
Is 1 prime in any convention?
It was in some nineteenth-century treatments, and the resulting exceptions to unique factorisation are exactly why the convention was abandoned. In modern algebra the correct general statement is that primes and units are disjoint classes in any integral domain.
Does Euclid's proof give an efficient way to find new primes?
No. The number formed is astronomically large after a few steps and factoring it to extract a new prime is harder than finding primes by any other means. The proof is an existence argument, not an algorithm.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 1-4.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.