Introduction to Analytic Number Theory

p. No prime

many primes of the form 4n + 1.

Let N be any integer > 1. We will show that there is a prime p > N such that p = 1 (mod 4). Let PROOF.

m = (N!)2 + 1.

Note that m is odd, m > 1. Let p be the smallest prime factor of m. None of the numbers 2,3, . . . , N divides m, so p > N. Also, we have (N !)’ = - 1 (mod p). Raising both members to the (p - 1)/2 power we find (N !)P- ’ E (- l)(P- ‘)I2 (mod p). But (N !)“- i = 1 (mod p) by the Euler-Fermat

theorem, so

(- 1)(p-1)/2 = 1 (mod p). Now the difference (- l)(p- 1)/2 - 1 is either 0 or - 2, and it cannot be - 2, because it is divisible by p, so it must be 0. That is, (-

l)(P-

I)/2

=

1.

But this means that (p - 1)/2 is even, so p = 1 (mod 4). In other words, we have shown that for each integer N > 1 there is a prime p > N such that p = 1 (mod 4). Therefore there are infinitely many primes of the form 4n + 1. 0 Simple arguments like those just given for primes of the form 4n - 1 and 4n + 1 can also be adapted to treat other special arithmetic progressions, 147

7: Dirichlet’s

theorem

on primes in arithmetic

progressions

such as 5n - 1,8n - 1,8n - 3 and 8n + 3 (see Sierpinski [67]), but no one has yet found such a simple argument that works for the general progression kn + h.

7.3 The plan of the proof of Dirichlet’s theorem In Theorem 4.10 we derived the asymptotic formula

p;x +

(2)

= log x + O(l),

where the sum is extended over all primes p I x. We shall prove Dirichlet’s theorem as a consequence of the following related asymptotic formula. Theorem 7.3 Ifk

> 0 and (h, k) = 1 we haue,for

(3) psh

IT p5.X

loi3P =

&

all x > 1,

log x + O(l),

(modk)

where the sum is extended over those primes p I x which are congruent to h mod k.

Since log x + co as x + co this relation implies that there are infinitely many primes p = h (mod k), hence infinitely many in the progression nk+h,n=0,1,2

,...

Note that the principal term on the right of (3) is independent of h. Therefore (3) not only implies Dirichlet’s theorem but it also shows that the primes in each of the q(k) reduced residue classesmod k make the same contribution to the principal term in (2). The proof of Theorem 7.3 will be presented through a sequence of lemmas which we have collected together in this section to reveal the plan of the proof. Throughout the chapter we adopt the following notation. The positive integer k represents a fixed modulus, and h is a fixed integer relatively prime to k. The q(k) Dirichlet characters mod k are denoted by xl,

x2

> . . . 3 &p(k)

with x1 denoting the principal character. For x # x1 we write L(1, x) and L’(1, x) for the sums of the following series: L(l,x)

= f x(n), n=l n

L’(l, x) = _ f n=l

148

xyg

n.

7.3: The plan of the proof of Dirichlet’s theorem

The convergence of each of these series was shown in Theorem 6.18. Moreover, in Theorem 6.20 we proved that L(1, x) # 0 if x is real-valued. The symbol p denotes a prime, and I,< x denotes a sum extended over all primes p I x. Lemma 7.4 For x > 1 we have

c 1% p=P $)

pzh

log x + -$)

PSX (modk)

It is clear that Lemma 7.4 will imply Theorem 7.3 if we show that 1 x(P)log P = O(1) PSX P

(4)

for each x # x1. The next lemma expresses this sum in a form which is not extended over primes. Lemma 7.5 For x > 1 and 1( # xl we have

= -L’(l, x)c @p + O(l). c x(p)log “2.x Pp a5.x Therefore Lemma 7.5 will imply (4) if we show that

(5)

&Mn)O(l). c--p-= “2X

This, in turn, will be deduced from the following lemma. Lemma 7.6 For x > 1 and x # x1 we have (6)

j-J,

x) 1

q

=

O(l).

n<x

If L(1, x) # 0 we can cancel L(1, x) in (6) to obtain (5). Therefore, the proof of Dirichlet’s theorem depends ultimately on the nonvanishing of L(1, x) for all x # x1. As already remarked, this was proved for real x # x1 in Theorem 6.20, so it remains to prove that L(1, 1) # 0 for all x # x1 which take complex as well as real values. For this purpose we let N(k) denote the number of nonprincipal characters x mod k such that L(1, x) = 0. If L(1, x) = 0 then L(l,X) = 0 and x # 1 since x is not real. Therefore the characters x for which L(1, x) = 0 occur in conjugate pairs, so N(k) is eoen. Our goal is to prove that N(k) = 0, and this will be deduced from the following asymptotic formula. 149

7: Dirichlet’s

theorem

on primes in arithmetic

progressions

Lemma 7.7 For x > 1 we have

?l ~51

= 1,(;‘k’ logx + O(1).

(modk)

If N(k) # 0 then N(k) 2 2 since N(k) is even, hence the coefficient of log x in (7) is negative and the right member + -cc as x -+ co. This is a contradiction since all the terms on the left are positive. Therefore Lemma 7.7 implies that N(k) = 0. The proof of Lemma 7.7, in turn, will be based on the following asymptotic formula. Lemma 7.8 If x # x1 and L(1, x) = 0 we haue

L’(l,2)n<x 1 ep =log x + O(1). 7.4 Proof of Lemma 7.4 To prove Lemma 7.4 we begin with the asymptotic formula mentioned earlier,

& Ey = log x

(2)

+ O(1)

and extract those terms in the sum arising from primes p = h (mod k). The extraction is done with the aid of the orthogonality relation for Dirichlet characters, as expressed in Theorem 6.16: o?(k)

q(k)

r?lxr(m)Zr(n) = 0

if m = n (mod k), if m + n (mod k).

This is valid for (n, k) = 1. We take m = p and n = h, where (h, k) = 1, then multiply both members by p- ’ log p and sum over all p I x to obtain

In the sum on the left we isolate those terms involving only the principal character x1 and rewrite (8) in the form (9)

q(k)

c p2.X pEh

+

= Xl(h) 1 P5.X

(modk)

Now Xl(h) = 1 and xi@) = 0 unless (p, k) = 1, in which case xi@) = 1. Hence the first term on the right of (9) is given by

(P,k)= 1

150

Plk

7.5: Proof of Lemma

7.5

since there are only a finite number of primes which divide k. Combining (10) with (9) we obtain @)

p1% P = 1 !t%! p5.x P

1

P2.X

p~h

+ ‘fj,(h)

c

r=2

PSX

“‘p

’ + O(1).

(modk)

Using (2) and dividing by q(k) we obtain Lemma 7.4.

cl

7.5 Proof of Lemma 7.5 We begin with the sum

x(n)W

C-y? nSx where A(n) is Mangoldt’s function, and express this sum in two ways. First we note that the definition of A(n) gives us

