O. Forster: Algorithmic Number Theory

8. Quadratic Residues, Quadratic Reciprocity Law

8.1. Quadratic residues. Let m be an integer > 2. An integer a is called a quadratic residue modulo m iff there exists an integer x with

x^{2} ≡ a mod m.

This means that the class of a in the ring ℤ/m is a square. Of particular importance is the case where m = p is an odd prime. Since 0 is always a square, we consider the group (ℤ/p)^{∗} = 𝔽_{p}^{∗} of non-zero elements. The squaring map

sq : 𝔽_{p}^{∗} ⟶ 𝔽_{p}^{∗}, x ↦ sq(x) := x^{2}

is a group homomorphism. The kernel of sq consists of the solutions of the equation x^{2} = 1 ⟺ (x + 1)(x − 1) = 0, hence Ker(sq) = {±1}. Therefore the image sq(𝔽_{p}^{∗}) = (𝔽_{p}^{∗})^{2}, which is the subgroup of squares in 𝔽_{p}^{∗}, has (#F_{p}^{∗})/2 = (p − 1)/2 elements. Hence there are exactly as many squares as non-squares in 𝔽_{p}^{∗}. A further consequence is that the product of two non-squares is a square.

8.2. The Legendre symbol. For an odd prime p and an integer a which is coprime to p, the Legendre symbol (\frac{a}{p}) is defined by

(\frac{a}{p}) = \{ \begin{matrix}+1, & if a is a quadratic residue mod p, \\ −1, & if a is not a quadratic residue mod p. \end{matrix}

This definition is extended to all integers a by setting

(\frac{a}{p}) = 0 for p | a.

The Jacobi symbol has the following properties:

(\frac{a}{p}) = (\frac{a′}{p} ) if a ≡ a′ mod p,

and

(\frac{ab}{p}) = (\frac{a}{p})(\frac{b}{p}) for all a, b ∈ ℤ.

Therefore the map x ↦ (\frac{x}{p}) can be seen as a group homomorphism 𝔽_{p}^{∗} → \{±1\}, which fits into an exact sequence

1 ⟶ \{±1\} ⟶ 𝔽_{p}^{∗} ⟶^{sq} 𝔽_{p}^{∗} ⟶^{(_{\overline{p}})} \{±1\} ⟶ 1.

The following is an important criterion of Euler to decide whether an integer a is a quadratic residue mod p.

Chap. 8 last revised: 2002-07-03 8.1

8. Quadratic residues

8.3. Theorem (Euler). Let p be an odd prime. Then

a^{(p−1)/2} ≡ (\frac{a}{p}) mod p for all a ∈ ℤ.

Proof. If p | a, then both sides of the equation are congruent 0. We may therefore assume p ∤ a.

a) Suppose first that a is a square mod p, i.e. a = b^{2} mod p for some integer b. Then

a^{(p−1)/2} ≡ b^{p−1} ≡ 1

by the theorem of Fermat.

b) Let g be a primitive root mod p. Since g^{p−1} ≡ 1 mod p and g^{(p−1)/2} ≢ 1 mod p, we must have g^{(p−1)/2} ≡ −1 mod p. If a is a non-square mod p, then a ≡ g^{s} mod p with an odd integer s. Now

s (p − 1)/2 ≡ (p − 1)/2 mod (p − 1),

hence

a^{(p−1)/2} ≡ g^{s(p−1)/2} ≡ g^{(p−1)/2} ≡ −1 mod p, q.e.d.

As an application of the criterion of Euler we can prove

8.4. Theorem (Supplements to the reciprocity law). Let p be an odd prime. Then

1) (\frac{−1}{p}) = (−1)^{(p−1)/2} = \{ \begin{matrix}+1, & if p ≡ 1 mod 4, \\ −1, & if p ≡ 3 mod 4, \end{matrix}

2) (\frac{2}{p}) = (−1)^{(p^{2}−1)/8} = \{ \begin{matrix}+1, & if p ≡ ±1 mod 8, \\ −1, & if p ≡ ±3 mod 8. \end{matrix}

Proof. The first assertion is a direct consequence of theorem 8.3.

Ad 2). We have to calculate 2^{(p−1)/2} mod p. We use a little trick and pass to the ring ℤ[i] of Gaussian integers. In ℤ[i] we have

