Course 311: Michaelmas Term 2005 Part I: Topics in Number Theory

D. R. Wilkins

Copyright \begin{matrix}c \\ ◯ \end{matrix} David R. Wilkins 1997–2005

Contents

1 Topics in Number Theory 2 1.1 Subgroups of the Integers . . . . . . . . . . . . . . . . . . . . 2 1.2 Greatest Common Divisors . . . . . . . . . . . . . . . . . . . . 2 1.3 The Euclidean Algorithm . . . . . . . . . . . . . . . . . . . . . 3 1.4 Prime Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.5 The Fundamental Theorem of Arithmetic . . . . . . . . . . . . 5 1.6 The Infinitude of Primes . . . . . . . . . . . . . . . . . . . . . 6 1.7 Congruences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.8 The Chinese Remainder Theorem . . . . . . . . . . . . . . . . 8 1.9 The Euler Totient Function . . . . . . . . . . . . . . . . . . . 9 1.10 The Theorems of Fermat, Wilson and Euler . . . . . . . . . . 11 1.11 Solutions of Polynomial Congruences . . . . . . . . . . . . . . 13 1.12 Primitive Roots . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.13 Quadratic Residues . . . . . . . . . . . . . . . . . . . . . . . . 16 1.14 Quadratic Reciprocity . . . . . . . . . . . . . . . . . . . . . . 21 1.15 The Jacobi Symbol . . . . . . . . . . . . . . . . . . . . . . . . 22

1 Topics in Number Theory

1.1 Subgroups of the Integers

A subset S of the set ℤ of integers is a subgroup of ℤ if 0 ∈ S, −x ∈ S and x + y ∈ S for all x ∈ S and y ∈ S.

It is easy to see that a non-empty subset S of ℤ is a subgroup of ℤ if and only if x − y ∈ S for all x ∈ S and y ∈ S.

Let m be an integer, and let mℤ = {mn : n ∈ ℤ}. Then mℤ (the set of integer multiples of m) is a subgroup of ℤ.

Theorem 1.1 Let S be a subgroup of ℤ. Then S = mℤ for some nonnegative integer m.

Proof If S = {0} then S = mℤ with m = 0. Suppose that S ≠ {0}. Then S contains a non-zero integer, and therefore S contains a positive integer (since −x ∈ S for all x ∈ S). Let m be the smallest positive integer belonging to S. A positive integer n belonging to S can be written in the form n = qm + r, where q is a positive integer and r is an integer satisfying 0 ≤ r < m. Then qm ∈ S (because qm = m + m + ⋯ + m). But then r ∈ S, since r = n − qm. It follows that r = 0, since m is the smallest positive integer in S. Therefore n = qm, and thus n ∈ mℤ. It follows that S = mℤ, as required.

1.2 Greatest Common Divisors

Definition Let a_{1}, a_{2}, …, a_{r} be integers, not all zero. A common divisor of a_{1}, a_{2}, …, a_{r} is an integer that divides each of a_{1}, a_{2}, …, a_{r}. The greatest common divisor of a_{1}, a_{2}, …, a_{r} is the greatest positive integer that divides each of a_{1}, a_{2}, …, a_{r}. The greatest common divisor of a_{1}, a_{2}, …, a_{r} is denoted by (a_{1}, a_{2}, …, a_{r}).

Theorem 1.2 Let a_{1}, a_{2}, …, a_{r} be integers, not all zero. Then there exist integers u_{1}, u_{2}, …, u_{r} such that

(a_{1}, a_{2}, …, a_{r}) = u_{1}a_{1} + u_{2}a_{2} + ⋯ + u_{r}a_{r}.

where (a_{1}, a_{2}, …, a_{r}) is the greatest common divisor of a_{1}, a_{2}, …, a_{r}.

Proof Let S be the set of all integers that are of the form

n_{1}a_{1} + n_{2}a_{2} + ⋯ + n_{r}a_{r}

for some n_{1}, n_{2}, …, n_{r} ∈ ℤ. Then S is a subgroup of ℤ. It follows that S = mℤ for some non-negative integer m (Theorem 1.1). Then m is a common divisor of a_{1}, a_{2}, …, a_{r}, (since a_{i} ∈ S for i = 1, 2, …, r). Moreover any common divisor of a_{1}, a_{2}, …, a_{r} is a divisor of each element of S and is therefore a divisor of m. It follows that m is the greatest common divisor of a_{1}, a_{2}, …, a_{r}. But m ∈ S, and therefore there exist integers u_{1}, u_{2}, …, u_{r} such that

(a_{1}, a_{2}, …, a_{r}) = u_{1}a_{1} + u_{2}a_{2} + ⋯ + u_{r}a_{r},

as required.

Definition Let a_{1}, a_{2}, …, a_{r} be integers, not all zero. If the greatest common divisor of a_{1}, a_{2}, …, a_{r} is 1 then these integers are said to be coprime. If integers a and b are coprime then a is said to be coprime to b. (Thus a is coprime to b if and only if b is coprime to a.)

Corollary 1.3 Let a_{1}, a_{2}, …, a_{r} be integers, not all zero, Then a_{1}, a_{2}, …, a_{r} are coprime if and only if there exist integers u_{1}, u_{2}, …, u_{r} such that

1 = u_{1}a_{1} + u_{2}a_{2} + ⋯ + u_{r}a_{r}.

Proof If a_{1}, a_{2}, …, a_{r} are coprime then the existence of the required integers u_{1}, u_{2}, …, u_{r} follows from Theorem 1.2. On the other hand, if there exist integers u_{1}, u_{2}, …, u_{r} with the required property then any common divisor of a_{1}, a_{2}, …, a_{r} must be a divisor of 1, and therefore a_{1}, a_{2}, …, a_{r} must be coprime.

1.3 The Euclidean Algorithm

Let a and b be positive integers with a > b. Let r_{0} = a and r_{1} = b. If b does not divide a then let r_{2} be the remainder on dividing a by b. Then a = q_{1}b + r_{2}, where q_{1} and r_{2} are positive integers and 0 < r_{2} < b. If r_{2} does not divide b then let r_{3} be the remainder on dividing b by r_{2}. Then b = q_{2}r_{2} + r_{3}, where q_{2} and r_{3} are positive integers and 0 < r_{3} < r_{2}. If r_{3} does not divide r_{2} then let r_{4} be the remainder on dividing r_{2} by r_{3}. Then r_{2} = q_{3}r_{3} + r_{4}, where q_{3} and r_{4} are positive integers and 0 < r_{4} < r_{3}. Continuing in this fashion, we construct positive integers r_{0}, r_{1}, …, r_{n} such that r_{0} = a, r_{1} = b and r_{i} is the remainder on dividing r_{i−2} by r_{i−1} for i = 2, 3, …, n. Then r_{i−2} = q_{i−1}r_{i−1} + r_{i}, where q_{i−1} and r_{i} are positive integers and 0 < r_{i} < r_{i−1}. The algorithm for constructing the positive integers r_{0}, r_{1}, …, r_{n} terminates when r_{n} divides r_{n−1}. Then r_{n−1} = q_{n}r_{n} for some positive integer q_{n}. (The algorithm must clearly terminate in a finite number of steps, since r_{0} > r_{1} > r_{2} > ⋯ > r_{n}.) We claim that r_{n} is the greatest common divisor of a and b.

Any divisor of r_{n} is a divisor of r_{n−1}, because r_{n−1} = q_{n}r_{n}. Moreover if 2 ≤ i ≤ n then any common divisor of r_{i} and r_{i−1} is a divisor of r_{i−2}, because r_{i−2} = q_{i−1}r_{i−1} + r_{i}. If follows that every divisor of r_{n} is a divisor of all the integers r_{0}, r_{1}, …, r_{n}. In particular, any divisor of r_{n} is a common divisor of a and b. In particular, r_{n} is itself a common divisor of a and b.