xW(4

cy= “SX

& *$I, xw;:g P”5.X We separate the terms with a = 1 and write

(11)

x(n)Nn) c-y=

“2.x

1 x(Pbg P PCX

p.

P + c f x(p”Yog P psx a=2 Pa . P’2.X

The second sum on the right is majorized by

so (11) gives us c x(PYog P x(nPW) = Jx y--+ O(l). P p5.X

(12)

Now we recall that A(n) = ‘&

P(d)log(n/d), hence

In the last sum we write n = cd and use the multiplicative to obtain

property of x

(13)

Since x/d 2 1, in the sum over c we may use formula (10) of Theorem 6.18 to obtain

xw% c c-y=

-L’(l,x)

+ 0

.

csxld

151

7: Dirichlet’s

theorem

on primes in arithmetic

progressions

Equation (13) now becomes (14)

The sum in the O-term is ; d&(log x - log d) = 1 [x]log x - c log d = O(1) X

d<x

>

since 1 log d = log[x]!

= x log x + O(x).

d<x

Therefore (14) becomes -L’(l,

x) 1

q

+ O(1)

d<x

which, with (12), proves Lemma 7.5.

Cl

7.6 Proof of Lemma 7.6 We use the generalized Mobius inversion formula proved in Theorem 2.23 which states that if c1is completely multiplicative we have (15)

G(x) = c cr(n)F x “5X

if, and only if, F(x) = c p(n)cc(n)G f . nsx

0

0

We take a(n) = x(n) and F(x) = x to obtain x =

(16)

C hUW n<x

t 0

where G(x) = 1 x(n) X = x 1 q. “5.x nbx By Equation (9) of Theorem 6.18 we can write G(x) = xL(1, x) + O(1). Using this in (16) we find x = 1 @)x(n)

“2X

i

X L(1, 2) + O(1) = xL(1, x) 1 F

I

Now we divide by x to obtain Lemma 7.6. 152

“lx

+ O(X). 0

7.8: Proof of Lemma

7.7

7.7 Proof of Lemma 7.8 We prove Lemma 7.8 and then use it to prove Lemma 7.7. Once again we make use of the generalized Mobius inversion formula (15). This time we take F(x) = x log x to obtain x log x = 1 &r)~(n)G ; nsx 0

(17)

where G(x) =

2 x(n); nsx

log ; = x log x 1 $) n<x

- x 1 ‘@)F “5X

n.

Now we use formulas (9) and (10) of Theorem 6.18 to get

= xL’(1, x) + O(log x) since we are assuming that L(1, x) = 0. Hence (17) gives us x log x = 1 &)x(n) ; L’(1, x) + 0 log ; “5X i ( I AM4 = xL’(1, x) 1 ~ + 0 1 (log x - log n) . nsx n ( n<x > We have already noted that the O-term on the right is O(x) (see the proof of Lemma 7.5). Hence we have &)x(n) ‘(1, x) 1 ~ + O(x), nsx n and when we divide by x we obtain Lemma 7.8. x log x =

XL

0

7.8 Proof of Lemma 7.7 We use Lemma 7.4 with h = 1 to get

pnl

(modk)

In the sum over p on the right we use Lemma 7.5 which states that c PSX

LiP)log

P P

=

-L’(l,

x,)

1

!q)

+

O(1).

“2X

153

7: Dirichlet’s

theorem

on primes in arithmetic

progressions

If L(1, x,) # 0, Lemma 7.6 shows that the right member of (18) is O(1). But if L(1, x,) = 0 then Lemma 7.8 implies -L’(l,

x,) 1 !y

“SX Therefore the sum on the right of (18) is

= -log x + O(1).

$) {-W)lOg x + O(l)), so (18) becomes 1 pal

%

= l ,(Y

log x + O(1).

PSX (modk)

This proves Lemma 7.7 and therefore also Theorem 7.3.

cl

As remarked earlier, Theorem 7.3 implies Dirichlet’s theorem: Theorem 7.9 If k > 0 and (h, k) = 1 there are injinitely arithmetic progression nk + h, n = 0, 1, 2, . . .

many primes in the

7.9 Distribution of primes in arithmetic progressions Ifk > Oand(a,k)

= 1,let %b) =

p;x PI

II (mod

1. k)

The function n,(x) counts the number of primes IX in the progression nk+a,n=0,1,2 ,... Dirichlet’s theorem shows that z,(x) + co as x + co. There is also a prime number theorem for arithmetic progressions which states that (19)

44

n&x)---L-

q(k)

X

q(k) log x

as ’ + O”’

if (a, k) = 1. A proof of (19) is outlined in [44]. The prime number theorem for progressions is suggested by the formula of Theorem 7.3, 1% P

ET

PSX prh

= --& log x + O(1).

(modk)

Since the principal term is independent of h, the primes seem to be equally distributed among the q(k) reduced residue classes mod k, and (19) is a precise statement of this fact. 154

Exercises for Chapter

7

We conclude this chapter by giving an alternate formulation of the prime number theorem for arithmetic progressions. Theorem 7.10 Ifthe

relation

Q(X) - -w as x -+ co dk)

(20)

holds for every integer a relatively prime to k, then %W N %(4 asx+oo whenever (a, k) = (b, k) = 1. Conversely, (21) implies (20).

(21)

PROOF.It is clear that (20) implies (21). To prove the converse we assume (21) and let A(k) denote the number of primes that divide k. If x > k we have n(x) = 1 1 = A(k) + c 1 P5.X P2.X PXk = A(k) +

i a=1 (a,k)=l

Therefore

1 pza

1 = A(k) +

5

q(x).

a=1 (a, k) = 1

p5.X (modk)

44 -A(k) %(X) (a,k)=l

By (21) each term in the sum tends to 1 as x -+ cc so the sum tends to q(k). Hence 44 44 -q(k) __-asx-rco. %(X) %(4 But A(k)/q,(x) --f 0 so 71(x)/q,(x) + q(k), which proves (20). 0

Exercises for Chapter 7 In Exercises 1 through 4, h and k are given positive integers, (h, k) = 1, and A(h, k) is the arithmetic progression A(h, k) = {h + kx:x = 0, 1, 2, . . .}. Exercises 1 through 4 are to be solved without using Dirichlet’s theorem. 1. Prove that, for every integer n 2 1, A@, k) contains infinitely prime to n. 2. Prove that A@, k) contains i#j.

an infinite

many numbers

relatively

subset {a,, a2,. . .} such that (ai, aj) = 1 if

3. Prove that A&, k) contains an infinite subset which forms a geometric progression (a set of numbers of the form ar”, n = 0, 1, 2, .). This implies that A@, k) contains infinitely many numbers having the same prime factors.

155

7: Dirichlet’s

theorem

on primes in arithmetic

progressions