2 = −i(1 + i)^{2},

therefore 2^{(p−1)/2} = (−i)^{(p−1)/2}(1 + i)^{p−1}, which implies

2^{(p−1)/2}(1 + i) = (−i)^{(p−1)/2}(1 + i)^{p}.

To calculate (1 + i)^{p}, we use the binomial theorem. Since the binomial coefficients \binom{p}{k} are divisible by p for all k = 1, 2, …, p − 1, it follows

(1 + i)^{p} ≡ 1 + i^{p} mod p.

8.2 (Of course the congruence mod p is to be understood separately for the real and imaginary part.) Therefore 2^{(p−1)/2} is congruent mod p to the real part of

z_{p} := (−i)^{(p−1)/2}(1 + i^{p}).

It is easily seen that z_{p} depends only on p mod 8 and

z_{p} = \{ \begin{matrix}1 + i & if p ≡ 1 mod 8, \\ −1 − i & if p ≡ 3 mod 8, \\ −1 − i & if p ≡ 5 mod 8, \\ 1 + i & if p ≡ 7 mod 8. \end{matrix}

This implies assertion 2) of the theorem, q.e.d.

8.5. Gauss sums. As we have seen in the proof of the preceeding theorem, it is sometimes helpful to use complex numbers. This will become even more apparent in the following developments. Let p be an odd prime and

ζ_{p} := e^{2πi/p} ∈ ℂ.

ζ_{p} is a primitive p-th root of unity. We define the Gauss sum S(p) as

S(p) := ∑_{k=1}^{p−1}(\frac{k}{p})ζ_{p}^{k}.

This is an element of the ring ℤ[ζ_{p}]. Since ζ_{p} is a root of the so called cyclotomic polynomial

Φ_{p}(X) = X^{p−1} + X^{p−2} + … + X + 1,

which is irreducible in the ring ℚ[X], every element z ∈ ℤ[ζ_{p}] has a unique representation as

z = ∑_{k=0}^{p−2} a_{k}ζ_{p}^{k} with a_{k} ∈ ℤ.

In particular

ζ_{p}^{p−1} = − ∑_{k=0}^{p−2} ζ_{p}^{k}.

Examples. i) Let p = 3. We have

ζ_{3} = e^{2πi/3} = \frac{1}{2}(−1 + i\sqrt{3}),
ζ_{3}^{2} = e^{4πi/3} = e^{−2πi/3} = \frac{1}{2}(−1 − i\sqrt{3})

8.3

8. Quadratic residues

and

S(3) = (\frac{1}{3})ζ_{3} + (\frac{2}{3})ζ_{3}^{2} = \frac{1}{2}(−1 + i\sqrt{3}) − \frac{1}{2}(−1 − i\sqrt{3}) = i\sqrt{3}.

ii) For p = 5 one has

ζ_{5} = e^{2πi/5} = cos(2π/5) + i sin(2π/5),
ζ_{5}^{2} = e^{4πi/5} = cos(4π/5) + i sin(4π/5),
ζ_{5}^{3} = \overline{ζ_{5}^{2}} = cos(4π/5) − i sin(4π/5),
ζ_{5}^{4} = \overline{ζ_{5}} = cos(2π/5) − i sin(2π/5),

and (\frac{1}{5}) = 1, (\frac{2}{5}) = −1, (\frac{3}{5}) = −1, (\frac{4}{5}) = 1, therefore

S(5) = ζ_{5} − ζ_{5}^{2} − ζ_{5}^{3} + ζ_{5}^{4} = (ζ_{5} + \overline{ζ_{5}}) − (ζ_{5}^{2} + \overline{ζ_{5}^{2}})
= 2 cos(2π/5) − 2 cos(4π/5) = \sqrt{5}.

This follows from the explicit formulas

cos(2π/5) = \frac{1}{2}(−1 + \sqrt{5}),
cos(4π/5) = \frac{1}{2}(−1 − \sqrt{5}),

and can also be derived from part a) of the following theorem. 8.6. Theorem. The Gauss sum for the odd prime p satisfies

a) S(p)^{2} = (\frac{−1}{p})p.

