This section develops the integers
We take the basic algebraic properties of for granted: addition and
multiplication are associative and commutative, and multiplication distributes
over addition; the integers and are identities for addition and
multiplication respectively; every integer has a negative ; there
are no zero divisors (if
Every nonempty subset
The well-ordering principle is logically equivalent to the principle of mathematical induction; we use both freely. The existence results below (division with remainder, termination of the Euclidean algorithm, Bézout’s identity, prime factorisation) all rest on it.
Let
The following consequences are used throughout, usually without citation.
Let
If
If
If
If
Part (1) is immediate:
Restricted to the natural numbers, where (5) becomes
Let
Existence. Consider the set
First,
Uniqueness. Suppose
The hypothesis
We denote the remainder produced by the division algorithm by
A common divisor of integers and is an integer with
The greatest common divisor is well defined when
Let
In particular, if
It suffices to show the two pairs and
Let
The sequence
The remainders
using
Compute :
The last nonzero remainder is , so
The number of division steps of the Euclidean algorithm for inputs
Back-substitution through the equations of the Euclidean algorithm expresses the gcd as an integer linear combination of the inputs.
Let
Moreover is the smallest positive integer expressible in the form
Let
Since
We claim that divides every element of . Indeed, let
The proof yields a characterisation of the gcd that is independent of the
order :
The Bézout coefficients
since the added terms and cancel; and
these are all the solutions. To prove completeness, observe first that
and are coprime: a common divisor of both makes a
common divisor of and , so
There is an algorithm that, on input
Alongside the remainder sequence of Theorem 2.8, maintain two auxiliary sequences and with the invariant
Initialise (taking
so (2.5) holds for
Then
so induction preserves (2.5). When the algorithm terminates
with
Run the extended algorithm on
For instance, row is row minus
Thus
Let
If
If
If
(1) By Bézout there are
(2) Write
(3) By Bézout,
which exhibits as an integer combination of and . Hence divides , so it equals . □
An integer
Excluding from the primes is necessary for factorisation into primes to be unique, since otherwise arbitrarily many factors of could be inserted. The property of primes on which uniqueness rests is the prime case of Euclid’s lemma.
Let be prime and
The only positive divisors of are and , so
Every integer
and this factorisation is unique up to the order of the factors. Equivalently, there is a unique expression
Existence. Suppose, for contradiction, that some integer
Uniqueness. Suppose
are two factorisations of the same integer into primes. The argument proceeds
by induction on . If
where the hat denotes omission. By the inductive hypothesis these two
factorisations agree up to order, with
Existence rests on the order structure (well-ordering); uniqueness rests on Euclid’s lemma, hence on Bézout, hence on the division algorithm. In some number systems with a division-like structure, Euclid’s lemma fails and factorisation into irreducibles is not unique.
Congruence formalises the arithmetic of remainders. Fix an integer
Let
if
The two formulations agree: if
Fix
Consequently
Reflexivity (
and
so both
Because congruence is an equivalence relation, it partitions into disjoint congruence classes (also called residue classes).
The congruence class (or residue class) of modulo is
We write the set of all congruence classes as
By the division algorithm every integer is congruent modulo to exactly
one of
Division is the inverse of multiplication, so division of remainders modulo
reduces to determining the for which the congruence
Let
The definition is well posed on classes: by
Proposition 2.21, if
Let
Suppose
Conversely, if is a unit, say
Uniqueness: if
Consider the computation of . The extended Euclidean algorithm on :
so
Hence
Later sections use the number of units.
Euler’s totient function is the number of integers
with
The two counts agree: the classes of
We have
Division by modulo is therefore multiplication by the inverse
class . By Theorem 2.24 that inverse exists
precisely when