4. Let S be any infinite subset of A(h, k). Prove that for every positive integer n there is a number in A(h, k) which can be expressed as a product of more than n different elements of S. 5. Dirichlet’s theorem implies the following statement: If h and k > 0 are any two integers with (h, k) = 1, then there exists at least one prime number of the form kn + h. Prove that this statement also implies Dirichlet’s theorem. 6. If (h, k) = 1, k > 0, prove that there is a constant that, if x 2 2,

A (depending

7. Construct an infinite set S of primes with the following property: then ($p - I), $(q - 1)) = (p, q - l)‘= (p - 1, q) = 1.

on h and on k) such

If p E S and q E S

8. Letfbe an integer-coefficient polynomial ofdegree n 2 1 with the following property: For each prime p there exists a prime q and an integer m such that f(p) = q”. Prove that q = p, m = n and f(x) = x” for all x. [Hint: If q # p then q”‘+’ divides f(p+tq”+‘)-f(p)foreacht= 1,2,...]

156

Periodic Arithmetical Functions and Gauss Sums

8

8.1 Functions periodic modulo k Let k be a positive integer. An arithmetical functionf with period k (or periodic modulo k) if

is said to be periodic

f(n -I- 4 = f(n) for all integers n. If k is a period so is mk for any integer m > 0. The smallest positive period off is called the fundamental period. Periodic functions have already been encountered in the earlier chapters. For example, the Dirichlet characters mod k are periodic mod k. A simpler example is the greatest common divisor (n, k) regarded as a function of n. Periodicity enters through the relation (n + k, k) = (n, k).

Another example is the exponential function f(n) = e2nimW where m and k are fixed integers. The number eZnimikis a kth root of unity andf(n) is its nth power. Any finite linear combination of such functions, say

is also periodic mod k for every choice of coefficients c(m). Our first goal is to show that every arithmetical function which is periodic mod k can be expressed as a linear combination of this type. These sums are called$nite Fourier series. We begin the discussion with a simple but important example known as the geometric sum. 157

8 : Periodic arithmetical functions and Gauss sums

Theorem 8.1 For jxed

k 2 1 let g(n)

k-l c

=

,+imnlk.

m=O

0 k

s(n) =

PROOF.

ifk,+‘n, if kin.

Since g(n) is the sum of terms in a geometric

progression,

k-l s(n)

=

1 m=O

xm,

where x = ezninik,we have

I

Xk - 1 ifx # 1, g(n) = . x - 1 k ifx = 1. But xk = 1, and x = 1 if and only if kin, so the theorem is proved.

0

8.2 Existence of finite Fourier series for periodic arithmetical functions We shall use Lagrange’s polynomial interpolation formula to show that every periodic arithmetical function has a finite Fourier expansion. Theorem 8.2 Lagrange’s interpolation theorem. Let zo, zl, . . , zk- 1 be k distinct complex numbers, and let wo, wl, . . . , wk- 1 be k complex numbers which need not be distinct. Then there is a unique polynomial P(z) of degree I k - 1 such that fY%l) = wnl for m = 0, 1,2, . . . , k - 1.

The required polynomial P(z), called the Lagrange interpolation polynomial, can be constructed explicitly as follows. Let

PROOF.

A(z) = (z - zo)(z - zl) . . . (z - Zk- 1) and let

A,(z) = ~44 z-zz,’ Then A,(z) is a polynomial of degree k - 1 with the following properties: &(z,) 158

Z 0,

A,(Zj) = 0

ifj # m.

8.2: Existence

of finite Fourier seriesfor periodic arithmetical functions

Hence A,(z)/A,(z,) is a polynomial of degree k - 1 which vanishes at each Zj for j # m, and has the value 1 at z,. Therefore the linear combination

is a polynomial of degree I k - 1 with P(zj) = wj for each j. If there were another such polynomial, say Q(z), the difference P(z) - Q(z) would vanish at k distinct points, hence P(z) = Q(z) since both polynomials have degree
w, = ~~oa~e2”i”“‘k

(1)

for m = 0, 1, 2, . . . , k - 1. Moreover, formula

the coejficients

a, are given by the

1 k-l

(2)

a, = - c w,e-2”i”“‘k

for

k m=o

n = 0, 1, 2,. . . , k - 1.

Let z, = e2nim’k.The numbers zo, zi, . . . , zk- r are distinct so there is a unique Lagrange polynomial

PROOF.

k-l

P(z) = C a,z” n=O

such that P(z,) = w, for each m = 0, 1,2, . . . , k - 1. This shows that there are uniquely determined numbers a, satisfying (1). To deduce the formula (2) for a, we multiply both sides of (1) by e-2nimr’k,where m and r are nonnegative integers less than k, and sum on m to get k-l C

k-l W,e-2~iWk

=

k-l

gl&Pi(n-‘Y

m=O

ByTheorem&l,thesumonmisOunlesskl(n-r).ButIn-r[


k 1(n - r) if, and only if, n = r. Therefore the only nonvanishing term on the right occurs when n = r and we find k-l c

w,emZnimrlk

=

ka,.

m=O

This equation gives us (2).

cl 159

8 : Periodic

arithmetical

functions

and Gauss sums

Theorem 8.4 Let f be an arithmetical function there is a uniquely determined arithmetical such that

which is periodic mod k. Then function g, also periodic mod k,

k-l

f(m)

= ~Og(n)eZnim”‘k.

In fact, g is given by the formula

g(n) = i 'Elf (m)e-2"im"lk. m0 PROOF. Let w, = f(m) for m = 0, 1,2, . . . , k - 1 and apply Theorem 8.3 to determine the numbers ao, al,. . . , ak- 1. Define the function g by the relations g(m) = a, for m = 0, 1,2, . . . , k - 1 and extend the definition of g(m) to all integers m by periodicity mod k. Then f is related to g by the equations in the theorem. 0

Note. Since both f and g are periodic mod k we can rewrite the sums in Theorem 8.4 as follows : f(m)

=

1

g(n)eznimnjk

nmodk

and g(n) = i

1

f(m)e-2"im"'k.

mmodk

In each case the summation can be extended over any complete residue system modulo k. The sum in (3) is called thejnite Fourier expansion off and the numbers g(n) defined by (4) are called the Fourier coe#icients off:

8.3 Ramanujan’s sum and generalizations In Exercise 2.14(b) it is shown that the Mabius function p(k) is the sum of the primitive kth roots of unity. In this section we generalize this result. Specifically, let n be a fixed positive integer and consider the sum of the nth powers of the primitive kth roots of unity. This sum is known as Ramanujan’s sum and is denoted by c,‘(n): ck(n) =

1

elnimnlk.

mmodk (m,k)=l

We have already noted that this sum reduces to the MCbius function when n = 1, Ak)

160

=

ck(l),

8.3: Ramanujan’s sum and generalizations

When k 1n the sum reduces to the Euler cpfunction since each term is 1 and the number of terms is q(k). Ramanujan showed that c,Jn) is always an integer and that it has interesting multiplicative properties. He deduced these facts from the relation Q(n) =

c dp f . dlh 4 0 This formula shows why c&) reduces to both p(k) and q(k). In fact, when n = 1 there is only one term in the sum and we obtain c&l) = ,a(k). And when kin we have (n, k) = k and ck(n) = xdlk d,a(k/d) = q(k). We shall deduce (5) as a special case of a more general result (Theorem 8.5). Formula (5) for c&r) suggests that we study general sums of the form (5)