If 2 ≤ i ≤ n then any common divisor of r_{i−2} and r_{i−1} is a divisor of r_{i}, because r_{i} = r_{i−2} − q_{i−1}r_{i−1}. It follows that every common divisor of a and b is a divisor of all the integers r_{0}, r_{1}, …, r_{n}. In particular any common divisor of a and b is a divisor of r_{n}. It follows that r_{n} is the greatest common divisor of a and b.

There exist integers u_{i} and v_{i} such that r_{i} = u_{i}a + v_{i}b for i = 1, 2, …, n. Indeed u_{i} = u_{i−2}−q_{i−1}u_{i−1} and v_{i} = v_{i−2}−q_{i−1}v_{i−1} for each integer i between 2 and n, where u_{0} = 1, v_{0} = 0, u_{1} = 0 and v_{1} = 1. In particular r_{n} = u_{n}a+v_{n}b.

The algorithm described above for calculating the greatest common divisor (a, b) of two positive integers a and b is referred to as the Euclidean algorithm. It also enables one to calculate integers u and v such that (a, b) = ua + vb.

Example We calculate the greatest common divisor of 425 and 119. Now

425 = 3 × 119 + 68
119 = 68 + 51
68 = 51 + 17
51 = 3 × 17.

It follows that 17 is the greatest common divisor of 425 and 119. Moreover

17 = 68 − 51 = 68 − (119 − 68)
= 2 × 68 − 119 = 2 × (425 − 3 × 119) − 119
= 2 × 425 − 7 × 119.

1.4 Prime Numbers

Definition A prime number is an integer p greater than one with the property that 1 and p are the only positive integers that divide p.

Let p be a prime number, and let x be an integer. Then the greatest common divisor (p, x) of p and x is a divisor of p, and therefore either (p, x) = p or else (p, x) = 1. It follows that either x is divisible by p or else x is coprime to p.

Theorem 1.4 Let p be a prime number, and let x and y be integers. If p divides xy then either p divides x or else p divides y.

Proof Suppose that p divides xy but p does not divide x. Then p and x are coprime, and hence there exist integers u and v such that 1 = up + vx (Corollary 1.3). Then y = upy + vxy. It then follows that p divides y, as required.

Corollary 1.5 Let p be a prime number. If p divides a product of integers then p divides at least one of the factors of the product.

Proof Let a_{1}, a_{2}, …, a_{k} be integers, where k > 1. Suppose that p divides a_{1}a_{2} ⋯ a_{k}. Then either p divides a_{k} or else p divides a_{1}a_{2} ⋯ a_{k−1}. The required result therefore follows by induction on the number k of factors in the product.

1.5 The Fundamental Theorem of Arithmetic

Lemma 1.6 Every integer greater than one is a prime number or factors as a product of prime numbers.

Proof Let n be an integer greater than one. Suppose that every integer m satisfying 1 < m < n is a prime number or factors as a product of prime numbers. If n is not a prime number then n = ab for some integers a and b satisfying 1 < a < n and 1 < b < n. Then a and b are prime numbers or products of prime numbers. Thus if n is not itself a prime number then n must be a product of prime numbers. The required result therefore follows by induction on n.

An integer greater than one that is not a prime number is said to be a composite number.

Let n be an composite number. We say that n factors uniquely as a product of prime numbers if, given prime numbers p_{1}, p_{2}, …, p_{r} and q_{1}, q_{2}, …, q_{s} such that

n = p_{1}p_{2} ⋯ p_{r} = q_{1}q_{2} … q_{s},

the number of times a prime number occurs in the list p_{1}, p_{2}, …, p_{r} is equal to the number of times it occurs in the list q_{1}, q_{2}, …, q_{s}. (Note that this implies that r = s.)

Theorem 1.7 (The Fundamental Theorem of Arithmetic) Every composite number greater than one factors uniquely as a product of prime numbers.

Proof Let n be a composite number greater than one. Suppose that every composite number greater than one and less than n factors uniquely as a product of prime numbers. We show that n then factors uniquely as a product of prime numbers. Suppose therefore that

n = p_{1}p_{2} ⋯ p_{r} = q_{1}q_{2} …, q_{s},

where p_{1}, p_{2}, …, p_{r} and q_{1}, q_{2}, …, q_{s} are prime numbers, p_{1} ≤ p_{2} ≤ ⋯ ≤ p_{r} and q_{1} ≤ q_{2} ≤ ⋯ ≤ q_{s}. We must prove that r = s and p_{i} = q_{i} for all integers i between 1 and r.

Let p be the smallest prime number that divides n. If a prime number divides a product of integers then it must divide at least one of the factors (Corollary 1.5). It follows that p must divide p_{i} and thus p = p_{i} for some integer i between 1 and r. But then p = p_{1}, since p_{1} is the smallest of the prime numbers p_{1}, p_{2}, …, p_{r}. Similarly p = q_{1}. Therefore p = p_{1} = q_{1}. Let m = n/p. Then

m = p_{2}p_{3} ⋯ p_{r} = q_{2}q_{3} ⋯ q_{s}.

But then r = s and p_{i} = q_{i} for all integers i between 2 and r, because every composite number greater than one and less than n factors uniquely as a product of prime numbers. It follows that n factors uniquely as a product of prime numbers. The required result now follows by induction on n. (We have shown that if all composite numbers m satisfying 1 < m < n factor uniquely as a product of prime numbers, then so do all composite numbers m satisfying 1 < m < n + 1.)

1.6 The Infinitude of Primes

Theorem 1.8 (Euclid) The number of prime numbers is infinite.

Proof Let p_{1}, p_{2}, …, p_{r} be prime numbers, let m = p_{1}p_{2} ⋯ p_{r} + 1. Now p_{i} does not divide m for i = 1, 2, …, r, since if p_{i} were to divide m then it would divide m − p_{1}p_{2} ⋯ p_{r} and thus would divide 1. Let p be a prime factor of m. Then p must be distinct from p_{1}, p_{2}, …, p_{r}. Thus no finite set {p_{1}, p_{2}, …, p_{r}} of prime numbers can include all prime numbers.

1.7 Congruences

Let m be a positive integer. Integers x and y are said to be congruent modulo m if x − y is divisible by m. If x and y are congruent modulo m then we denote this by writing x ≡ y (mod m).

The congruence class of an integer x modulo m is the set of all integers that are congruent to x modulo m.

Let x, y and z be integers. Then x ≡ x (mod m). Also x ≡ y (mod m) if and only if y ≡ x (mod m). If x ≡ y (mod m) and y ≡ z (mod m) then x ≡ z (mod m). Thus congruence modulo m is an equivalence relation on the set of integers.

Lemma 1.9 Let m be a positive integer, and let x, x′, y and y′ be integers. Suppose that x ≡ x′ (mod m) and y ≡ y′ (mod m). Then x + y ≡ x′ + y′ (mod m) and xy ≡ x′y′ (mod m).

Proof The result follows immediately from the identities

(x + y) − (x′ + y′) = (x − x′) + (y − y′),
xy − x′y′ = (x − x′)y + x′(y − y′).

Lemma 1.10 Let x, y and m be integers with m ≠ 0. Suppose that m divides xy and that m and x are coprime. Then m divides y.

Proof There exist integers a and b such that 1 = am + bx, since m and x are coprime (Corollary 1.3). Then y = amy + bxy, and m divides xy, and therefore m divides y, as required.

Lemma 1.11 Let m be a positive integer, and let a, x and y be integers with ax ≡ ay (mod m). Suppose that m and a are coprime. Then x ≡ y (mod m).

Proof If ax ≡ ay (mod m) then a(x − y) is divisible by m. But m and a are coprime. It therefore follows from Lemma 1.10 that x − y is divisible by m, and thus x ≡ y (mod m), as required.

Lemma 1.12 Let x and m be non-zero integers. Suppose that x is coprime to m. Then there exists an integer y such that xy ≡ 1 (mod m). Moreover y is coprime to m.

Proof There exist integers y and k such that xy + mk = 1, since x and m are coprime (Corollary 1.3). Then xy ≡ 1 (mod m). Moreover any common divisor of y and m must divide xy and therefore must divide 1. Thus y is coprime to m, as required.

