This section develops the integers
We take the basic algebraic properties of Z for granted: addition and
multiplication are associative and commutative, and multiplication distributes
over addition; the integers 0 and 1 are identities for addition and
multiplication respectively; every integer a has a negative − a ; 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
| a = b q + r, 0 ≤ r < b . |
Existence. Consider the set
| S = { a − b k : k ∈ Z, a − b k ≥ 0 } ⊆ N . |
First,
Uniqueness. Suppose
The hypothesis
We denote the remainder r produced by the division algorithm by
A common divisor of integers a and b is an integer d with
The greatest common divisor is well defined when
Let
| gcd (a, b) = gcd (b, a − q b) . |
In particular, if
It suffices to show the two pairs (a, b) and
Let
| r i − 1 = r i q i + r i + 1, 0 ≤ r i + 1 < r i . |
The sequence
The remainders
| gcd (a, b) = gcd (r 0, r 1) = gcd (r 1, r 2) = ⋯ = gcd (r n, r n + 1) = gcd (r n, 0) = r n, |
using
Compute gcd (1071, 462) :
| 1071 | = 2 ⋅ 462 + 147, | ||
| 462 | = 3 ⋅ 147 + 21, | ||
| 147 | = 7 ⋅ 21 + 0 . |
The last nonzero remainder is 21 , 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
| a u + b v = d . |
Moreover d is the smallest positive integer expressible in the form
| { a x + b y : x, y ∈ Z } = d Z = { k d : k ∈ Z } . |
Let
| m s + n t = a (m x 1 + n x 2) + b (m y 1 + n y 2) ∈ I . |
Since
We claim that g divides every element of I . Indeed, let
The proof yields a characterisation of the gcd that is independent of the
order ≤ :
The Bézout coefficients
| a (u + k b d) + b (v − k a d) = d, |
since the added terms k a b d and − k a b d cancel; and
these are all the solutions. To prove completeness, observe first that
a / d and b / d are coprime: a common divisor e of both makes d e a
common divisor of a and b , so
There is an algorithm that, on input
Alongside the remainder sequence of Theorem 2.8, maintain two auxiliary sequences (s i) and (t i) with the invariant
| r i = a s i + b t i for all i . |
Initialise (taking
| r 0 = a, s 0 = 1, t 0 = 0 ; r 1 = b, s 1 = 0, t 1 = 1, |
so (2.5) holds for
| s i + 1 = s i − 1 − q i s i, t i + 1 = t i − 1 − q i t i . |
Then
| a s i + 1 + b t i + 1 = (a s i − 1 + b t i − 1) − q i (a s i + b t i) = r i − 1 − q i r i = r i + 1, |
so induction preserves (2.5). When the algorithm terminates
with
Run the extended algorithm on
| i r i s i t i 0 1071 1 0 1 462 0 1 2 147 1 − 2 3 21 − 3 7 4 0 22 − 51 |
For instance, row 2 is row 0 minus
| 1071 ⋅ (− 3) + 462 ⋅ 7 = − 3213 + 3234 = 21 . |
Thus
Let
If
If
If
(1) By Bézout there are
(2) Write
(3) By Bézout,
| 1 = (a x 1 + b y 1) (a x 2 + c y 2) = a (a x 1 x 2 + x 1 c y 2 + b y 1 x 2) ⏟ ∈ Z + b c (y 1 y 2), |
which exhibits 1 as an integer combination of a and b c . Hence gcd (a, b c) divides 1 , so it equals 1 . □
An integer
Excluding 1 from the primes is necessary for factorisation into primes to be unique, since otherwise arbitrarily many factors of 1 could be inserted. The property of primes on which uniqueness rests is the prime case of Euclid’s lemma.
Let p be prime and
The only positive divisors of p are 1 and p , so
Every integer
| n = p 1 p 2 ⋯ p k, |
and this factorisation is unique up to the order of the factors. Equivalently, there is a unique expression
| n = p 1 e 1 p 2 e 2 ⋯ p r e r, p 1 < p 2 < ⋯ < p r prime, e i ≥ 1 . |
Existence. Suppose, for contradiction, that some integer
Uniqueness. Suppose
| p 1 p 2 ⋯ p k = q 1 q 2 ⋯ q l |
are two factorisations of the same integer into primes. The argument proceeds
by induction on k . If
| p 2 ⋯ p k = q 1 ⋯ q j ^ ⋯ q l, |
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
| a ≡ b (mod n), |
if
The two formulations agree: if
Fix
| a + b ≡ a ′ + b ′ (mod n), a b ≡ a ′ b ′ (mod n) . |
Consequently
Reflexivity (
| (a + b) − (a ′ + b ′) = n (s + t), |
and
| a b − a ′ b ′ = a b − a ′ b + a ′ b − a ′ b ′ = (a − a ′) b + a ′ (b − b ′) = n (s b + a ′ t), |
so both
Because congruence is an equivalence relation, it partitions Z into disjoint congruence classes (also called residue classes).
The congruence class (or residue class) of a modulo n is
| [a] n = { b ∈ Z : b ≡ a (mod n) } = { a + k n : k ∈ Z } = a + n Z . |
We write the set of all congruence classes as
| Z / n Z = { [a] n : a ∈ Z } . |
By the division algorithm every integer is congruent modulo n to exactly
one of
Division is the inverse of multiplication, so division of remainders modulo
n reduces to determining the a for which the congruence
Let
| (Z / n Z) × = { [a] n : [a] n is a unit } . |
The definition is well posed on classes: by
Proposition 2.21, if
Let
Suppose
Conversely, if [a] n is a unit, say
Uniqueness: if
Consider the computation of [17] 43 − 1 . The extended Euclidean algorithm on (43, 17) :
| 43 | = 2 ⋅ 17 + 9, | ||
| 17 | = 1 ⋅ 9 + 8, | ||
| 9 | = 1 ⋅ 8 + 1, | ||
| 8 | = 8 ⋅ 1 + 0, |
so
| 1 = 9 − 8 = 9 − (17 − 9) = 2 ⋅ 9 − 17 = 2 (43 − 2 ⋅ 17) − 17 = 2 ⋅ 43 − 5 ⋅ 17 . |
Hence
Later sections use the number of units.
Euler’s totient function φ (n) is the number of integers a
with
The two counts agree: the classes of
We have
Division by a modulo n is therefore multiplication by the inverse
class [a] n − 1 . By Theorem 2.24 that inverse exists
precisely when