(6)

,,;,)f’d’g

0ii . These resemble the sums for the Dirichlet convolutionf * g except that we sum over a subset of the divisors of k, namely those d which also divide n. Denote the sum in (6) by Sk(n).Since n occurs only in the gcd (n, k) we have s,& + k) =

Sk(n)

so Sk(n)is a periodic function of n with period k. Hence this sum has a finite Fourier expansion. The next theorem tells us that its Fourier coefficients are given by a sum of the same type. Theorem 8.5 Let Sk(n) = CdlCn,kj f(d)g(k/d). expansion

Sk(n)=

Then Sk(n) has the finite Fourier

1 ak(m)e2ffim”‘k mmodk

where ak(m)

=

f

d,c~k,gW m,

;.

0

PROOF. By Theorem 8.4 the coefficients ak(m) are given by

ak(m)= k c sk(n)e-2ninm’k nmodk

= k “tl

F /(d)g(i)e-‘“‘““‘*. d,;

Now we write n = cd and note that for each fixed d the index c runs from 1 to k/d and we obtain ak(m) = ; d; f(d)g

f 0

k$ e-2nicdm/k. c

1

161

8 : Periodic arithmetical functions and Gausssums

Now we replace d by kfd in the sum on the right to get (d) i e-2nicm’d. C=l

But by Theorem 8.1 the sum on c is 0 unless d j m in which case the sum has the value d. Hence

which proves (8). Now we specializef and g to obtain the formula for R.amanujan’s sum mentioned earlier. Theorem 8.6 We have

PROOF.

Taking f(k) = k and g(k) = p(k) in Theorem 8.5 we find c dp(;‘) = dlh k) /

1

ak(m)e2”im”‘k

mmodk

where ak(m) =

1 if (m, k) == 1, if(m,k)> 1.

1 p(d) =: [A]={0 dlh k)

Hence d,pkdp(!j) “3

== ,zdk

e2nimnlk = ck(n).

(m,k)=l

8.4 Multiplicative sums S&Z)

properties of the

Theorem 8.7 Let Sk(n)

=

1

f(&

dlh k)

where f and g are multiplicative. (9) 162

s,,&b)

= s,(&,(b)

Then we have whenever (a, k) = (b, m) = 1.

Cl

8.4: Multiplicative properties of the sumss&z)

In particular,

we have s,(ab) = s,(a)

(10)

if(b, m) = 1,

and if (a, k) = 1.

s&a) = s,(a)g(k)

(11)

PROOF.The relations (a, k) = (b, m) = 1 imply (see Exercise 1.24) W, 4

= (a, m)(k b)

with (a, m) and (b, k) relatively prime. Therefore

Writing d = d,d, in the last sum we obtain

%&b)= dll(o,m) 1 d#‘,k) c f(dAg This proves (9). Taking k = 1 in (9) we get s,(ab) = s,(a)sI(b)

since s,(b) = f(l)g(l)

= s,,,(a)

= 1. This proves (10). Taking b = 1 in (9) we find %kta)

=

sm(a)sk(l)

=

G&W

since sk(1) = f( l)g(k) = g(k). This proves (11).

0

EXAMPLE For Ramanujan’s sum we obtain the following

multiplicative

properties : whenever (a, k) = (b, m) = 1, whenever (b, m) = 1,

Cm,@‘) = d&,(b) c&b) = c,(a) and &k(a)

=

whenever (a, k) = 1.

c,&Mk)

Sometimes the sums Sk(n) can be evaluated in terms of the Dirichlet convolutionf * g. In this connection we have: Theorem 8.8 Let f be completely multiplicative, h is multiplicative. and let

Assume that

Sk(n)

=

f

and let g(k) = p(k)h(k), where (p) # 0 and f (p) # h(p) for all primes p,

1 f (dig dlh k)

. 163

8 : Periodic

arithmetical

functions

and Gauss sums

Then we have s

(n)

=

Wg(N)

k J’(N)

’

where F = f * g and N = k/(n, k).

PROOF.First we note that

F(k) = c f(d)p k h k - c f k 44W = f(k); dlk

cd)

cd)

= /(k);(l

-

- $j

>

d,k

a(d)#

cd)

.

Next, we write a = (n, k), so that k = aN. Then we have Sk@)

=

1 dlo

f@)~

2 (“>

h

-j (“1

=

f (& 7

c dla

(““>

h -d(““1

Now p(Nd) = p(N)p(d) if (N, d) - 1, and p(Nd) = 0 if (N, d) > 1, so the last equation gives us sk(n)

=

&WN)

f

c

db

z

N)h(d)

f(a)p(N)h(N)

=

0

(N,d)=

‘i p(d) E 40 (N,d)=l

1

= f(4NW4N)~ PXN

F(k) f(N) WMWW) =~GMWW)~OF(~~ = F(N)

FW&V =F(Ni.

EXAMPLE For Ramanujan’s sum we obtain the following simplification:

ck(n)

164

=

cp(k)p(Nh(N)

=

0

8.5 : Gauss sums associated

with Dirichlet

characters

8.5 Gauss sums associated with Dirichlet characters Definition For any Dirichlet character x mod k the sum G(n, x) = i &t)e2nimn’k m=l

is called the Gauss sum associated with x. If x = x1, the principal character mod k, we have x1(m) = 1 if (m, k) = 1, and x1(m) = 0 otherwise. In this case the Gauss sum reduces to Ramanujan’s sum : G(n, xl) =

i

e2nimn/k=

ck(n).

m=l (m,k)=l

Thus, the Gauss sums G(n, x) can be regarded as generalizations of Ramanujan’s sum. We turn now to a detailed study of their properties. The first result is a factorization property which plays an important role in the subsequent development. Theorem 8.9 If x is any Dirichlet

character mod k then

G(n, x) = z(n)G(l, x)

whenever (n, k) = 1.

PROOF. When (n, k) = 1 the numbers nr run through a complete residue system mod k with r. Also, 1x(n) 1’ = x(n)f(n) = 1 so

x(r) = i3nMnM) = dnkh). Therefore the sum defining G(n, x) can be written as follows: G(n, x) =

c

X(r)e2ninr’k = j(n)

rmodk

c

X(nr)e2ninr’k

rmodk

= r?(n)1 xbk 2nim’k= j(n)G(l, x). mmodk

q

This proves the theorem. Definition The Gauss sum G(n, x) is said to be separable if (12)

Gh xl = XWW, xl.

Theorem 8.9 tells us that G(n, x) is separable whenever n is relatively prime to the modulus k. For those integers n not relatively prime to k we have the following theorem. 165

8 : Periodic

arithmetical

functions

and Gauss sums

Theorem 8.10 If x is a character mod k the Gauss sum G(n., x) is separable for every n if and only if, G(n, x) == 0

whenever (n, k) > 1.

PROOF. Separability always holds if (n, k) = 1. But if (n, k) > 1 we have j(n) = 0 so Equation (12) holds if and only if G(n, x) = 0. cl

The next theorem gives an important consequence of separability. Theorem 8.11 Zf G(n, x) is separablefor (13) PROOF.

every n then

IGU, x)l2 = k.