Lemma 1.13 Let m be a positive integer, and let a and b be integers, where a is coprime to m. Then there exist integers x that satisfy the congruence ax ≡ b (mod m). Moreover if x and x′ are integers such that ax ≡ b (mod m) and ax′ ≡ b (mod m) then x ≡ x′ (mod m).

Proof There exists an integer c such that ac ≡ 1 (mod m), since a is coprime to m (Lemma 1.12). Then ax ≡ b (mod m) if and only if x ≡ cb (mod m). The result follows.

Lemma 1.14 Let a_{1}, a_{2}, …, a_{r} be integers, and let x be an integer that is coprime to a_{i} for i = 1, 2, …, r. Then x is coprime to the product a_{1}a_{2} ⋯ a_{r} of the integers a_{1}, a_{2}, …, a_{r}.

Proof Let p be a prime number which divides the product a_{1}a_{2} ⋯ a_{r}. Then p divides one of the factors a_{1}, a_{2}, …, a_{r} (Corollary 1.5). It follows that p cannot divide x, since x and a_{i} are coprime for i = 1, 2, …, r. Thus no prime number is a common divisor of x and the product a_{1}a_{2} ⋯ a_{r}. It follows that the greatest common divisor of x and a_{1}a_{2} ⋯ a_{r} is 1, since this greatest common divisor cannot have any prime factors. Thus x and a_{1}a_{2} ⋯ a_{r} are coprime, as required.

Let m be a positive integer. For each integer x, let [x] denote the congruence class of x modulo m. If x, x′, y and y′ are integers and if x ≡ x′ (mod m) and y ≡ y′ (mod m) then xy ≡ x′y′ (mod m). It follows that there is a well-defined operation of multiplication defined on congruence classes of integers modulo m, where [x][y] = [xy] for all integers x and y. This operation is commutative and associative, and [x][1] = [x] for all integers x. If x is an integer coprime to m, then it follows from Lemma 1.12 that there exists an integer y coprime to m such that xy ≡ 1 (mod m). Then [x][y] = [1]. Therefore the set ℤ_{m}^{∗} of congruence classes modulo m of integers coprime to m is an Abelian group (with multiplication of congruence classes defined as above).

1.8 The Chinese Remainder Theorem

Let I be a set of integers. The integers belonging to I are said to be pairwise coprime if any two distinct integers belonging to I are coprime.

Proposition 1.15 Let m_{1}, m_{2}, …, m_{r} be non-zero integers that are pairwise coprime. Let x be an integer that is divisible by m_{i} for i = 1, 2, …, r. Then x is divisible by the product m_{1}m_{2} ⋯ m_{r} of the integers m_{1}, m_{2}, …, m_{r}.

Proof For each integer k between 1 and r let P_{k} be the product of the integers m_{i} with 1 ≤ i ≤ k. Then P_{1} = m_{1} and P_{k} = P_{k−1}m_{k} for k = 2, 3, …, r. Let x be a positive integer that is divisible by m_{i} for i = 1, 2, …, r. We must show that P_{r} divides x. Suppose that P_{k−1} divides x for some integer k between 2 and r. Let y = x/P_{k−1}. Then m_{k} and P_{k−1} are coprime (Lemma 1.14) and m_{k} divides P_{k−1}y. It follows from Lemma 1.10 that m_{k} divides y. But then P_{k} divides x, since P_{k} = P_{k−1}m_{k} and x = P_{k−1}y. On successively applying this result with k = 2, 3, …, r we conclude that P_{r} divides x, as required.

Theorem 1.16 (Chinese Remainder Theorem) Let m_{1}, m_{2}, …, m_{r} be pairwise coprime positive integers. Then, given any integers x_{1}, x_{2}, …, x_{r}, there exists an integer z such that z ≡ x_{i} (mod m_{i}) for i = 1, 2, …, r. Moreover if z′ is any integer satisfying z′ ≡ x_{i} (mod m_{i}) for i = 1, 2, …, r then z′ ≡ z (mod m), where m = m_{1}m_{2} ⋯ m_{r}.

Proof Let m = m_{1}m_{2} ⋯ m_{r}, and let s_{i} = m/m_{i} for i = 1, 2, …, r. Note that s_{i} is the product of the integers m_{j} with j ≠ i, and is thus a product of integers coprime to m_{i}. It follows from Lemma 1.14 that m_{i} and s_{i} are coprime for i = 1, 2, …, r. Therefore there exist integers a_{i} and b_{i} such that a_{i}m_{i} + b_{i}s_{i} = 1 for i = 1, 2, …, r (Corollary 1.3). Let u_{i} = b_{i}s_{i} for i = 1, 2, …, r. Then u_{i} ≡ 1 (mod m_{i}), and u_{i} ≡ 0 (mod m_{j}) when j ≠ i. Thus if

z = x_{1}u_{1} + x_{2}u_{2} + ⋯ x_{r}u_{r}

then z ≡ x_{i} (mod m_{i}) for i = 1, 2, …, r.

Now let z′ be an integer with z′ ≡ x_{i} (mod m_{i}) for i = 1, 2, …, r. Then z′ − z is divisible by m_{i} for i = 1, 2, …, r. It follows from Proposition 1.15 that z′ −z is divisible by the product m of the integers m_{1}, m_{2}, …, m_{r}. Then z′ ≡ z (mod m), as required.

1.9 The Euler Totient Function

Let n be a positive integer. We define φ(n) to be the number of integers x satisfying 0 ≤ x < n that are coprime to n. The function φ on the set of positive integers is referred to as the Euler totient function.

Every integer (including zero) is coprime to 1, and therefore φ(1) = 1. Let p be a prime number. Then φ(p) = p − 1, since every positive integer

less than p is coprime to p. Moreover φ(p^{k}) = p^{k} − p^{k−1} for all positive integers k, since there are p^{k−1} integers x satisfying 0 ≤ x < p^{k} that are divisible by p, and the integers coprime to p^{k} are those that are not divisible by p.

Theorem 1.17 Let m_{1} and m_{2} be positive integers. Suppose that m_{1} and m_{2} are coprime. Then φ(m_{1}m_{2}) = φ(m_{1})φ(m_{2}).

Proof Let x be an integer satisfying 0 ≤ x < m_{1} that is coprime to m_{1}, and let y be an integer satisfying 0 ≤ y < m_{2} that is coprime to m_{2}. It follows from the Chinese Remainder Theorem (Theorem 1.16) that there exists exactly one integer z satisfying 0 ≤ z < m_{1}m_{2} such that z ≡ x (mod m_{1}) and z ≡ y (mod m_{2}). Moreover z must then be coprime to m_{1} and to m_{2}, and must therefore be coprime to m_{1}m_{2}. Thus every integer z satisfing 0 ≤ z < m_{1}m_{2} that is coprime to m_{1}m_{2} is uniquely determined by its congruence classes modulo m_{1} and m_{2}, and the congruence classes of z modulo m_{1} and m_{2} contain integers coprime to m_{1} and m_{2} respectively. Thus the number φ(m_{1}m_{2}) of integers z satisfying 0 ≤ z < m_{1}m_{2} that are coprime to m_{1}m_{2} is equal to φ(m_{1})φ(m_{2}), since φ(m_{1}) is the number of integers x satisfying 0 ≤ x < m_{1} that are coprime to m_{1} and φ(m_{2}) is the number of integers y satisfying 0 ≤ y < m_{2} that are coprime to m_{2}.

Corollary 1.18 φ(n) = n ∏_{p|n} (1 − \frac{1}{p}), for all positive integers n, where

∏_{p|n} (1 − \frac{1}{p}) denotes the product of 1 − \frac{1}{p} taken over all prime numbers p

that divide n.

Proof Let n = p_{1}^{k_{1}}p_{2}^{k_{2}} ⋯ p_{m}^{k_{m}}, where p_{1}, p_{2}, …, p_{m} are prime numbers and k_{1}, k_{2}, …, k_{m} are positive integers. Then φ(n) = φ(p_{1}^{k_{1}})φ(p_{2}^{k_{2}}) ⋯ φ(p_{m}^{k_{m}}), and

