(v) (2 | n) = (’1)(n ;

m’1 n’1

(vi) (m | n) = (’1) (n | m).

2 2

Proof. Parts (i)“(iii) follow directly from the de¬nition (exercise).

For parts (iv) and (vi), one can easily verify (exercise) that for odd integers

n1 , . . . , n k ,

k

(ni ’ 1)/2 ≡ (n1 · · · nk ’ 1)/2 (mod 2).

i=1

Part (iv) easily follows from this fact, along with part (ii) of this theorem and

part (i) of Theorem 12.4 (exercise). Part (vi) easily follows from this fact,

along with parts (i) and (ii) of this theorem, and part (v) of Theorem 12.4

(exercise).

For part (v), one can easily verify (exercise) that for odd integers

n1 , . . . , n k ,

(n2 ’ 1)/8 ≡ (n2 · · · n2 ’ 1)/8 (mod 2).

i 1 k

1¤i¤k

Part (v) easily follows from this fact, along with part (ii) of this theorem,

and part (iv) of Theorem 12.4 (exercise). 2

As we shall see later, this theorem is extremely useful from a computa-

tional point of view ” with it, one can e¬ciently compute (a | n), without

having to know the prime factorization of either a or n. Also, in applying

this theorem it is useful to observe that for odd integers m, n,

• (’1)(n’1)/2 = 1 i¬ n ≡ 1 (mod 4);

2 ’1)/8

• (’1)(n = 1 i¬ n ≡ ±1 (mod 8);

• (’1)((m’1)/2)((n’1)/2) = 1 i¬ m ≡ 1 (mod 4) or n ≡ 1 (mod 4).

12.4 Notes 289

It is sometimes useful to view the Jacobi symbol as a group homomor-

phism. Let n be an odd, positive integer. De¬ne the Jacobi map

Z— ’ {±1}

Jn : n

[a]n ’ (a | n).

First, we note that by part (iii) of Theorem 12.8, this de¬nition is unam-

biguous. Second, we note that since gcd(a, n) = 1 implies (a | n) = ±1, the

image of Jn is indeed contained in {±1}. Third, we note that by part (i) of

Theorem 12.8, Jn is a group homomorphism.

Since Jn is a group homomorphism, it follows that its kernel, ker(Jn ), is

a subgroup of Z— .

n

Exercise 12.1. Let n be an odd, positive integer. Show that [Z— : (Z— )2 ] =

n n

r , where r is the number of distinct prime divisors of n.

2

Exercise 12.2. Let n be an odd, positive integer, and consider the Jacobi

map Jn .

(a) Show that (Z— )2 ⊆ ker(Jn ).

n

(b) Show that if n is the square of an integer, then ker(Jn ) = Z— .

n

(c) Show that if n is not the square of an integer, then [Z— : ker(Jn )] = 2

n

— )2 ] = 2r’1 , where r is the number of distinct prime

and [ker(Jn ) : (Zn

divisors of n.

Exercise 12.3. Let p and q be distinct primes, with p ≡ q ≡ 3 (mod 4),

and let n := pq.

(a) Show that [’1]n ∈ ker(Jn ) \ (Z— )2 , and from this, conclude that

n

— )2 in ker(J ) are the two distinct cosets (Z— )2 and

the cosets of (Zn n n

— )2 .

[’1]n (Zn

(b) Show that the squaring map on (Z— )2 is a group automorphism.

n

(c) Let δ ∈ Z— \ker(Jn ). Show that the map from {0, 1}—{0, 1}—(Z— )2 ’

n n

— that sends (a, b, γ) to δ a (’1)b γ is a bijection.

Zn

12.4 Notes

The proof we present here of Theorem 12.4 is essentially the one from Niven

and Zuckerman [68]. Our proof of Theorem 12.8 is essentially the one found

in Bach and Shallit [12].

13

Computational problems related to quadratic

residues

13.1 Computing the Jacobi symbol

Suppose we are given an odd, positive integer n, along with an integer a,

and we want to compute the Jacobi symbol (a | n). Theorem 12.8 suggests

the following algorithm:

t←1

repeat

// loop invariant: n is odd and positive

a ← a mod n

if a = 0

if n = 1 return t else return 0

compute a , h such that a = 2h a and a is odd

if h ≡ 0 (mod 2) and n ≡ ±1 (mod 8) then t ← ’t

if a ≡ 1 (mod 4) and n ≡ 1 (mod 4) then t ← ’t

(a, n) ← (n, a )

forever

That this algorithm correctly computes the Jacobi symbol (a | n) fol-

lows directly from Theorem 12.8. Using an analysis similar to that of Eu-

clid™s algorithm, one easily sees that the running time of this algorithm is

O(len(a) len(n)).

Exercise 13.1. Develop a “binary” Jacobi symbol algorithm, that is, one

that uses only addition, subtractions, and “shift” operations, analogous to

the binary gcd algorithm in Exercise 4.1.

Exercise 13.2. This exercise develops a probabilistic primality test based

290

13.2 Testing quadratic residuosity 291

on the Jacobi symbol. For odd integer n > 1, de¬ne

Gn := {± ∈ Z— : ±(n’1)/2 = [Jn (±)]n },

n

where Jn : Z— ’ {±1} is the Jacobi map.

n

(a) Show that Gn is a subgroup of Z— .

n

(b) Show that if n is prime, then Gn = Z— .

n

Z— .

(c) Show that if n is composite, then Gn n

(d) Based on parts (a)“(c), design and analyze an e¬cient probabilistic

primality test that works by choosing a random, non-zero element

± ∈ Zn , and testing if ± ∈ Gn .

13.2 Testing quadratic residuosity

In this section, we consider the problem of testing whether a is a quadratic

residue modulo n, for given integers a and n, from a computational perspec-

tive.

13.2.1 Prime modulus