We have --

IG(1, x)12 = G(l, x)G(l, x) = G(l, x) 1 j(m)e-2”im~k m=l

= mclG(m, X)e-2nim/k = mil .il X(r)e2nin1rlke-2nimlk

= ilx(4

i: e2nim(r-l)/k = Q(l)

= k,

In=1

since the last sum over m is a geometric sum which vanishes unless r

=

1.

8.6 Dirichlet characters with nonvanishing Gauss sums For every character x mod k we have seenthat G(n, x) is separable if (n, k) = 1, and that separability of G(n, x) is equivalent to the vanishing of G(n, x) for (n, k) > 1. Now we describe further properties of those characters such that G(n, x) = 0 whenever (n, k) > 1. Actually, it is simpler to lstudy the complementary set. The next theorem gives a necessary condition for G(n, 1) to be nonzero for (n, k) > 1. Theorem 8.12 Let x be a Dirichlet character mod k and assume that G(n, x) # 0 for some n satisfying (n, k) > 1. Then there exists a dicisor d of k, d < k, such that

(14)

x(a) = 1 wheneuer (a, k) = 1 and a z 1 (mod d).

For the given n, let 4 = (n, k) and let d = k/q. Then d I k and, since q > 1, we have d < k. Choose any a satisfying (a, k) = 1 and a = 1 (mod d). We will prove that x(a) = 1. PROOF.

166

8.7: Induced moduli and primitive characters

Since (a, k) = 1, in the sum defining G(n, x) we can replace the index of summation m by am and we find G(n, x) =

c

X(m)e2ninm’k =

mmodk

= x(a) 1

X(m)e2ninam’k.

mmodk

Since a = 1 (mod d) and d = k/q we can write a = 1 + (bk/q) for some integer b, and we have anm -=-+k

nm k

bknm = t qk

+ brim E t 4

(mod 1)

since q 1n. Hence e2ninrrm’k = e2ninm’kand the sum for G(n, x) becomes

Gh xl = x~~)m~dkx.(mk2ri”m/*= x(Wh

xl.

Since G(n, x) # 0 this implies x(a) = 1, as asserted.

Cl

The foregoing theorem leads us to consider those characters x mod k for which there is a divisor d < k satisfying (14). These are treated next.

8.7 Induced

moduli

and primitive

characters

of induced modulus Let x be a Dirichlet character mod k and let d be any positive divisor of k. The number d is called an induced modulus for x if we have

Definition

(15)

x(a) = 1 whenever (a, k) = 1 and a = 1 (mod d).

In other words, d is an induced modulus if the character x mod k acts like a character mod d on the representatives of the residue class f mod d which are relatively prime to k. Note that k itself is always an induced modulus for x. Theorem 8.13 Let x be a Dirichlet character modulus for x $ and only if, x = x1.

mod k. Then 1 is an induced

If x = x1 then x(a) = 1 for all a relatively prime to k. But since every a satisfies a = 1 (mod 1) the number 1 is an induced modulus. Conversely, if 1 is an induced modulus, then x(a) = 1 whenever (a, k) = 1, so x = x1 since x vanishes on the numbers not prime to k. 0

PROOF.

167

8 : Periodic arithmetical functions and Gausssums For any Dirichlet character mod k the modulus k itself is an induced modulus. If there are no others we call the character ,~imitiue. That is, we have: of primitive characters A Dirichlet character x mod k is said to be primitive mod k if it has no induced modulus d < k. In other words, x is primitive mod k if, and only if, for every divisor d of k, 0 < d < k, there exists an integer a = 1 (mod d), (a, k) = 1, such that x(a) # 1.

Definition

If k > 1 the principal character x1 is not primitive since it has 1 as an induced modulus. Next we show that if the modulus is prime every nonprincipal character is primitive. Theorem 8.14 Every nonprincipal character mod p.

character

x modulo a prime p is a primitive

PROOF. The only divisors of p are 1 and p so these are the only candidates for induced moduli. But if x # x1 the divisor 1 is not an induced modulus so x has no induced modulus
Now we can restate the results of Theorems 8.10 through 8.12 in the terminology of primitive characters. Theorem 8.15 Let 1 be a primitive

Dirichlet

character mod k. Then we have:

(a) G(n, x) = Ofor every n with (n, k) > 1. (b) G(n, x) is separable for every n. (4 IGU, x)l’ = k.

If G(n, x) # 0 for some n with (n, k) > 1 then Theorem 8.12 shows that x has an induced modulus d < k, so x cannot be primitive. This proves (a). Part (b) follows from (a) and Theorem 8.10. Part (c) follows from part (b) and Theorem 8.11. q PROOF.

Note. Theorem 8.15(b) shows that the Gauss sum G(n, x) is separable if x is primitive. In a later section we prove the converse. That is, if G(n, 1) is separable for every n then 2 is primitive. (SeeTheorem 8.19.)

8.8 Further

properties

of induced moduli

The next theorem refers to the action of x on numbers which are congruent modulo an induced modulus. Theorem 8.16 Let x be a Dirichlet character mod k and assume d 1k, d > 0. Then d is an induced modulus for x if, and only if,

(16) 168

x(a) = X(b)

whenever (a, k) = (b, k) = 1 and a z b (mod d).

8.8 : Further

properties

of induced

moduli

PROOF. If (16) holds then d is an induced modulus since we may choose b = 1

and refer to Equation (15). Now we prove the converse. Choose a and b so that (a, k) = (b, k) = 1 and a = b (mod d). We will show that x(a) = X(b). Let a’ be the reciprocal of u mod k, au’ - 1 (mod k). The reciprocal exists because (a, k) = 1. Now au’ - 1 (mod d) since d I k. Hence ~(uu’) = 1 since d is an induced modulus. But au’ = bu’ 3 1 (mod d) because a = b (mod d), hence x(au’) = X(bu’), so

But ~(a’) # 0 since x(u)x(u’) = 1. Canceling ~(a’) we find x(u) = X(b), and this completes the proof. 0 Equation (16) tells us that x is periodic mod d on those integers relatively prime to k. Thus x acts very much like a character mod d. To further explore this relation it is worthwhile to consider a few examples. EXAMPLE 1 The following table describes one of the characters x mod 9. n

1

x(n)

1

2 -1

3

4

5

0

1

-1

6

7

0

1

8 -1

9 0

We note that this table is periodic modulo 3 so 3 is an induced modulus for x. In fact, x acts like the following character + modulo 3 : n

1

2

3

$(n)

1

- 1

0

Since x(n) = I&) for all n we call x an extension of t+Q. It is clear that whenever x is an extension of a character $ modulo d then d will be an induced modulus for x. EXAMPLE 2 Now we examine one of the characters x modulo 6: n

1

2

3

4

5

6

x(n)

1

0

0

0

- 1

0

In this case the number 3 is an induced modulus because x(n) = 1 for all n = 1 (mod 3) with (n, 6) = 1. (There is only one such n, namely, n = 1.) 169

8 : Periodic arithmetical functions and Gauss sums

However, x is not an extension of any character II/ modulo 3, because the only characters modulo 3 are the principal character +i, ,given by the table: n

1

2

3

and the character $ shown in Example 1. Since x(2) = 0 it cannot be an extension of either + or $,. These examples shed some light on the next theorem. Theorem 8.17 Let x be a Dirichlet Then the following

character modulo k and assume d 1k, d > 0. two statements are equivalent:

(a) d is an induced modulus for x. (b) There is a character II/ modulo d such that (17) where x1 is the principal

x(n) = rl/(nh(n)

for all 4

character modulo k.

PROOF. Assume (b) holds. Choose n satisfying (n, k) = 1, n = 1 (mod d). Then x1(n) = IC/(n) = I so x(n) = 1 and hence d is an induced modulus. Thus, (b) implies (a). Now assume (a) holds. We will exhibit a character I++modulo d for which (17) holds. We define $(n) as follows: If (n, d) > 1, let I&) = 0. In this case we also have (n, k) > 1 so (17) holds because both members are zero. Now suppose (n, d) = 1. Then there exists an integer m such that m E n (mod d), (m, k) = 1. This can be proved immediately with Dirichlet’s theorem. The arithmetic progression xd + n contains infinitely many primes. We choose one that does not divide k and call this m. However, the result is not that deep; the existence of such an m can easily be e;stablished without using Dirichlet’s theorem. (See Exercise 8.4 for an alternate proof.) Having chosen m, which is unique modulo d, we define

ti(n) = x(m). The number e(n) is well-defined because x takes equal values at numbers which are congruent modulo d and relatively prime to k. The reader can easily verify that x is, indeed, a character mod d. We shall verify that Equation (17) holds for all n. If (n, k) = 1 then (n, d) = 1 so $(n) = x(m) for some m E n (mod d). Hence, by Theorem 8.16, x(n) = x(m) = IL(n) = Wkl(n) since x1(n) = 1. If (n, k) > 1, then x(n) = xl(n) = 0 and both members of (17) are 0. Thus, 0 (17) holds for all n. 170

8.10: Primitive charactersand separableGausssums

8.9 The conductor

of a character

Let x be a Dirichlet character mod k. The smallest induced modulus d for x is called the conductor of x.

Definition

Theorem8.18

Every Dirichlet

(18)

character x mod k can be expressed as a product,

x(n) = Il/(nkl(n)

where x1 is the principal character modulo the conductor of 1+9.

for all n,

mod k and $ is a primitive

character

PROOF.Let d be the conductor of x. From Theorem 8.17 we know that x can be expressed as a product of the form (18), where II/ is a character mod d. Now we shall prove that $ is primitive mod d. We assume that $ is not primitive mod d and arrive at a contradiction. If I,+is not primitive mod d there is a divisor q of d, q < d, which is an induced modulus for $. We shall prove that this q, which divides k, is also an induced modulus for x, contradicting the fact that d is the smallest induced modulus for x. Choose n = 1 (mod q), (n, k) = 1. Then x(4 = vWxl(n) = 964 = 1 because q is an induced modulus for II/. Hence q is also an induced modulus for x and this is a contradiction. 0

8.10 Primitive characters Gauss sums

and separable

As an application of the foregoing theorems we give the following alternate description of primitive characters. Theorem 8.19 Let x be a character only if, the Gauss sum G(n, x) =

mod k. Then x is primitive

1

mod k if, and

X(m)e2zimn’k

mmodk

is separable for every n.

PROOF.If x is primitive, then G(n, x) is separable by Theorem 8.15(b). Now we prove the converse. Because of Theorems 8.9 and 8.10 it suffices to prove that if x is not primitive mod k then for some r satisfying (r, k) > 1 we have G(r, x) # 0. Suppose, then, that x is not primitive mod k. This implies k > 1. Then x has a conductor d < k. Let r = k/d. Then (r, k) > 1 and we shall prove that 171

8 : Periodic

arithmetical

functions

and Gauss sums

G(r, x) # 0 for this r. By Theorem 8.18 there exists a primitive character $ mod d such that x(n) = r/+)x1(n) for all n. Hence we can write G(r, x) =

1

t)(m)Xl(m)e2xirm’k= m,C, kWWnirmik

mmodk (m,k)=

=

mzdk

be+

(m,k)=

2nimld

=

g

1

1

mzdd

(m,d)=

$,(m)e2sWd,

1

where in the last step we used Theorem 5.33(a). Therefore we have G(r, x) = g

G( 1, II/).

But 1G(l, $)I2 = d by Theorem 8.15 (since $ is primitive mod d) and hence G(r, x) # 0. This completes the proof. q

8.11 The finite Fourier characters

series of the Dirichlet

Since each Dirichlet character x mod k is periodic mod k it has a finite Fourier expansion k

(19)

x(m) = 1 ak(n)e2nimn’k,

and Theorem 8.4 tells us that its coefficients are given by the formula uk(n) = t i X(m)e-2”im”ik. m-l The sum on the right is a Gauss sum G( - n, x) so we have (20)

a,‘(n) = ; G( -n, X).

When x is primitive the Fourier expansion (19) can be expressed as follows : Theorem 8.20 The finite Fourier expansion of a primitive x mod k has the form (21)

x(m) = !$$

i ji(n)e-2”imdk n 1

where (2-a

Zk(X) = TG(17x) = 5

The numbers tk(x) have absolute value 1.

172

~~I~(m)e2”im~k.

Dirichlet

character

8.12: Pdya’s

inequality

for the partial

sums of primitive

characters

PROOF. Since x is primitive we have G( --n, x) = j( -n)G(l, x) and (20) implies L&I) = j( - n)G(l, x)/k. Therefore (19) can be written as

which is the same as (21). Theorem 8.11 shows that the numbers zk(x) have absolute value 1. 0

8.12 Pblya’s inequality for the partial sums of primitive characters The proof of Dirichlet’s theorem given in Chapter 7 made use of the relation I

m;~(m)

I

I dk)

which holds for any Dirichlet character x mod k and every real x 2 1. This cannot be improved when x = x1 because cm=, x1(m) = q(k). However, Polya showed that the inequality can be considerably improved when x is a primitive character. Theorem 8.21 Polya’s inequality. If x is any primitive for all x 2 1 we have

character

mod k then

(23) PROOF.

We express x(m) by its finite Fourier expansion, as given in Theorem

8.20

x(m) = ?$$! $ x(n)e-2nimnlk, ”

1

and sum over all m I x to get

since X(k) = 0. Taking absolute values and multiplying by & we find

say, where

173

8 : Periodic

arithmetical

functions

and Gauss sums

Now f(k

_

n)

=

2

e-

2nim(k-N/k

=

1

m<x

e2nimn/k

=

f(n)

msx

so

(f(k - n) 1= 1f(n) I. Hence (24) can be written as (25)

Nowf(n)

is a geometric sum of the form f(n) = i

Y”

m=l

where r = [x] and y = e- 2nin’k. Here y # 1 since 1 I n < k - 1. Writing z = e-xinlk, we have y = z2 and ,z2 # 1 since n I k/2. Hence we have

NOW we use the inequality m/k to get

sin t 2 2t/x, valid for Cl 5 t < 7~12, with t =

-Irk

Hence (25) becomes I k c &k/2

and this proves (23).

1-c k log k, n 0

Note. In a later chapter we will prove that Polya’s inequality can be extended to any nonprincipal character. For nonprimitive characters it takes the form

(See Theorem 13.15.) 174

Exercises for Chapter

8

Exercises for Chapter 8 1. Let x = ezniin and prove that

2. Let ((x)) = x - [x] - $ if x is not an integer, and let ((x)) = 0 otherwise. Note that ((x)) is a periodic function of x with period 1. If k and n are integers, with n > 0, prove that k (0) n

=--

3. Let ck(m) denote Ramanujan’s Mobius function.

in $rrcot

y

sin T

.

sum and let M(x) = cnSX p(n), the partial

sums of the

(a) Prove that k$lckh,

In particular,

=

1 dM(;). dim

=

dF

when n = m, we have k~,ckb,

dM(;). n

(b) Use (a) to deduce that M(m)

= m 1 y dim

i

c,(d).

k=l

(c) Prove that m$lck(m)

=

c

&(;)[j.

dlk

4. Let n, a, d be given integers with (a, d) = 1. Let m = a + qd where q is the product (possibly empty) of all primes which divide n but not a. Prove that m E a (mod d) 5. Prove that there exists no real primitive

and(m,n)

character x mod k if k = 2m, where m is odd.

6. Let 1 be a character mod k. If kl and k2 are induced (k,, k2), their gtd. 7. Prove that the conductor

= 1.

of 1 divides every induced

moduli modulus

for x prove that so too is for x.

In Exercises 8 through 12, assume that k = k,kz ... k,, where the positive integers ki are relatively prime in pairs: (ki, kj) = 1 if i # j. 8. (a) Given any integer a, prove that there is an integer ai such that ai = a (mod ki)

and ai = 1 (mod kj)

for all j # i.

175

8 : Periodic

arithmetical

functions

(b) Let x be a character

and Gauss sums

mod k. Define xi by the equation =

Idal

x(4X

where ai is the integer of part (a). Prove that xi is a character

mod ki.

9. Prove that every character x mod k can be factored uniquely form x = x1 x2 . . x,, where xi is a character mod ki. 10. Let f(x) denote the conductor that f(x) = f(xJ

of x. If x has the factorization

as a product

of the

in Exercise 9, prove

. fW

11. If 2 has the factorization

in Exercise 9, prove that for every integer a we have

G(aa X)= iolXi(3k G(aia Xi), where ai is the integer of Exercise 8. 12. If x has the factorization in Exercise 9, prove that x is primitive each xi is primitive mod ki. [Hint: Theorem 8.19.1 13. Let x be a primitive

character

mod k if, and only if,

mod k. Prove that if N < M we have

I.;+,$1

< A1

Jit

log k.

14. This exercise outlines a slight improvement in Polya’s inequality. of Theorem 8.21. After inequality (26) write

Show that the integral

is less than -(k/n)log(sin(~/2k))

Refer to the proof

and deduce that

In&x:Ix(n) I <4 +i 4 1%k. This improves 15. The Kloosterman

Polya’s

inequality

by a factor 2/x in the principal

term.

sum K(m, n; k) is defined as follows: qm,

n; k) =

1

$Wmh+nh’)lk

hmodk (h,k)=l

where h’ is the reciprocal of h mod k. When k 1n this reduces to Ramanujan’s sum ck(m). Derive the following properties of Kloosterman sums: (a) K(m, n; k) = K(n, m; k). (b) K(m, n; k) = K(1, mn; k) whenever (m, k) = 1. (c) Given integers n, k,, k2 such that (k,, k,) = 1, show that there exist integers n, and n2 such that n = nlkz2 + n2k12 (mod k,k,), and that for these integers we have Kh 176

n; klk2)

= Kh

nl; kMm,

nz; k2).

Exercises for Chapter

This reduces the study of Kloosterman p is prime.

8

sums to the special case K(m, n; p”), where

16. If n and k are integers, n > 0, the sum G(k ; n) = i e2niWn r=1 is called a quadratic Gauss sum. Derive the following properties of quadratic Gauss sums : (a) G(k; mn) = G(km; n)G(kn; m) whenever (m, n) = 1. This reduces the study of Gauss sums to the special case G(k; p”), where p is prime. (b) Let p be an odd prime, p ,j’ k, tl 2 2. Prove that G(k; p”) = pG(k; pa-‘) and deduce that

ai2 G(k;p”)

=

’ 1 p@- ‘)“G(k;

if t( is even, p)

if tl is odd.

Further properties of the Gauss sum G(k; p) are developed in the next chapter where it is shown that G(k; p) is the same as the Gauss sum G(k, x) associated with a certain Dirichlet character x mod p. (See Exercise 9.9.)

177

9

Quadratic Residues and the Quadratic Reciprocity Law

9.1 Quadratic

residues

As shown in Chapter 5, the problem of solving a polynomial congruence f(x) E 0 (mod m) can be reduced to polynomial congruences with prime moduli plus a set of linear congruences. This chapter is concerned with quadratic congruences of the form x2 z n (mod p)

(1)

where p is an odd prime and n f 0 (mod p). Since the modulus is prime we know that (1) has at most two solutions. Moreover, if x is a solution so is -x, hence the number of solutions is either 0 or 2. If congruence (1) has a solution we say that n is a quadratic residue mod p and we write nRp. If (1) has no solution we say that n is a quadratic nonresidue mod p and we write r&p.

Definition

Two basic problems dominate the theory of quadratic residues: 1. Given a prime p, determine which n are quadratic residues mod p and which are quadratic nonresidues mod p. 2. Given n, determine those primes p for which n is a quadratic residue mod p and those for which n is a quadratic nonresidue mod p. We begin with some methods for solving problem 1. 178

9.2 : Legendre’s symbol and its properties

EXAMPLE To find the quadratic residues modulo 11 we square the numbers

1,2,...,

10 and reduce mod 11. We obtain

12 z 1,

22 s 4,

32 = 9,

42 = 5,

52 G 3 (mod 11).

It suffices to square only the first half of the numbers since 62 ZE(-5)2 z 3,

72 z (-4)2 E 5,...,

lo2 E (- 1)2 E 1 (mod 11).

Consequently, the quadratic residues mod 11 are 1, 3, 4, 5, 9, and the nonresidues are 2,6, 7, 8, 10. This example illustrates the following theorem. Theorem 9.1 Let p be an odd prime. Then every reduced residue system mod p contains exactly (p - 1)/2 quadratic residues and exactly (p - 1)/2 quadratic nonresidues mod p. The quadratic residues belong to the residue classes containing the numbers

p-l 2 12, 22, 32,. . .) ~ ( 2 > . First we note that the numbers in (2) are distinct mod p. In fact, if x2 = y2 (mod p) with 1 < x I (p - 1)/2 and 1 I y 5 (p - 1)/2, then

PROOF.

(x - y)(x + y) 3 0 (mod p). But 1 < x + y < p so x - y c 0 (mod p), hence x = y. Since 0, - k)’ = k2 (mod p),

every quadratic residue is congruent mod p to exactly one of the numbers in (2). This completes the proof. cl The following brief table of quadratic residues R and nonresidues i? was obtained with the help of Theorem 9.1. p=3

p=5

p=l

p= 11

p= 13

R:

1

L4

1,2,4

1, 334, 59

1, 3,4,9, 10, 12

R:

2

2, 3

3, 5, 6

2, 6, 7, 8, 10

2, 5, 6, 7, 8, 11

9.2 Legendre’s symbol and its properties Let p be an odd prime. If n + 0 (mod p) we define Legendre’s symbol (n 1p) as follows : + 1 if nRp, (nip) = i - 1 if r&p.

Definition

If n = 0 (mod p) we define (n 1p) = 0. 179

9: Quadratic residuesand the quadratic reciprocity law

EXAMPLES(~~P)= l,(m’Ip)

= 1,(7)11) = -1,(22[11)

= 0.

Note. Some authors write $ instead of (n Ip). 0 It is clear that (m Ip) = (n Ip) whenever m = n (mod p), so (n Ip) is a periodic function of n with period p. The little Fermat theorem tells us that rip-l GE1 (mod p) if p ,j’ n. Since n p-1

_

1 =

(n(P-w2

_

l)(n’P-“12

+

1)

it follows that nCp- 1)‘2 = + 1 (mod p). The next theorem tells us that we get + 1 if nRp and - 1 if ni?p.Theorem9.2 Euler’s criterion. Let p be an odd prime. Then for all n we have (n Ip) = nCp- 1)‘2 (mod p). PROOF. If n = 0 (mod p) the result is trivial since both members are congruent to 0 mod p. Now suppose that (nip) = 1. Then there is an x such that x2 = n (mod p) and hence a(P-

1)/z

E

(~2)(P-1)/2

=

xP-1

E

1

=

(n

Ip)

(mod

p).

This proves the theorem if (n I p) = 1. Now suppose that (n Ip) = - 1 and consider the polynomial f(x) = ,$-1)/2 - 1. Sincef(x) has degree (p - 1)/2 the congruence f(x) = 0 (mod p) has at most (p - 1)/2 solutions. But the (p - 1)/2 quadratic residues mod p are solutions so the nonresidues are not. Hence nCp-‘)”

f 1 (mod p)

if(nlp) = -1.

But n(P- l)j2 = + 1 (mod p) so nCp- ‘)I2 = - 1 = (n Ip) (mod p). This com0 pletes the proof.Theorem 9.3 Legendre’s symbol (n I p) is a completely multiplicative

function

of n.

PROOF.If plm or pin then plmn so (mnlp) = 0 and either (mlp) = 0 or (nip) = 0. Therefore (mnlp) = (mjp)(nlp) ifplm or pin. Ifp$mandp$nthenp,j’mnandwehave (mn Ip) = (mn)(“- ‘)I2 = rn(P- ‘)i2n(P- ‘)I2 = (m Ip)(n Ip) (mod p).

180

9.3: Evaluation

of (- 1 Jp) and (21~)

But each of (mn 1p), (m 1p) and (n 1p) is 1 or - 1 so the difference

(mnld - (mIP)(nIP) is either 0,2, or - 2. Since this difference is divisible by p it must be 0. Note. Since (n jp) is a completely multiplicative function of n which is periodic with period p and vanishes when p (n, it follows that (n Ip) = x(n), where x is one of the Dirichlet characters modulo p. The Legendre symbol is called the quadratic character mod p.

9.3 Evaluation of (- 1Ip) and (2)~) Theorem

9.4 For every odd prime p we have

(-lIPI

= (-l)(p-1)‘2

=

-1

1 if p = 1 (mod 4), ifp ~ 3 (mod4)

PROOF. By Euler’s criterion we have (- 1 Ip) = (- l)(p- r)12 (mod p). Since

each member of this congruence is 1 or - 1 the two members are equal. 0 Theorem 9.5 For every odd prime p we have (4p)

= (-1)@-1)/8

=

-1

1 f p = f 1 (mod 8), ifp= +3 (mod8).

PROOF. Consider the following 0, - 1)/2 congruences: p - 1 = l( - 1)’

(mod P)

2 E 2(-1)2

(mod P)

p - 3 E 3( - 1)3

(mod P)

4 E 4(-

(mod P)

r E q

1)4

(- l)(P- IV2 (mod p),

where r is either p - (p - 1)/2 or (p - 1)/2. Multiply that each integer on the left is even. We obtain !(- 1)1+2+,..+(~-1)/2

these together and note

(mod

p).

This gives us 2(Pe’V2(!?$)!

G (!!)!(-1)(pzm1)~8

(mod p).

181

9: Quadratic

residues and the quadratic

reciprocity

law

Since (0, - 1)/2)! + 0 (mod p) this implies 2’P- I)/2 = (_ I)@- I)/8 (mod p). By Euler’s criterion we have 2u- ‘)I2 = (21~) (mod p), and since each member is 1 or - 1 the two members are equal. This completes the proof. 0

9.4 Gauss’ lemma Although Euler’s criterion gives a straightforward method for computing (n Ip), the calculation may become prohibitive for large n since it requires raising n to the power (p - 1)/2. Gauss found another criterion which involves a simpler calculation. Theorem 9.6 Gauss’ lemma. Assume n f 0 (mod p) and consider the least positive residues mod p of the following (p - 1)/2 multiples of n: P-l n, 2n, 3n, . . , ~

2

n

If m denotes the number of these residues which exceed p/2, then

(nld = (- 1)“. PROOF.The numbers in (3) are incongruent mod p. We consider their least positive residues and distribute them into two disjoint sets A and B, according as the residues are