φ(p_{i}^{k_{i}}) = p_{i}^{k_{i}}(1 − (1/p_{i})) for i = 1, 2, …, m. Thus φ(n) = n ∏_{i=1}^{m} (1 − \frac{1}{p_{i}} ), as

required.

Let f be any function defined on the set of positive integers, and let n be a positive integer. We denote the sum of the values of f(d) over all divisors d

of n by ∑_{d|n} f(d).

Lemma 1.19 Let n be a positive integer. Then ∑_{d|n} φ(d) = n.

Proof If x is an integer satisfying 0 ≤ x < n then (x, n) = n/d for some divisor d of n. It follows that n = ∑_{d|n} n_{d}, where n_{d} is the number of integers x

satisfying 0 ≤ x < n for which (x, n) = n/d. Thus it suffices to show that n_{d} = φ(d) for each divisor d of n.

Let d be a divisor of n, and let a = n/d. Given any integer x satisfying 0 ≤ x < n that is divisible by a, there exists an integer y satisfying 0 ≤ y < d such that x = ay. Then (x, n) is a multiple of a. Moreover a multiple ae of a divides both x and n if and only if e divides both y and d. Therefore (x, n) = a(y, d). It follows that the integers x satisfying 0 ≤ x < n for which (x, n) = a are those of the form ay, where y is an integer, 0 ≤ y < d and (y, d) = 1. It follows that there are exactly φ(d) integers x satisfying 0 ≤ x < n for which (x, n) = n/d, and thus n_{d} = φ(d) and n = ∑_{d|n} φ(d), as

required.

1.10 The Theorems of Fermat, Wilson and Euler

Theorem 1.20 (Fermat) Let p be a prime number. Then x^{p} ≡ x (mod p) for all integers x. Moreover if x is coprime to p then x^{p−1} ≡ 1 (mod p).

We shall give three proofs of this theorem below.

Lemma 1.21 Let p be a prime number. Then the binomial coefficient \binom{p}{k}

is divisible by p for all integers k satisfying 0 < k < p.

Proof The binomial coefficient is given by the formula \binom{p}{k} = \frac{p!}{(p − k)!k!}.

Thus if 0 < k < p then \binom{p}{k} = \frac{pm}{k!}, where m = \frac{(p − 1)!}{(p − k)!}. Thus if 0 < k < p

then k! divides pm. Also k! is coprime to p. It follows that k! divides m

(Lemma 1.10), and therefore the binomial coefficient \binom{p}{k} is a multiple of

p.

First Proof of Theorem 1.20 Let p be prime number. Then

(x + 1)^{p} = ∑_{k=0}^{p} \binom{p}{k}x^{k}.

It then follows from Lemma 1.21 that (x + 1)^{p} ≡ x^{p} + 1 (mod p). Thus if f(x) = x^{p} − x then f(x + 1) ≡ f(x) (mod p) for all integers x, since f(x + 1) − f(x) = (x + 1)^{p} − x^{p} − 1. But f(0) ≡ 0 (mod p). It follows by induction on |x| that f(x) ≡ 0 (mod p) for all integers x. Thus x^{p} ≡ x (mod p) for all integers x. Moreover if x is coprime to p then it follows from Lemma 1.11 that x^{p−1} ≡ 1 (mod p), as required.

Second Proof of Theorem 1.20 Let x be an integer. If x is divisible by p then x ≡ 0 (mod p) and x^{p} ≡ 0 (mod p).

Suppose that x is coprime to p. If j is an integer satisfying 1 ≤ j ≤ p − 1 then j is coprime to p and hence xj is coprime to p. It follows that there exists a unique integer u_{j} such that 1 ≤ u_{j} ≤ p−1 and xj ≡ u_{j} (mod p). If j and k are integers between 1 and p−1 and if j ≠ k then u_{j} ≠ u_{k}. It follows that each integer between 1 and p − 1 occurs exactly once in the list u_{1}, u_{2}, …, u_{p−1}, and therefore u_{1}u_{2} ⋯ u_{p−1} = (p − 1)!. Thus if we multiply together the left hand sides and right hand sides of the congruences xj ≡ u_{j} (mod p) for j = 1, 2, …, p − 1 we obtain the congruence x^{p−1}(p − 1)! ≡ (p − 1)! (mod p). But then x^{p−1} ≡ 1 (mod p) by Lemma 1.11, since (p − 1)! is coprime to p. But then x^{p} ≡ x (mod p), as required.

Third Proof of Theorem 1.20 Let p be a prime number. The congruence classes modulo p of integers coprime to p constitute a group of order p − 1, where the group operation is multiplication of congruence classes. Now it follows from Lagrange’s Theorem that that order of any element of a finite group divides the order of the group. If we apply this result to the group of congruence classes modulo p of integers coprime to p we find that if an integer x is not divisible by p then x^{p−1} ≡ 1 (mod p). It follows that x^{p} ≡ x (mod p) for all integers x that are not divisible by p. This congruence also holds for all integers x that are divisible by p.

Theorem 1.22 (Wilson’s Theorem) (p−1)!+1 is divisible by p for all prime numbers p.

Proof Let p be a prime number. If x is an integer satisfying x^{2} ≡ 1 (mod p) then p divides (x − 1)(x + 1) and hence either p divides either x − 1 or x + 1. Thus if 1 ≤ x ≤ p − 1 and x^{2} ≡ 1 (mod p) then either x = 1 or x = p − 1.

For each integer x satisfying 1 ≤ x ≤ p − 1, there exists exactly one integer y satisfying 1 ≤ y ≤ p − 1 such that xy ≡ 1 (mod p). Moreover y ≠ x when 2 ≤ x ≤ p − 2. It follows that (p − 2)! is a product of numbers of the form xy, where x and y are distinct integers between 2 and p − 2 and xy ≡ 1 (mod p). It follows that (p − 2)! ≡ 1 (mod p). But then (p−1)! ≡ p−1 (mod p), and hence (p−1)!+1 ≡ 0 (mod p), as required.

The following theorem of Euler generalizes Fermat’s Theorem (Theorem 1.20).

Theorem 1.23 (Euler) Let m be a positive integer, and let x be an integer coprime to m. Then x^{φ(m)} ≡ 1 (mod m).

First Proof of Theorem 1.23 The result is trivially true when m = 1. Suppose that m > 1. Let I be the set of all positive integers less than m that are coprime to m. Then φ(m) is by definition the number of integers in I. If y is an integer coprime to m then so is xy. It follows that, to each integer j in I there exists a unique integer u_{j} in I such that xj ≡ u_{j} (mod m). Moreover if j ∈ I and k ∈ I and j ≠ k then u_{j} ≢ u_{k}. Therefore I = {u_{j} : j ∈ I}. Thus if we multiply the left hand sides and right hand sides of the congruences xj ≡ u_{j} (mod m) for all j ∈ I we obtain the congruence x^{φ(m)}z ≡ z (mod m), where z is the product of all the integers in I. But z is coprime to m, since a product of integers coprime to m is itself coprime to m. It follows from Lemma 1.11 that x^{φ(m)} ≡ 1 (mod m), as required.

2nd Proof of Theorem 1.23 Let m be a positive integer. Then the congruence classes modulo m of integers coprime to m constitute a group of order φ(m), where the group operation is multiplication of congruence classes. Now it follows from Lagrange’s Theorem that that order of any element of a finite group divides the order of the group. If we apply this result to the group of congruence classes modulo m of integers coprime to m we find that x^{φ(m)} ≡ 1 (mod m), as required.

1.11 Solutions of Polynomial Congruences

Let f be a polynomial with integer coefficients, and let m be a positive integer. If x and x′ are integers, and if x ≡ x′ (mod m), then f(x) ≡ f(x′) (mod m). It follows that the set consisting of those integers x which satisfy the congruence f(x) ≡ 0 (mod m) is a union of congruence classes modulo m. The number of solutions modulo m of the congruence f(x) ≡ 0 (mod m) is defined to be the number of congruence classes of integers modulo m such that an integer x satisfies the congruence f(x) ≡ 0 (mod m) if and only if it belongs to one of those congruence classes. Thus a congruence f(x) ≡ 0 (mod m) has n solutions modulo m if and only if there exist n integers a_{1}, a_{2}, …, a_{n} satisfying the congruence such that every solution of the congruence f(x) ≡ 0 (mod m) is congruent modulo m to exactly one of the integers a_{1}, a_{2}, …, a_{n}.