b) If q ≠ p is another odd prime, then

S(p)^{q} ≡ (\frac{q}{p})S(p) mod q.

Here the congruence mod q means that the difference of the right hand and left hand side is an element of qℤ[ζ_{p}]. Proof. a) To abbreviate the notation, we write ζ instead of ζ_{p}.

S(p)^{2} = ∑_{k∈𝔽_{p}^{∗}}(\frac{k}{p})ζ^{k} ∑_{ℓ∈𝔽_{p}^{∗}}(\frac{ℓ}{p})ζ^{ℓ} = ∑_{k,ℓ∈𝔽_{p}^{∗}}(\frac{kℓ}{p})ζ^{k+ℓ}
= ∑_{k∈𝔽_{p}^{∗}} ∑_{s∈𝔽_{p}^{∗}}(\frac{kks}{p})ζ^{k+ks} = ∑_{s∈𝔽_{p}^{∗}}(\frac{s}{p}) ∑_{k∈𝔽_{p}^{∗}}(ζ^{1+s})^{k}.

8.4 Here we have substituted ℓ = ks. When s runs through all elements of 𝔽_{p}^{∗}, also ks runs through all elements of 𝔽_{p}^{∗}. Now we have to distinguish the cases s + 1 = 0 and s + 1 ≠ 0. In the latter case, ζ^{1+s} is a non-trivial p-th root of unity, hence

∑_{k=0}^{p−1}(ζ^{1+s})^{k} = 0 ⟹ ∑_{k∈𝔽_{p}^{∗}}(ζ^{1+s})^{k} = −1

If s + 1 = 0, then (ζ^{1+s})^{k} = 1 for all k. It follows

S(p)^{2} = (\frac{−1}{p})(p − 1) − ∑_{s=1}^{p−2}(\frac{s}{p}) = (\frac{−1}{p})p − ∑_{s=1}^{p−1}(\frac{s}{p}).

Now ∑_{s=1}^{p−1}(\frac{s}{p}) = 0 (since there are as many quadratic residues as non-residues), which

implies

S(p)^{2} = (\frac{−1}{p})p, q.e.d.

b) We make use of the formula

(x_{1} + x_{2} + … + x_{r})^{q} ≡ x_{1}^{q} + x_{2}^{q} + … + x_{r}^{q} mod q

This follows by induction on r from the binomial theorem and the fact that q | \binom{q}{k} for 1 ≤ k ≤ q − 1. Applying this to the definition of S(p) we get

S(p)^{q} ≡ ∑_{k∈𝔽_{p}^{∗}}(\frac{k}{p})ζ^{qk} ≡ ∑_{k∈𝔽_{p}^{∗}}(\frac{qqk}{p} )ζ^{qk} ≡  [Subst. s = qk]

≡ ∑_{s∈𝔽_{p}^{∗}}(\frac{q}{p})(\frac{s}{p})ζ^{s} ≡ (\frac{q}{p})S(p) mod q, q.e.d.

8.7. Theorem (Quadratic reciprocity law of Gauss). Let p ≠ q be odd primes. Then

(\frac{p}{q})(\frac{q}{p}) = (−1)^{\frac{p−1}{2} · \frac{q−1}{2}} .

In other words,

(\frac{p}{q}) = (\frac{q}{p}) if p ≡ 1 mod 4 or q ≡ 1 mod 4,
(\frac{p}{q}) = −(\frac{q}{p}) if p ≡ 3 mod 4 and q ≡ 3 mod 4.

Proof. We start with the formula of theorem 8.6.b) and multiply it by S(p).

S(p)^{q+1} ≡ (\frac{q}{p})S(p)^{2} mod q.

8.5 Using 8.6.a) for S(p)^{2} we get

(\frac{−1}{p})^{(q+1)/2}p^{(q+1)/2} ≡ (\frac{q}{p})(\frac{−1}{p})p mod q.

Since p is invertible mod q and (\frac{−1}{p}) = ±1, we can divide both sides by (\frac{−1}{p})p and obtain

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

Now we use theorem 8.4.1 and the Euler criterion 8.3, yielding

(−1)^{\frac{p−1}{2} \frac{q−1}{2}} (\frac{p}{q}) ≡ (\frac{q}{p}) mod q.