Note that the number of solutions of the congruence f(x) ≡ 0 (mod m) is equal to the number of integers x satisfying 0 ≤ x < m for which f(x) ≡ 0 (mod m). This follows immediately from the fact that each congruence class of integers modulo m contains exactly one integer x satisfying 0 ≤ x < m.

Theorem 1.24 Let f be a polynomial with integer coefficients, and let p be a prime number. Suppose that the coefficients of f are not all divisible by p.

Then the number of solutions modulo p of the congruence f(x) ≡ 0 (mod p) is at most the degree of the polynomial f.

Proof The result is clearly true when f is a constant polynomial. We can prove the result for non-constant polynomials by induction on the degree of the polynomial.

First we observe that, given any integer a, there exists a polynomial g with integer coefficients such that f(x) = f(a) + (x − a)g(x). Indeed f(y + a) is a polynomial in y with integer coefficients, and therefore f(y+a) = f(a)+yh(y) for some polynomial h with integer coefficients. Thus if g(x) = h(x − a) then g is a polynomial with integer coefficients and f(x) = f(a) + (x − a)g(x).

Suppose that f(a) ≡ 0 (mod p) and f(b) ≡ 0 (mod p). Let f(x) = f(a) + (x − a)g(x), where g is a polynomial with integer coefficients. The coefficients of f are not all divisible by p, but f(a) is divisible by p, and therefore the coefficients of g cannot all be divisible by p.

Now f(a) and f(b) are both divisible by the prime number p, and therefore (b−a)g(b) is divisible by p. But a prime number divides a product of integers if and only if it divides one of the factors. Therefore either b − a is divisible by p or else g(b) is divisible by p. Thus either b ≡ a (mod p) or else g(b) ≡ 0 (mod p). The required result now follows easily by induction on the degree of the polynomial f.

1.12 Primitive Roots

Lemma 1.25 Let m be a positive integer, and let x be an integer coprime to m. Then there exists a positive integer n such that x^{n} ≡ 1 (mod m).

Proof There are only finitely many congruence classes modulo m. Therefore there exist positive integers j and k with j < k such that x^{j} ≡ x^{k} (mod m). Let n = k − j. Then x^{j}x^{n} ≡ x^{j} (mod m). But x^{j} is coprime to m. It follows from Lemma 1.11 that x^{n} ≡ 1 (mod m).

Remark The above lemma also follows directly from Euler’s Theorem (Theorem 1.23).

Let m be a positive integer, and let x be an integer coprime to m. The order of the congruence class of x modulo m is by definition the smallest positive integer d such that x^{d} ≡ 1 (mod m).

Lemma 1.26 Let m be a positive integer, let x be an integer coprime to m, and let j and k be positive integers. Then x^{j} ≡ x^{k} (mod m) if and only if j ≡ k (mod d), where d is the order of the congruence class of x modulo m.

Proof We may suppose without loss of generality that j < k. If j ≡ k (mod d) then k − j is divisible by d, and hence x^{k−j} ≡ 1 (mod m). But then x^{k} ≡ x^{j}x^{k−j} ≡ x^{j} (mod m). Conversely suppose that x^{j} ≡ x^{k} (mod m) and j < k. Then x^{j}x^{k−j} ≡ x^{j} (mod m). But x^{j} is coprime to m. It follows from Lemma 1.11 that x^{k−j} ≡ 1 (mod m). Thus if k − j = qd + r, where q and r are integers and 0 ≤ r < d, then x^{r} ≡ 1 (mod m). But then r = 0, since d is the smallest positive integer for which x^{d} ≡ 1 (mod m). Therefore k − j is divisible by d, and thus j ≡ k (mod d).

Lemma 1.27 Let p be a prime number, and let x and y be integers coprime to p. Suppose that the congruence classes of x and y modulo p have the same order. Then there exists a non-negative integer k, coprime to the order of the congruence classes of x and y, such that y ≡ x^{k} (mod p).

Proof Let d be the order of the congruence class of x modulo p. The solutions of the congruence x^{d} ≡ 1 (mod p) include x^{j} with 0 ≤ j < d. But the congruence x^{d} ≡ 1 (mod p) has at most d solutions modulo p, since p is prime (Theorem 1.24), and the congruence classes of 1, x, x^{2}, …, x^{d−1} modulo p are distinct (Lemma 1.26). It follows that any solution of the congruence x^{d} ≡ 1 (mod p) is congruent to x^{k} for some positive integer k. Thus if y is an integer coprime to p whose congruence class is of order d then y ≡ x^{k} (mod p) for some positive integer k. Moreover k is coprime to d, for if e is a common divisor of k and d then y^{d/e} ≡ x^{d(k/e)} ≡ 1 (mod p), and hence e = 1.

Let m be a positive integer. An integer g is said to be a primitive root modulo m if, given any integer x coprime to m, there exists an integer j such that x ≡ g^{j} (mod m).

A primitive root modulo m is necessarily coprime to m. For if g is a primitive root modulo m then there exists an integer n such that g^{n} ≡ 1 (mod m). But then any common divisor of g and m must divide 1, and thus g and m are coprime.

Theorem 1.28 Let p be a prime number. Then there exists a primitive root modulo p.

Proof If x is an integer coprime to p then it follows from Fermat’s Theorem (Theorem 1.20) that x^{p−1} ≡ 1 (mod p). It then follows from Lemma 1.26 that the order of the congruence class of x modulo p divides p − 1. For each divisor d of p−1, let ψ(d) denote the number of congruence classes modulo p of integers coprime to p that are of order d. Clearly ∑_{d|p−1} ψ(d) = p − 1.

Let x be an integer coprime to p whose congruence class is of order d, where d is a divisor of p − 1. If k is coprime to d then the congruence class of x^{k} is also of order d, for if (x^{k})^{n} ≡ 1 (mod p) then d divides kn and hence d divides n (Lemma 1.10). Let y be an integer coprime to p whose congruence class is also of order d. It follows from Lemma 1.27 that there exists a non-negative integer k coprime to d such that y ≡ x^{k} (mod p). It then follows from Lemma 1.26 that there exists a unique integer k coprime to d such that 0 ≤ k < d and y ≡ x^{k} (mod p). Thus if there exists at least one integer x coprime to p whose congruence class modulo p is of order d then the congruence classes modulo p of integers coprime to p that are of order d are the congruence classes of x^{k} for those integers k satisfying 0 ≤ k < d that are coprime to d. Thus if ψ(d) > 0 then ψ(d) = φ(d), where φ(d) is the number of integers k satisfying 0 ≤ k < d that are coprime to d.

Now 0 ≤ ψ(d) ≤ φ(d) for each divisor d of p−1. But ∑_{d|p−1} ψ(d) = p−1 and

∑_{d|p−1} φ(d) = p − 1 (Lemma 1.19). Therefore ψ(d) = φ(d) for each divisor d of

p − 1. In particular ψ(p − 1) = φ(p − 1) ≥ 1. Thus there exists an integer g whose congruence class modulo p is of order p − 1. The congruence classes of 1, g, g^{2}, … g^{p−2} modulo p are then distinct. But there are exactly p − 1 congruence classes modulo p of integers coprime to p. It follows that any integer that is coprime to p must be congruent to g^{j} for some non-negative integer j. Thus g is a primitive root modulo p.

Corollary 1.29 Let p be a prime number. Then the group of congruence classes modulo p of integers coprime to p is a cyclic group of order p − 1.

Remark It can be shown that there exists a primitive root modulo m if m = 1, 2 or 4, if m = p^{k} or if m = 2p^{k}, where p is some odd prime number and k is a positive integer. In all other cases there is no primitive root modulo m.

1.13 Quadratic Residues

Definition Let p be a prime number, and let x be an integer coprime to p. The integer x is said to be a quadratic residue of p if there exists an integer y such that x ≡ y^{2} (mod p). If x is not a quadratic residue of p then x is said to be a quadratic non-residue of p.

Proposition 1.30 Let p be an odd prime number, and let a, b and c be integers, where a is coprime to p. Then there exist integers x satisfying the congruence ax^{2} + bx + c ≡ 0 (mod p) if and only if either b^{2} − 4ac is a quadratic residue of p or else b^{2} − 4ac ≡ 0 (mod p).

Proof Let x be an integer. Then ax^{2} + bx + c ≡ 0 (mod p) if and only if 4a^{2}x^{2} + 4abx + 4ac ≡ 0 (mod p), since 4a is coprime to p (Lemma 1.11). But 4a^{2}x^{2} + 4abx + 4ac = (2ax + b)^{2} − (b^{2} − 4ac). It follows that ax^{2} + bx + c ≡ 0 (mod p) if and only if (2ax + b)^{2} ≡ b^{2} − 4ac (mod p). Thus if there exist integers x satisfying the congruence ax^{2} + bx + c ≡ 0 (mod p) then either b^{2} − 4ac is a quadratic residue of p or else b^{2} − 4ac ≡ 0 (mod p). Conversely suppose that either b^{2}−4ac is a quadratic residue of p or b^{2}−4ac ≡ 0 (mod p). Then there exists an integer y such that y^{2} ≡ b^{2} − 4ac (mod p). Also there exists an integer d such that 2ad ≡ 1 (mod p), since 2a is coprime to p (Lemma 1.12). If x ≡ d(y − b) (mod p) then 2ax + b ≡ y (mod p), and hence (2ax + b)^{2} ≡ b^{2} − 4ac (mod p). But then ax^{2} + bx + c ≡ 0 (mod p), as required.

Lemma 1.31 Let p be an odd prime number, and let x and y be integers. Suppose that x^{2} ≡ y^{2} (mod p). Then either x ≡ y (mod p) or else x ≡ −y (mod p).

Proof x^{2} − y^{2} is divisible by p, since x^{2} ≡ y^{2} (mod p). But x^{2} − y^{2} = (x − y)(x + y), and a prime number divides a product of integers if and only if it divides at least one of the factors. Therefore either x − y is divisible by p or else x + y is divisible by p. Thus either x ≡ y (mod p) or else x ≡ −y (mod p).

Lemma 1.32 Let p be an odd prime number, and let m = (p − 1)/2. Then there are exactly m congruence classes of integers coprime to p that are quadratic residues of p. Also there are exactly m congruence classes of integers coprime to p that are quadratic non-residues of p.

Proof If i and j are integers between 1 and m, and if i ≠ j then i ≢ j (mod p) and i ≢ −j (mod p). It follows from Lemma 1.31 that if i and j are integers between 1 and m, and if i ≠ j then i^{2} ≢ j^{2}. Thus the congruence classes of 1^{2}, 2^{2}, …, m^{2} modulo p are distinct. But, given any integer x coprime to p, there is an integer i such that 1 ≤ i ≤ m and either x ≡ i (mod p) or x ≡ −i (mod p), and therefore x^{2} ≡ i^{2} (mod p). Thus every quadratic residue of p is congruent to i^{2} for exactly one integer i betweeen 1 and m. Thus there are m congruence classes of quadratic residues of p.

There are 2m congruence classes of integers modulo p that are coprime to p. It follows that there are m congruence classes of quadratic non-residues of p, as required.

Theorem 1.33 Let p be an odd prime number, let R be the set of all integers coprime to p that are quadratic residues of p, and let N be the set of all integers coprime to p that are quadratic non-residues of p. If x ∈ R and y ∈ R then xy ∈ R. If x ∈ R and y ∈ N then xy ∈ N. If x ∈ N and y ∈ N then xy ∈ R.

Proof Let m = (p − 1)/2. Then there are exactly m congruence classes of integers coprime to p that are quadratic residues of p. Let these congruence classes be represented by the integers r_{1}, r_{2}, …, r_{m}, where r_{i} ≢ r_{j} (mod p) when i ≠ j. Also there are exactly m congruence classes of integers coprime to p that are quadratic non-residues modulo p.

The product of two quadratic residues of p is itself a quadratic residue of p. Therefore xy ∈ R for all x ∈ R and y ∈ R.

Suppose that x ∈ R. Then xr_{i} ∈ R for i = 1, 2, …, m, and xr_{i} ≢ xr_{j} when i ≠ j. It follows that the congruence classes of xr_{1}, xr_{2}, …, xr_{m} are distinct, and consist of quadratic residues of p. But there are exactly m congruence classes of quadratic residues of p. It follows that every quadratic residue of p is congruent to exactly one of the integers xr_{1}, xr_{2}, …, xr_{m}. But if y ∈ N then y ≢ r_{i} and hence xy ≢ xr_{i} for i = 1, 2, …, m. It follows that xy ∈ N for all x ∈ R and y ∈ N.

Now suppose that x ∈ N. Then xr_{i} ∈ N for i = 1, 2, …, m, and xr_{i} ≢ xr_{j} when i ≠ j. It follows that the congruence classes of xr_{1}, xr_{2}, …, xr_{m} are distinct, and consist of quadratic non-residues modulo p. But there are exactly m congruence classes of quadratic non-residues modulo p. It follows that every quadratic non-residue of p is congruent to exactly one of the integers xr_{1}, xr_{2}, …, xr_{m}. But if y ∈ N then y ≢ r_{i} and hence xy ≢ xr_{i} for i = 1, 2, …, m. It follows that xy ∈ R for all x ∈ N and y ∈ N.

Let p be an odd prime number. The Legendre symbol (\frac{x}{p}) is defined for

integers x as follows: if x is coprime to p and x is a quadratic residue of p then (\frac{x}{p}) = +1; if x is coprime to p and x is a quadratic non-residue of p

then (\frac{x}{p}) = −1; if x is divisible by p then (\frac{x}{p}) = 0.

The following result follows directly from Theorem 1.33.

Corollary 1.34 Let p be an odd prime number. Then

(\frac{x}{p})(\frac{y}{p}) = (\frac{xy}{p} )

for all integers x and y.

Lemma 1.35 (Euler) Let p be an odd prime number, and let x be an integer coprime to p. Then x is a quadratic residue of p if and only if x^{(p−1)/2} ≡ 1 (mod p). Also x is a quadratic non-residue of p if and only if x^{(p−1)/2} ≡ −1 (mod p).

Proof Let m = (p−1)/2. If x is a quadratic residue of p then x ≡ y^{2} (mod p) for some integer y coprime to p. Then x^{m} = y^{p−1}, and y^{p−1} ≡ 1 (mod p) by Fermat’s Theorem (Theorem 1.20), and thus x^{m} ≡ 1 (mod p).

It follows from Theorem 1.24 that there are at most m congruence classes of integers x satisfying x^{m} ≡ 1 (mod p). However all quadratic residues modulo p satisfy this congruence, and there are exactly m congruence classes of quadratic residues modulo p. It follows that an integer x coprime to p satisfies the congruence x^{m} ≡ 1 (mod p) if and only if x is a quadratic residue of p.

Now let x be a quadratic non-residue of p and let u = x^{m}. Then u^{2} ≡ 1 (mod p) but u ≢ 1 (mod p). It follows from Lemma 1.31 that u ≡ −1 (mod p). It follows that an integer x coprime to p is a quadratic non-residue of p if and only if x^{m} ≡ −1 (mod p).

Corollary 1.36 Let p be an odd prime number. Then

x^{(p−1)/2} ≡ (\frac{x}{p}) (mod p)

for all integers x.

Proof If x is coprime to p then the result follows from Lemma 1.35. If x is divisible by p then so is x^{(p−1)/2}. In that case x^{(p−1)/2} ≡ 0 (mod p) and

(\frac{x}{p}) = 0 (mod p).