This congruence was derived as a congruence in ℤ[ζ_{p}], i.e. the difference of the left hand and right hand side is an element of qℤ[ζ_{p}]. Since qℤ[ζ_{p}] ∩ ℤ = qℤ, this is already a congruence in ℤ. Both sides of the congruence are ±1 and q ≥ 3, so we must actually have an equation

(−1)^{\frac{p−1}{2} \frac{q−1}{2}} (\frac{p}{q}) = (\frac{q}{p}),

which is the assertion of the theorem.

8.8. Fermat primes. It is easy to see that if an integer of the form 2^{k} + 1 is prime, then k must be a power of 2. Otherwise we could write k = ℓm with ℓ ≥ 3 odd and m > 1, and 2^{k} + 1 = (2^{m})^{ℓ} + 1 is divisible by 2^{m} + 1. The numbers

F_{n} := 2^{2^{n}} + 1

were conjectured by Fermat to be primes. This is true for

F_{0} = 2^{1} + 1 = 3,
F_{1} = 2^{2} + 1 = 5,
F_{2} = 2^{4} + 1 = 17,
F_{3} = 2^{8} + 1 = 257,
F_{4} = 2^{16} + 1 = 65537,

but already Euler showed that F_{5} = 2^{32} + 1 = 4 294 967 297 is divisible by 641. Until today, no Fermat prime F_{n} with index n ≥ 5 was found. In order to derive a criterion for the primality of F_{n}, we first prove:

If F_{n} is prime, (n ≥ 1), then (\frac{3}{F_{k}} ) = −1.

8.6 Since F_{n} ≡ 1 mod 4, the reciprocity law implies (\frac{3}{F_{n}}) = (\frac{F_{n}}{3} ). We have the following congruence modulo 3

F_{n} = 2^{2^{n}} + 1 ≡ (−1)^{2^{n}} + 1 ≡ 2 mod 3.

Therefore (\frac{3}{F_{n}}) = (\frac{2}{3}) = −1, q.e.d.

8.9. Theorem (Pepin 1877). The number F_{n} = 2^{2^{n}} + 1, (n ≥ 1), is prime iff

3^{(F_{n}−1)/2} ≡ −1 mod F_{n}.

Proof. The necessity of this condition follows from the Euler criterion (theorem 8.3).

Suppose now that the condition is satisfied. Then 3^{F_{n}−1} ≡ 1 mod F_{n}, hence the order of 3 in the multiplicative group (ℤ/F_{n})^{∗} is a divisor of F_{n} − 1 = 2^{2^{n}}. From 3^{(F_{n}−1)/2} ≡ −1 it follows that ord_{(ℤ/F_{n})^{∗}}(3) = 2^{2^{n}}. Therefore (ℤ/F_{n})^{∗} must have at least 2^{2^{n}} = F_{n} − 1 elements. This shows that F_{n} is prime.

Remark. Since (F_{n} − 1)/2 = 2^{2^{n}−1}, the calculation of 3^{(F_{n}−1)/2} mod F_{n} requires 2^{n} − 1 squarings mod F_{n}. The number F_{n} has 2^{n} + 1 binary digits.

8.10. Theorem. Every possible prime divisor of F_{n}, n ≥ 5, has the form

p = h · 2^{n+2} + 1

with an integer h.

Example. The prime divisor 641 of F_{5}, which was found by Euler, is in fact of this form:

641 = 5 · 128 + 1 = 5 · 2^{5+2} + 1.

Proof. If p | F_{n} = 2^{2^{n}} + 1, then

2^{2^{n}} ≡ −1 mod p ⟹ 2^{2^{n+1}} ≡ 1 mod p.

This shows that the element 2 mod p in 𝔽_{p}^{∗} has order 2^{n+1}; in particular we have 2^{n+1} | (p − 1). It follows that p ≡ 1 mod 8, hence by theorem 8.4.2

(\frac{2}{p}) = 1.

Therefore there exists an element x ∈ 𝔽_{p}^{∗} such that x^{2} ≡ 2 mod p. This element has order 2^{n+2} in 𝔽_{p}^{∗}, hence 2^{n+2} | (p − 1), which implies the assertion of the theorem.