Corollary 1.37 (\frac{−1}{p}) = (−1)^{(p−1)/2} for all odd prime numbers p.

Proof It follows from Corollary 1.36 that (\frac{−1}{p}) ≡ (−1)^{(p−1)/2} (mod p) for

all odd prime numbers p. But (\frac{−1}{p}) = ±1, by the definition of the Legendre

symbol. Therefore (\frac{−1}{p}) = (−1)^{(p−1)/2}, as required.

Remark Let p be an odd prime number. It follows from Theorem 1.28 that there exists a primitive root g modulo p. Moreover the congruence class of g modulo p is of order p − 1. It follows that g^{j} ≡ g^{k} (mod p), where j and k are positive integers, if and only if j − k is divisible by p − 1. But p − 1 is even. Thus if g^{j} ≡ g^{k} then j − k is even. It follows easily from this that an integer x is a quadratic residue of p if and only if x ≡ g^{k} (mod p) for some even integer k. The results of Theorem 1.33 and Lemma 1.35 follow easily from this fact.

Let p be an odd prime number, and let m = (p − 1)/2. Then each integer not divisible by p is congruent to exactly one of the integers ±1, ±2, …, ±m.

The following lemma was proved by Gauss.

Lemma 1.38 Let p be an odd prime number, let m = (p − 1)/2, and let x be an integer that is not divisible by p. Then (\frac{x}{p}) = (−1)^{r}, where r is the

number of pairs (j, u) of integers satisfying 1 ≤ j ≤ m and 1 ≤ u ≤ m for which xj ≡ −u (mod p).

Proof For each integer j satisfying 1 ≤ j ≤ m there is a unique integer u_{j} satisfying 1 ≤ u_{j} ≤ m such that xj ≡ e_{j}u_{j} (mod p) with e_{j} = ±1. Then e_{1}e_{2} ⋯ e_{m} = (−1)^{r}.

If j and k are integers between 1 and m and if j ≠ k, then j ≢ k (mod p) and j ≢ −k (mod p). But then xj ≢ xk (mod p) and xj ≢ −xk (mod p) since x is not divisible by p. Thus if 1 ≤ j ≤ m, 1 ≤ k ≤ m and j ≠ k then u_{j} ≠ u_{k}. It follows that each integer between 1 and m occurs exactly once in the list u_{1}, u_{2}, …, u_{m}, and therefore u_{1}u_{2} ⋯ u_{m} = m!. Thus if we multiply the congruences xj ≡ e_{j}u_{j} (mod p) for j = 1, 2, …, m we obtain the congruence x^{m}m! ≡ (−1)^{r}m! (mod p). But m! is not divisible by p, since p is prime and m < p. It follows that x^{m} ≡ (−1)^{r} (mod p). But x^{m} ≡ (\frac{x}{p}) (mod p) by Lemma 1.35. Therefore (\frac{x}{p}) ≡ (−1)^{r} (mod p), and

hence (\frac{x}{p}) = (−1)^{r}, as required.

Let n be an odd integer. Then n = 2k + 1 for some integer k. Then n^{2} = 4(k^{2} + k) + 1, and k^{2} + k is an even integer. It follows that if n is an odd integer then n^{2} ≡ 1 (mod 8), and hence (−1)^{(n^{2}−1)/8} = ±1.

Theorem 1.39 Let p be an odd prime number. Then (\frac{2}{p}) = (−1)^{(p^{2}−1)/8}.

Proof The value of (−1)^{(p^{2}−1)/8} is determined by the congruence class of p modulo 8. Indeed (−1)^{(p^{2}−1)/8} = 1 when p ≡ 1 (mod 8) or p ≡ −1 (mod 8), and (−1)^{(p^{2}−1)/8} = −1 when p ≡ 3 (mod 8) or p ≡ −3 (mod 8).

Let m = (p − 1)/2. It follows from Lemma 1.38 that (\frac{2}{p}) = (−1)^{r}, where

r is the number of integers x between 1 and m for which 2x is not congruent modulo p to any integer between 1 and m. But the integers x with this property are those for which m/2 < x ≤ m. Thus r = m/2 if m is even, and r = (m + 1)/2 if m is odd.

If p ≡ 1 (mod 8) then m is divisible by 4 and hence r is even. If p ≡ 3 (mod 8) then m ≡ 1 (mod 4) and hence r is odd. If p ≡ 5 (mod 8) then m ≡ 2 (mod 4) and hence r is odd. If p ≡ 7 (mod 8) then m ≡ 3 (mod 4)

and hence r is even. Therefore (\frac{2}{p}) = 1 when p ≡ 1 (mod 8) and when

p ≡ 7 (mod 8), and (\frac{2}{p}) = −1 when p ≡ 3 (mod 8) and p ≡ 5 (mod 8).

Thus (\frac{2}{p}) = (−1)^{(p^{2}−1)/8} for all odd prime numbers p, as required.

1.14 Quadratic Reciprocity

Theorem 1.40 (Quadratic Reciprocity Law) Let p and q be distinct odd prime numbers. Then

(\frac{p}{q})(\frac{q}{p}) = (−1)^{(p−1)(q−1)/4}

Proof Let S be the set of all ordered pairs (x, y) of integers x and y satisfying 1 ≤ x ≤ m and 1 ≤ y ≤ n, where p = 2m + 1 and q = 2n + 1. We must prove that (\frac{p}{q})(\frac{q}{p}) = (−1)^{mn}.

First we show that (\frac{p}{q}) = (−1)^{a}, where a is the number of pairs (x, y)

of integers in S satisfying −n ≤ py − qx ≤ −1. If (x, y) is a pair of integers in S satisfying −n ≤ py − qx ≤ −1, and if z = qx − py, then 1 ≤ y ≤ n, 1 ≤ z ≤ n and py ≡ −z (mod q). On the other hand, if (y, z) is a pair of integers such that 1 ≤ y ≤ n, 1 ≤ z ≤ n and py ≡ −z (mod q) then there is a unique positive integer x such that z = qx − py. Moreover qx = py + z ≤ (p + 1)n = 2n(m + 1) and q > 2n, and therefore x < m + 1. It follows that the pair (x, y) of integers is in S, and −n ≤ py − qx ≤ −1. We deduce that the number a of pairs (x, y) of integers in S satisfying −n ≤ py − qx ≤ −1 is equal to the number of pairs (y, z) of integers satisfying 1 ≤ y ≤ n, 1 ≤ z ≤ n and py ≡ −z (mod q). It now follows from Lemma 1.38 that (\frac{p}{q}) = (−1)^{a}.

Similarly (\frac{q}{p}) = (−1)^{b}, where b is the number of pairs (x, y) in S satisfying

1 ≤ py − qx ≤ m.

If x and y are integers satisfying py − qx = 0 then x is divisible by p and y is divisible by q. It follows from this that py − qx ≠ 0 for all pairs (x, y) in S. The total number of pairs (x, y) in S is mn. Therefore mn = a+b+c+d, where c is the number of pairs (x, y) in S satisfying py − qx < −n and d is the number of pairs (x, y) in S satisfying py − qx > m.

Let (x, y) be a pair of integers in S, and let and let x′ = m + 1 − x and y′ = n + 1 − y. Then the pair (x′, y′) also belongs to S, and py′ − qx′ = m − n − (py − qx). It follows that py − qx > m if and only if py′ − qx′ < −n. Thus there is a one-to-one correspondence between pairs (x, y) in S satisfying py − qx > m and pairs (x′, y′) in S satisfying py′ − qx′ < −n, where (x′, y′) = (m + 1 − x, n + 1 − y) and (x, y) = (m + 1 − x′, n + 1 − y′). Therefore c = d, and thus mn = a + b + 2c. But then (−1)^{mn} = (−1)^{a}(−1)^{b} = (\frac{p}{q})(\frac{q}{p}), as

required.

Corollary 1.41 Let p and q be distinct odd prime numbers. If p ≡ 1 (mod 4) or q ≡ 1 (mod 4) then (\frac{p}{q}) = (\frac{q}{p}). If p ≡ 3 (mod 4) and