8.11. Proposition. Every pair of Fermat numbers F_{n}, F_{m}, n ≠ m, is relatively prime, i.e.

gcd(F_{n}, F_{m}) = 1.

8.7 Proof. We may assume n < m. If F_{n} and F_{m} were not relatively prime, there would exist a common prime divisor p of F_{n} and F_{m}. Then

2^{2^{n}} ≡ −1 mod p and 2^{2^{m}} ≡ (2^{2^{n}})^{2^{m−n}} ≡ −1 mod p,

which is a contradiction.

8.12. The Jacobi symbol. If one wants to apply the reciprocity law to calculate the Legendre symbol (\frac{a}{p}), the argument a has to be decomposed into a product of primes. This may be difficult for large a. To overcome this difficulty, Jacobi has defined a generalization of the Jacobi symbol. Let m be an odd number ≥ 3 and

m = p_{1} · p_{2} · . . . · p_{r}

a prime factorization of m. (The primes p_{i} are not necessarily distinct.) Then for a ∈ ℤ the Jacobi symbol is defined by

(\frac{a}{m}) := ∏_{i=1}^{r}(\frac{a}{p_{i}} ).

The following properties follow immediately from the corresponding properties of the Legendre symbol:

(\frac{a}{m}) = (\frac{b}{m})  if a ≡ b mod m,
(\frac{ab}{m}) = (\frac{a}{m})(\frac{b}{m}) for all a, b ∈ ℤ,
(\frac{a}{m}) = 0 ⟺ gcd(a, m) > 0.

Note however the following difference to the Legendre symbol: (\frac{a}{m}) = 1 is a necessary, but in general not sufficient condition for a to be a quadratic residue modulo m. For example,

(\frac{2}{15}) = (\frac{2}{3})(\frac{2}{5}) = (−1)(−1) = 1,

but 2 is not a quadratic residue modulo 15.

8.13. Lemma. For an odd integer x ∈ ℤ define ε(x), ω(x) ∈ ℤ/2 by

ε(x) := \frac{x − 1}{2} mod 2, ω(x) := \frac{x^{2} − 1}{8} mod 2.

Then ε and ω induce group homomorhisms

ε : (ℤ/4)^{∗} ⟶ ℤ/2 and ω : (ℤ/8)^{∗} ⟶ ℤ/2

8.8 from the multiplicative groups (ℤ/4)^{∗} and (ℤ/8)^{∗} to the additive group ℤ/2.

Proof. It is clear that ε(x) depends only on x mod 4 and ω(x) depends only on x mod 8 and we have

\begin{matrix}x & 1 & 3 \\ ε(x) & 0 & 1 \end{matrix}  \begin{matrix}x & 1 & 3 & 5 & 7 \\ ω(x) & 0 & 1 & 1 & 0 \end{matrix}

The formulas ε(xy) = ε(x) + ε(y) and ω(xy) = ω(x) + ω(y) can be easily checked by a complete case distinction.

8.14. Theorem (Reciprocity law for the Jacobi symbol). Let m ≥ 3 be an odd integer. Then

a) (1^{st} supplement)

(\frac{−1}{m}) = (−1)^{(m−1)/2} = \{ \begin{matrix}+1, & if m ≡ 1 mod 4, \\ −1, & if m ≡ 3 mod 4, \end{matrix}

b) (2^{nd} supplement)

(\frac{2}{m}) = (−1)^{(m^{2}−1)/8} = \{ \begin{matrix}+1, & if m ≡ ±1 mod 8, \\ −1, & if m ≡ ±3 mod 8. \end{matrix}

c) (reciprocity law) If k ≥ 3 is another odd integer which is coprime to m, then

(\frac{k}{m})(\frac{m}{k}) = (−1)^{\frac{k−1}{2} · \frac{m−1}{2}} .

Proof. Let m = p_{1} · . . . · p_{r} be a decomposition of m into a product of primes.

a) By definition we have

(\frac{−1}{m}) = ∏_{i=1}^{r}(\frac{−1}{p_{i}}) = ∏_{i=1}^{r}(−1)^{(p_{i}−1)/2} = (−1)^{∑ ε(p_{i})},

where ε was defined in the preceding lemma. By the same lemma,