q ≡ 3 (mod 4) then (\frac{p}{q}) = −(\frac{q}{p}).

Example We wish to determine whether or not 654 is a quadratic residue modulo the prime number 239. Now 654 = 2 × 239 + 176 and thus 654 ≡ 176 (mod 239). Also 176 = 16 × 11. Therefore

(\frac{654}{239}) = (\frac{176}{239}) = (\frac{16}{239})(\frac{11}{239}) = (\frac{4}{239})^{2}(\frac{11}{239}) = (\frac{11}{239})

But (\frac{11}{239}) = −(\frac{239}{11}) by the Law of Quadratic Reciprocity. Also 239 ≡ 8 (mod 11). Therefore

(\frac{239}{11}) = (\frac{8}{11}) = (\frac{2}{11})^{3} = (−1)^{3} = −1

It follows that (\frac{654}{239}) = +1 and thus 654 is a quadratic residue of 239, as required.

1.15 The Jacobi Symbol

Let s be an odd positive integer. If s > 1 then s = p_{1}p_{2} ⋯ p_{m}, where p_{1}, p_{2}, …, p_{m} are odd prime numbers. For each integer x we define the Jacobi symbol (\frac{x}{s}) by

(\frac{x}{s}) = ∏_{i=1}^{m}(\frac{x}{p_{i}} )

(i.e., (\frac{x}{s}) is the product of the Legendre symbols (\frac{x}{p_{i}} ) for i = 1, 2, …, m.)

We define (\frac{x}{1}) = 1.

Note that the Jacobi symbol can have the values 0, +1 and −1.

Lemma 1.42 Let s be an odd positive integer, and let x be an integer. Then (\frac{x}{s}) ≠ 0 if and only if x is coprime to s.

Proof Let s = p_{1}p_{2} ⋯ p_{m}, where p_{1}, p_{2}, …, p_{m} are odd prime numbers. Suppose that x is coprime to s. Then x is coprime to each prime factor of s, and hence (\frac{x}{p_{i}} ) = ±1 for i = 1, 2, …, m. It follows that (\frac{x}{s}) = ±1 and thus

(\frac{x}{s}) ≠ 0.

Next suppose that x is not coprime to s. Let p be a prime factor of the greatest common divisor of x and s. Then p = p_{i}, and hence (\frac{x}{p_{i}} ) = 0 for

some integer i between 1 and m. But then (\frac{x}{s}) = 0.

Lemma 1.43 Let s be an odd positive integer, and let x and x′ be integers. Suppose that x ≡ x′ (mod s). Then (\frac{x}{s}) = (\frac{x′}{s} ).

Proof If x ≡ x′ (mod s) then x ≡ x′ (mod p) for each prime factor p of s, and therefore (\frac{x}{p}) = (\frac{x′}{p} ) for each prime factor of s. Therefore (\frac{x}{s}) =

(\frac{x′}{s} ).

Lemma 1.44 Let x and y be integers, and let s and t be odd positive integers.

Then (\frac{xy}{s} ) = (\frac{x}{s})(\frac{y}{s}) and (\frac{x}{st}) = (\frac{x}{s})(\frac{x}{t}).

Proof (\frac{xy}{p} ) = (\frac{x}{p})(\frac{y}{p}) for all prime numbers p (Corollary 1.34). The required result therefore follows from the definition of the Jacobi symbol.

Lemma 1.45 (\frac{x^{2}}{s} ) = 1 and (\frac{x}{s^{2}} ) = 1 for for all odd positive integers s and all integers x that are coprime to s.

Proof This follows directly from Lemma 1.44 and Lemma 1.42.

Theorem 1.46 (\frac{−1}{s}) = (−1)^{(s−1)/2} for all odd positive integers s.

Proof Let f(s) = (−1)^{(s−1)/2}(\frac{−1}{s}) for each odd positive integer s. We must prove that f(s) = 1 for all odd positive integers s. If s and t are odd positive integers then

(st − 1) − (s − 1) − (t − 1) = st − s − t + 1 = (s − 1)(t − 1)

But (s − 1)(t − 1) is divisible by 4, since s and t are odd positive integers. Therefore (st−1)/2 ≡ (s−1)/2+(t−1)/2 (mod 2), and hence (−1)^{(st−1)/2} = (−1)^{(s−1)/2}(−1)^{(t−1)/2}. It now follows from Lemma 1.44 that f(st) = f(s)f(t) for all odd numbers s and t. But f(p) = 1 for all prime numbers p, since

(\frac{−1}{p}) = (−1)^{(p−1)/2} (Lemma 1.37). It follows that f(s) = 1 for all odd

positive integers s, as required.

Theorem 1.47 (\frac{2}{s}) = (−1)^{(s^{2}−1)/8} for all odd positive integers s.

Proof Let g(s) = (−1)^{(s^{2}−1)/8}(\frac{2}{s}) for each odd positive integer s. We must prove that g(s) = 1 for all odd positive integers s. If s and t are odd positive integers then

(s^{2}t^{2} − 1) − (s^{2} − 1) − (t^{2} − 1) = s^{2}t^{2} − s^{2} − t^{2} + 1 = (s^{2} − 1)(t^{2} − 1).

But (s^{2} − 1)(t^{2} − 1) is divisible by 64, since s^{2} ≡ 1 (mod 8) and t^{2} ≡ 1 (mod 8). Therefore (s^{2}t^{2} − 1)/8 ≡ (s^{2} − 1)/8 + (t^{2} − 1)/8 (mod 8), and hence (−1)^{(s^{2}t^{2}−1)/8} = (−1)^{(s^{2}−1)/8}(−1)^{(t^{2}−1)/8}. It now follows from Lemma 1.44 that g(st) = g(s)g(t) for all odd numbers s and t. But g(p) = 1 for all prime

numbers p, since (\frac{2}{p}) = (−1)^{(p^{2}−1)/8} (Lemma 1.39). It follows that g(s) = 1

for all odd positive integers, as required.

Theorem 1.48 (\frac{s}{t})(\frac{t}{s}) = (−1)^{(s−1)(t−1)/4} for all odd positive integers s and t.

Proof Let h(s, t) = (−1)^{(s−1)(t−1)/4}(\frac{s}{t})(\frac{t}{s}). We must prove that h(s, t) = 1 for all odd positive integers s and t. Now h(s_{1}s_{2}, t) = h(s_{1}, t)h(s_{2}, t) and h(s, t_{1})h(s, t_{2}) = h(s, t_{1}t_{2}) for all odd positive integers s, s_{1}, s_{2}, t, t_{1} and t_{2}.

Also h(s, t) = 1 when s and t are prime numbers by the Law of Quadratic Reciprocity (Theorem 1.40). It follows from this that h(s, t) = 1 when s is an odd positive integer and t is a prime number, since any odd positive integer is a product of odd prime numbers. But then h(s, t) = 1 for all odd positive integers s and t, as required.

The results proved above can be used to calculate Jacobi symbols, as in the following example.

Example We wish to determine whether or not 442 is a quadratic residue

modulo the prime number 751. Now (\frac{442}{751}) = (\frac{2}{751})(\frac{221}{751}). Also (\frac{2}{751}) =

1, since 751 ≡ 7 (mod 8) (Theorem 1.39). Also (\frac{221}{751}) = (\frac{751}{221}) (Theorem 1.48), and 751 ≡ 88 (mod 221). Thus

(\frac{442}{751}) = (\frac{751}{221}) = (\frac{88}{221}) = (\frac{2}{221})^{3}(\frac{11}{221}).

Now (\frac{2}{221}) = −1, since 221 ≡ 5 (mod 8) (Theorem 1.47). Also it follows from Theorem 1.48 that

(\frac{11}{221}) = (\frac{221}{11}) = (\frac{1}{11}) = 1,

since 221 ≡ 1 (mod 4) and 221 ≡ 1 (mod 11). Therefore (\frac{442}{751}) = −1, and thus 442 is a quadratic non-residue of 751. The number 221 is not prime, since 221 = 13 × 17. Thus the above calculation made use of Jacobi symbols that are not Legendre symbols.