∑ ε(p_{i}) ≡ ε(∏ p_{i}) ≡ ε(m) mod 2,

hence

(\frac{−1}{m}) = (−1)^{ε(m)} = (−1)^{(m−1)/2}.

b) Similarly,

(\frac{2}{m}) = ∏_{i=1}^{r}(\frac{2}{p_{i}} ) = ∏_{i=1}^{r}(−1)^{(p_{i}^{2}−1)/8} = (−1)^{∑ ω(p_{i})}
= (−1)^{ω(m)} = (−1)^{(m^{2}−1)/8}.

8.9 c) Let k = q_{1} · . . . · q_{s} be a prime decomposition of k. Then by definition and the reciprocity law for the Legendre symbol

(\frac{k}{m})(\frac{m}{k}) = ∏_{i,j}(\frac{q_{j}}{p_{i}} )(\frac{p_{i}}{q_{j}} ) = ∏_{i,j}(−1)^{ε(q_{j})ε(p_{i})} = (−1)^{∑_{i,j} ε(q_{j})ε(p_{i})}

Now

∑_{i,j} ε(q_{j})ε(p_{i}) ≡ (∑_{j} ε(q_{j}))(∑_{i} ε(p_{i})) ≡ ε(k)ε(m) ≡ \frac{k − 1}{2} · \frac{m − 1}{2} mod 2,

which proves the theorem.

8.15. Algorithm for the Jacobi symbol. The reciprocity law can be applied to get an efficient algorithm to calculate the Jacobi symbol. Suppose we want to calculate (\frac{a}{m}) with m ≥ 3 odd and a ∈ ℤ. In a similar way as for the Euclidean algorithm, set

x_{0} := a, x_{1} := m

We now define inductively integers x_{2}, x_{3}, … x_{k} until we arrive at x_{k} ∈ {0, 1}. To get x_{i} from x_{i−2}, x_{i−1} we divide x_{i−2} by x_{i−1} with rest

x_{i−2} = q_{i−1}x_{i−1} + y_{i}, 0 ≤ y_{i} < x_{i−1}.

If y_{i} = 0, we stop. Otherwise we write y_{i} = 2^{t_{i}}x_{i} with x_{i} odd; if x_{i} = 1, we stop, otherwise we continue. In this way we get a chain of equations

x_{0} = q_{1}x_{1} + 2^{t_{1}}x_{2},
x_{1} = q_{2}x_{2} + 2^{t_{2}}x_{3},
⋮  ⋮
x_{i−1} = q_{i}x_{i} + 2^{t_{i}}x_{i+1},
⋮  ⋮
x_{k−1} = q_{k}x_{k} + 2^{t_{k}}x_{k+1},

where x_{i} ≥ 3 odd for all 1 ≤ i ≤ k and x_{k+1} = 0 or 1. We show now how one can reduce the calculation of (\frac{x_{i−1}}{x_{i}}) to the calculation of (\frac{x_{i}}{x_{i+1}} ) for i = 1, 2, ... . We have for all i ≤ k

(\frac{x_{i−1}}{x_{i}} ) = (\frac{2}{x_{i}} )^{t_{i}}(\frac{x_{i+1}}{x_{i}} ) = (−1)^{t_{i}ω(x_{i})}(\frac{x_{i+1}}{x_{i}} ),

where ω(x) was defined in lemma 8.13. If i = k, we have x_{i+1} = 0, 1 and we can stop. Else we have x_{i} ≥ 3 odd, so we can apply the quadratic reciprocity theorem to get

(\frac{x_{i+1}}{x_{i}} ) = (−1)^{ε(x_{i})+ε(x_{i+1})}(\frac{x_{i}}{x_{i+1}} ),

8.10

O. Forster: Algorithmic Number Theory

yielding

(\frac{x_{i−1}}{x_{i}} ) = (−1)^{t_{i}ω(x_{i})+ε(x_{i})+ε(x_{i+1})}(\frac{x_{i}}{x_{i+1}} ).

This is the desired recursion relation which allows to calculate the Jacobi symbol (\frac{a}{m}) = (\frac{x_{0}}{x_{1}} ) in k steps. As in the case of the Euclidean algorithm the complexity is O(log m).

8.11