Introduction to Number Theory

Proof If x 2 == n

(I)

(modp)

is soluble, then there are at most two solutions. From (p x 2 == n(modp), we see that one of the roots of (1) must satisfy 1 :;;; x :;;; }(p - 1).

X)2

== ( - xf = (2)

That is, if (1) is soluble, there must be a solution satisfying (2). Also 12,2 2, ... ,(}(P - 1))2 are incongruent numbers because a 2 - b 2 = (a - b)(a + b) and neither of these factors, being smaller than p, is a multiple of p. The theorem is proved. 0

36

3. Quadratic Residues

Theorem 1.2 (Euler's Criterion). Let p be an odd prime. Then we have

nt (p-1) Proof I) If (~)

== (;) (modp).

= I, then there exists

x such that x 2

nt (p-1) == XP-1 == I

== n (modp), and so

(modp).

t(P -

2) From Theorem 2.9.1 we know that there are at most 1) solutions to nt(p - 1) == 1 (mod p). Combining with 1) we see that this equation actually has 1) solutions, that is the quadratic residues modp, and no other. 3) We have

t(P -

pl(nP-1 _ I)

= (n t (p-1) - 1)(nt (P-1) + 1).

Therefore, if p,r(n t (P-1) - 1), then nt(p-1)

The theorem is proved.

+ I == 0

(modp).

0

We have, as a consequence of this theorem: Theorem 1.3.

Thus,

(~)

if p,rmn , then

(;)(;)

= (:n).

0

is a mUltiplicative function of n. We also deduce:

Theorem 1.4. (i) The product of two quadratic residues is a quadratic residue. (ii) The product of two quadratic non-residues is a quadratic residue. (iii) The product ofa quadratic residue and a quadratic non-residue is a quadratic non-residue. 0

3.2 The Evaluation of Legendre's Symbol From Theorem 1.3 we see that the evaluation of Legendre's symbol reduces to the evaluation of

where q is an odd prime. For if 2 < q1 < ... < q..

then

37

3.2 The Evaluation of Legendre's Symbol

Taking n = - 1 in Theorem 1.2 we have

(~1) == (_ I)P~l

(modp),

and since both sides of the congruence must be ± 1, we have Theorem 2.1.

If p > 2,

then

C/ ) = ( -

ly!-(p-l).

D

In other words, - 1 is a quadratic residue or non-residue modp, according to whether p == 1 or 3 (mod4). It follows from this that the odd prime divisors of x 2 + 1 must be congruent to 1 (mod 4). Theorem 2.2 (Gauss's Lemma). Let p > 2, p,tn. Denote by m the number of least positive residues of the 1) numbers n, 2n, ... l)n (mod p) which exceed p/2. Then

t(P -

Example 1. p

7,n

=

=

,t(P -

10. We have 10,20, 30 == 3,6,2

(mod 7).

There is exactly one least positive residue which exceeds (If) = - 1.

J. Therefore m = 1 and

Example 2. p = 11, n = 2. We have the residues 2,4,6,8, 10 (mod 11), and there are three which exceed 1f. Therefore (121) = - 1.

t(P -

Proof of Theorem 2.2. Let 1= 1) - m, and let at> ... , a, be those residues which are less than p/2, and bI> ... , bm be those residues which are greater than p/2. Then'

n as n b == n I

m

t(p-l)

l

s=l

1=1

k=l

(p _1)

p-l

kn = - - !n-22

(modp).

(1)

Since 1 ::;:; p - bl ::;:; t(p - 1) it follows that as and p - bl are t(p - 1) integers in the 1). We now prove that they are distinct by proving interval from 1 to as -:f p - bl • Suppose, if possible, as + bl = p. Then there are integers x, y such that

t(P -

xn

or x

+ yn == 0

+ y == 0 (modp),

1::;:; x ::;:;

(modp),

tCP -

1),

which is impossible. Therefore

n as n (P I

m

s=l/=l

bl )

1::;:; y ::;:;

(p _1) !.

= -

2

t(P - 1)

38

3. Quadratic Residues

From (1) we see that the left hand side of this equation is

== (- l)m

rl Ii as

s=1

ht

== (- l) mnt(p-l)(p 2

t=1

I)!

(modp).

Therefore nt(p-l)

== (- l)m (modp).

From Euler's criterion we see that (;) == ( - l)m (modp), and so (;)

= (-

l)m. 0

If we take n = 2 in Theorem 2.2, then

2,2'2, 2·3, ... ,t(p -1)·2 are already in the interval from 0 to p. We can now determine the number of integers k satisfying i < 2k < p, or ~ < k < i, which gives

m= Let p = 8a

+ r, r =

[~J -[~l

1,3,5,7. Then

m = 2a

+

GJ -[~J

== 0, 1, 1,0 (mod 2).

Therefore we have: Theorem 2.3.

If p > 2,

then (;)

= (-

l)i(pL 1).

0

In other words 2 is a quadratic residue or nO!l-residue modp, according to whether p == ± 1 or ± 3 (mod 8). It follows from this that every odd prime divisor of x 2 - 2 must be congruent to ± 1 (mod 8). Exercise. Let n be a positive integer such that 4n + 3 and 8n + 7 are primes. Prove that 24n + 3 - 1 = M 4n + 3 is composite. Use this to prove the following concerning Mersenne numbers:

231M ll ,

471M23 ,

1671Ms3 ,

263IM 131 ,

3591M 179 ,

3831M 19b

4791M239 ,

5031M251 •

3.3 The Law of Quadratic Reciprocity Theorem 3.1. Let p, q he two distinct odd primes. Then

(~) (~) = (_

l)t(p-1)t(q-1).

39

3.3 The Law of Quadratic Reciprocity

x2

In other words, if p == q == 3 (mod 4), then exactly one of the two congruences == p (mod q), x 2 == q (modp) is soluble. Otherwise the two congruences are either

both soluble or both insoluble. This is the famous and important Law of Quadratic Reciprocity in elementary number theory which was discovered by Legendre and proved by Gauss, who named it "the queen of number theory". The later research work on algebraic number theory by Kummer, Eisenstein, Hilbert, Takagi, Artin, Furtwangler seem to justify the name. Proof We do not, for the moment, exclude the case q = 2, and we suppose that p, q are distinct primes. When 1 ~ k ~ t(P - 1) we can write

Let m

I

a=

a.,

I

b=

bt

t= I

s= I

where as and bt are defined in the previous section. Then we have tIp-I)

I

+ b.

rk = a

(1)

k=I

We saw in the proof of G.auss's lemma that a., p - bt are the same as 1,2, ... ,t(P - 1). Therefore

p2 _ 1

1

-8-=1+2+ ... +"2(p-l)=a+mp -b,

(2)

and

p2 _ 1 - -q

tIp-I)

=

I

tIp-I)

kq

=p

I

g k=I k=I Subtracting (2) from (3), we have p2 _ 1 -g-(q - 1)

tIp-I)

qk

I

+

tIp-I)

rk

=P

k=I

I

qk

+ a + b.

(3)

k=I

!(p-I)

I

=p

qk - mp

+ 2b,

k=I

or

p2_1

tIp-I)

(4) I qk - m (mod 2). k=I 1) (Alternative proof of Theorem 2.3). We take q = 2 so that qk are all 0, and hence -8-(q - 1)

==

p2 _ 1

- - == - m (mod 2). 8

2) Let q > 2. Then tIp-I)

m ==

I

k=I

qk

(mod 2).

40

3. Quadratic Residues

Therefore

Similarly we have

so that

If we can prove that t(p-1)

[kq]

t(q-1)

k= 1

P

1= 1

L

- + L

[lP] _P - 1 q - 1

- --2

q

or

2

=p-lq-l 2 2

(mod 2),

then the theorem will follow. It suffices therefore to prove the following lemma.

Lemma.

_P- 1q- 1 L [kq] -P + L [IP] -q . 2 2

t(p-1)

t(q- 1)

k= 1

1= 1

Proof Consider the rectangle with vertices: (O,tq)

(0,0), (0, tq), (tp, 0), (tp, tq)

<tp,O)

(0,0)

The diagonal from the origin does not pass through any lattice point (a point with integer coordinates). This is because if (x, y) is a lattice point on the diagonal, then xq - yp = 0 and so pix, qly, showing that (x,y) must lie outside the rectangle. The total number oflattice points in the rectangle is 1) . t(q - 1). The number of lattice points in the two triangular regions below and above the diagonal are respectively

t(P -

t(I

1

)

k=l

The lemma is therefore proved.

[kq] , P

0

Example 1. Determine those primes p > 3 of which 3 is a quadratic residue. From the law of quadratic reciprocity we have

(3) (p)

p-1 \p = 3 (- 1)-2-.

41

3.3 The Law of Quadratic Reciprocity

Now

{m~I'

G)~ (-/)~ p

p-l

(-1)-2-=

{

if p=.1

-I,

(mod 3),

if p=.2 (mod 3); if p=.1 (mod 4), if p =. - 1 (mod 4).

1 ' - 1,

It follows from the Chinese remainder theorem that if p =. if p =.

±1

(mod 12), ± 5 (mod 12).

Example 2. Determine those primes p -:f 5 of which 5 is a quadratic residue.

From the law of quadratic reciprocity we have (;) = (~), and

(5"2) =(-1)-8-= -1, 52-1

G)= 1,

G)=(-5 2 )=-I,

(i) =

so that if p =. ± 1 (mod 5), if p =. ± 2 (mod 5). Example 3. Determine those primes p of which 10 is a quadratic residue.

From Example 2 and the Chinese remainder theorem we have if p =. if p =.

± 1, ± 3, ± 9, ± 13 (mod 40), ± 7, ± 11, ± 17, ± 19 (mod 40).

Example 4. Determine the solubility of x 2 =. -1457 (mod2389).

Here p = 2389 is a prime. Since - 1457 = - 31 x 47 it follows from (

~ 1) = 1,

(:1) =

(:J e =

2 1) = 1,

(~) = (:7) = (:7)G~) = - (~7)G~) 8 = - G)C 3) = - G)C23) = - I, that

C2~n7

) = - 1, so that the congruence is not soluble.

Exercise 1. Show that (;3) = 1,

G~) =

- 1.

195) = - 1, (74) Exercise 2. Show that ( 1901 101 = - 1, (365) 1847 = 1.

1,

42

3. Quadratic Residues

Exercise 3. Show that

= ±1

or

±5

(mod 24),

then(~) = 1;

±7

or

±

(mod 24),

then

if

p

if

p=

11

(~) = -

1.

3.4 Practical Methods for the Solutions Although the theory above is simple and beautiful, it is nevertheless rather negative. By this we mean the following. If, following our theory, the congruence is insoluble, then the problem is finished. However, if the congruence is soluble, we may further ask for the actual solutions to the congruence, and the method does not give us the solutions. In actual fact, when p is large, the determination of the solutions to x 2 = n (modp) is no easy matter. However, ifp = 3 (mod 4) or p = 5 (mod 8), then we have the following methods. 1) p = 3 (mod 4). Since (;) = 1, we have n t (p-1) = 1 (mod p). and so (n!
=(1.2 ...

~(P-l)Y=(G(P-l)!y

This gives us a solution. From (!)

=

1, we have

nt (p-1) - 1 = 0

(modp).

Now n satisfies n!
=1

(modp)

or n!
=- 1

(modp).

From the first congruence we have

From the second congruence we have (n~p+3)f

=-

n

(modp),

(modp).

(1)

43

3.4 Practical Methods for the Solutions

so that

3) p == 1 (mod 8). This is a more difficult case. When p is not too large, we usually use the method of successive eliminations. The congruence X Z == n (mod p) is equivalent to the indeterminate equation X Z = n + py. We may assume that 0< n

2, p,re, and we let nb nz, n3, ... be the quadratic non-residues. Denote by Vb Vz, ... the solutions to

n

+ py == nz,...

(mode).

If y == Vi (mod e), then py + n is a quadratic non-residue mod e, and is therefore not a square. We may therefore discard those y == Vi (mode). We may further discard more values of y by choosing different values of e until the number of trials is small enough not to be troublesome. X Z == 73 (mod 127). We try to solve x 2 = 127y + 73 where 1 ::;;; y ::;;; 31. We take e = 3, ni = 2. From 73 + 127y == 2 (mod 3), that is y == 1 (mod 3), we see that the remaining values for y are:

Example. Solve

2,3,5,6,8,9,11,12,14,15, 17, 18,20,21,23,24,26,27,29,30. We next take e = 5, ni = 2, n2 = 3. From 127y + 73 == 2,3 (mod5), we have VI == 2, V2 == 0 (mod 5) and so the remaining values for yare now 3,6,8,9,11,14,18,21,23,24,26,29. We next take e = 7, ni = 3, n2 = 5, n3 = 6. From the congruences 127y + 73 == 3,5,6 (mod 7), or y + 3 == 3, 5, 6 (mod 7) we have y == 0,2, 3 (mod 7), so that we are left with only the six values 6,8,11,18,26,29 for the trials. In fact 73 the solutions.

+8 x

127 = 1089 = 33 2 so that x == ± 33 (mod 127) are

Note. In this method, having taken e and e', there is no need to take ee'. Again, having taken an odd e, there is no need to take 2e.

All we discuss here is related to the work of Gauss. We see therefore that this "Prince of mathematics" is not only a theoretician, but also an expert problem solver.

44

3. Quadratic Residues

3.5 The Number of Roots of a Quadratic Congruence Theorem 5.1. Let I> 0, p,tn. If p > 2, then the congruence X2 = n (mod pI) has 1 + (~) solutions. If p = 2, then we have the following three cases. 1) 1= 1. There is one root. 2) I = 2. There are two or no roots depending on whether n = 1 or 3 (mod 4). 3) I > 2. There are four or no roots depending on whether n = 1 or n =1= 1 (mod 8). Proof We first discuss the three cases associated with p = 2. 1) This is trivial. 2) The congruence X2 = 1 (mod 4) has the solutions ± 1 (mod 4) and the congruence X2 = 3 (mod 4) has no solution. 3) If X2 = n (mod 2') is soluble, then x must be odd, say 2k + 1. Since . k(k + 1) (2k+l)2=4k(k+l)+1=8' 2 +1=1

(mod 8),

it follows that the congruence is not soluble if n =1= 1 (mod 8). Suppose now that n = 1 (mod 8). When I = 3, there are clearly the four roots 1,3,5,7. We now proceed by induction on I. Let a satisfy a 2 = n (mod 2' - 1 ). Then

We take b = (n - a 2)j2'-l. Then a + 2' - 2b is a solution with respect to mod2'. Therefore a solution to X2 = n (mod 2') certainly exists. Let Xl be a solution, and let X2 be any solution. Then x~ = (Xl - X2)(Xl + X2) = 0 (mod2'), and since Xl - X2, Xl + X2 are both even it follows that t(Xl - X2) . t(Xl + X2) = 0 (mod 2' - 2 ). But t(Xl - X2) and t(Xl + X2) must be of opposite parity, since otherwise their sum Xl cannot be odd. Therefore we have either Xl = X2 (mod2 ' - l ) or Xl = - X2 (mod2 ' - l ), and this means that X2 = ± Xl + k2 ' - l (k = 0 or 1). Hence there are at most four solutions to X2 = n (mod 2'). Since ± Xl> ± Xl + 2' - 1 are actually incongruent solutions we see that the congruence has exactly four solutions. When p > 2 and I = I, the result is trivial, and the remaining part of the theorem follows from Theorem 2.9.3. D

xi -

From the results of Chapter 2 we can determine the number of solutions to a quadratic congruence to any integer modulus m.

3.6 Jacobi's Symbol Throughout this section m denotes a positive odd integer. Definition. Let the standard factorization of m be PI ... Pt, where the Pr may be repeated. If (n,m) = 1 then we define the Jacobi's symbol by

45

3.6 Jacobi's Symbol

(-mn) =0 G) t

r=1

Examples.

r

(~) = 1. If (a,m) = 1, then (~) = 1.

Note: If (:) = 1, it does not follow that x 2

=n (modm) is soluble.

Theorem 6.1. Let m and m' be positive odd integers. (i) If n

= n'

(modm) and

(n, m) = 1, then (:) = (:). (ii) If(n, m) = (n, m') = 1, then (:) (;,) = (m:'). (iii) If(n,m) = (n',m) = 1, then (:)(:) = (:'). Theorem 6.2. (

-:n 1)

D

= ( - l)t(m-l).

Proof. It suffices to prove that t

t

L

Pi - 1 2

i=1

=

OPi- 1 (mod 2),

i=1

2

which certainly holds when t = I. Given any two odd integers u, v we always have

u - 1 v-I -2- + -2-

=-uv2- -1

(mod 2)

(or (u - 1)(v - I)

=0 (mod4)).

It follows by induction that t

Pi -

1

t-l Pi -

1

Pt -

1

L=i= L - +2i= 1 2 1 2 t-l

o

_

Theorem 6.3.

i=1

Pi -

1

1

0 Pi -

= 222 +~

1

i=1

(mod 2).

(~) = (_ 1)~mL1).

Proof. This is similar to the above, except that we replace (I) by U2 V 2 -

8

1

u2 - 1 v2 - 1 = - 8 - + - 8 - (mod 2).

D

Theorem 6.4. Let m, n be coprime positive odd integers. Then ( -m)(n) n m

~.'!!..::..! 2.

= ( - 1) 2

D

(1)

46

3. Quadratic Residues

Proof Let m = TIp, n =

=

TI q. Then n-lm-l

p-lq-l

TITI (- 1)-2--2- = (- 1)-2--2p

where we have used (1).

q

0

In using the Legendre's symbol we must always ensure that the denominator is a prime. In using Jacobi's symbol however, we can avoid the factorization process. For example:

383) (443) ( 60 ) ( 22 ) ( 15 ) ( 15 ) ( 443 = - 383 = - 383 = - 383 383 = - 383 8 8 = C1 :) = ( 5) = (25) = 1. If we delete the condition that m, m' are positive in Theorem 6.4, then we have:

Theorem 6.5. Let m, n be coprime odd integers.

(Imln)(m) jnf = - ( -

Otherwise, the required value is ( -

If m, n are both negative, then m-ln-l

1)-2--2-.

l)t<m-l).!
Example. Determine the solubility of x 2

=-

0

286 (mod 4272943).

Here p = 4272943 is a prime, and we have 10 evaluate (-:86). Since

(~1) = _ 1, (~) = 1, we have (-:86) = We now determine

C;3)

(~1 )(~)C;3) = _ C;3).

as follows: We have

4272943 = 29880 x 143 + 103*, 143 = 2 x 103 - 63, 103 = 2 x 63 - 23, 63 = 2 x 23 + 17*, 23 = 2 x 17 17 = 2 x

11,

11 - 5*,

11=2x5+1

47

3.7 Two Terms Congruences

where each step with a * denotes a change of sign. Therefore

p

( 143) = (-I? =-1. Thus ( as

;86) = I,

and the congruence is soluble. Gauss determined the solutions

± 1493445.

3.7 Two Terms Congruences Let p be prime. We now discuss the congruence

Xk

== n (modp).

Theorem 7.1. The congruence Xk

== I (modp)

(I)

has (k,p - I) roots. Proof I) Let d = (k,p - I) and let s, t be integers such that sk + t(p - I) then have :x;
=

== I (modp),

d. We

(2)

and conversely. 2) It suffices to prove that (2) has d roots. From Theorem 2.9.1 the number of roots for (2) certainly cannot exceed d. Also, there are p - I roots to xP- 1 == I (modp). Again, by Theorem 2.9.1 the number of roots for

xp -

1 -

I

p-l

- . , - - - = (Xd)-d-- 1

:x;
+ ... + x d + I == 0

(modp)

does not exceed p - I - d, so that the number of roots for (2) must be at least d. The theorem is proved. 0 Theorem 7.2. Either the congruence (k,p - I) solutions.

Xk

== n (modp), p,rn has no solution or it has

Proof If Xo is a solution, then (X;;-l X)k == follows from Theorem 7.1. 0

XkX;;-k

== I (modp). The required result

Theorem 7.3. If x runs over a reduced set of residues mod p, then (p - I)/(k,p - I) different values.

Xk

take

Proof From Theorem 7.2 we see that there are (k,p - I) distinct residues whose k-th power have the same residue modp. The p - I residues are now partitioned into (p - I)/(k,p - I) classes, and there is a one-to-one correspondence. 0

48

3. Quadratic Residues

Definition. Let h be an integer, and (h, n) = 1. The least positive integer I such that h' == I (modn) is called the order of h (modn). Theorem 7.4.

If hm == I (modn), then 11m.

Proof Suppose the contrary. Then there are integers q, r such that m = ql + r, 0< r < I. Now hr == hm(h,)-q == I (modn) contradicts with the definition of I. 0 Theorem 7.5. Let lip - I, and denote by ({)(/) the number ofincongruent integers with order I. Then ({)(I) is the Euler's function.

Proof We first establish certain properties of (()(I). I) If (110 12) = I, then ({)(l1/2) = ({)(lr)({)(l2). Let hI and h2 be integers with orders 11 and 12 respectively, and let Ibe the order of h 1h 2. From I == (h1h2)"2 == h';2 (modp), and Theorem 7.4 we see that / 11112. Since (110 12) = I, we have 111/, and similarly /211. Therefore I = 1112, that is· the order of h1h2 is 11/2. Thus, given any hI, h2 with orders 11,/2, we can construct h1h2 whose order is 11/2. We now prove that if we do not have hI == h~,h2 == h~ (modp), then h1h2 i= h~h~ (modp). For if h1h2 == h'lh~ (modp), then h 1h'1-1 == h~h21 (modp). But the order of h1h~-1 divides 11 and the order of h~h21 divides 12, so that h1h~-1 ==h~h21 == I (modp) which contradicts our assumption. Conversely, if h is an integer with order 11/2 where (/r,/2) = I, then hI = h'2, h2 = h" are integers with orders 110 12. Therefore ({)(lr)({)(/2) = (()(l1/2). 2) If q is prime, then ({)(qt) = qt - qt-1. The number of roots of xqt - 1 == 0 (mod p) is qt. If x satisfies this congruence and its order is not qt, then it must satisfy ~t-' _ I == 0 (modp). But the number of roots of this congruence is qt-1. Therefore ({)(qt) = qt _ qt-1. That (()(I) is Euler's function follows from the two properties in I) and 2). 0

3.8 Primitive Roots and Indices From Theorem 7.5 we see that there are ({)(p - I) incongruent numbers with order p - I (modp). Definition 1. A positive integer whose order is p - I is called a primitive root of p. Let g be a primitive root of p. Then gO, gl, . .. , gP- 2 are incongruent (modp). Definition 2. Corresponding to each integer n not divisible by p, there exists a such that

n == ga

(modp),

O~a
We call athe index ofn (modp) and we denote it by indg n or simply ind n. If b is such that n == gb (modp), then b == indn (modp - I).

49

3.9 The Structure of a Reduced Residue System

The function ind is similar to the logarithm function in that there are following properties: I) indnm == indm + indn (modp - l),p,rmn; 2) indn' == lindn (modp - 1),p,rn. Note: We do not define indn when pin; this is similar to not defining log O. Definition 3. Let p,rn. If the congruence

Y!' == n (modp)

(1)

is soluble, then we call n a k-th power residue mod p; otherwise we call n a k-th power non-residue. Theorem 8.1. A necessary and sufficient condition for n to be a k-th power residue modp is that (k,p - I) divides indn.

Proof Let a = indn and y = indx. Then (I) is equivalent to ky == a (modp - 1), and a necessary and sufficient condition for this to be soluble is that (k,p - 1) divides a. D "Base interchange formula". It is clear that the index depends on the primitive root chosen. Let gi be another primitive root and gi == gb (modp). Then n == g~ == (gb)a (modp) or

This is similar to the base interchange formula for the logarithm function. We list the least primitive roots for all the primes up to 5000 at the end of this chapter.

3.9 The Structure of a Reduced Residue System Let m be a natural number. We ask whether there exists

g

such that

gO, gi, g2, ... , g,,(m)-i (modm) form a reduced residue system. If g exists, then we

call it a primitive root of m. Theorem 9.1. A necessary and sufficient condition for m to have a primitive root is that m = 2,4,p' or 2p', where p is an odd prime.

Proof 1) Let the standard factorization of m be

Pi
From Euler's theorem, any integer a not divisible by Pi must satisfy

50

3. Quadratic Residues

Let I be the least common mUltiple of cp(it'), ... , cp(p!s) so that a l = I (modm). Therefore there can be no primitive root if 1< cp(m). If p > 2, then cp(pl) is even, so that m cannot have two distinct odd prime divisors. If m has a primitive root, then m must be of the form 21, i or 2cpl. If c ~ 2, then cp(2C) = 2C- 1 is also even, and so 2ci cannot have primitive roots. Therefore m must be of the form 21,pl or 2pl. 2) m = 21. If I = I, then I is a primitive root. If 1= 2, then 3 is a primitive root. Let I ~ 3. We prove by induction that for all odd a, we have a 2' - 2

=

I

(mod 21).

This is easy, since if then

Therefore there is no primitive root for m = 21 (/ > 2). 3) m = i. The case I = I has already been settled in §8. Let g be a primitive root of p. If gP-l - I =1= 0 (modp2), then we take r = g; if gP-l - I = 0 (modp2), then we take r = g + p. We then have

Therefore such an r is a primitive root of p2. Let rP -

1 -

I

=

kp, p,tk.

Since s~O,

we can prove as before that

Hence rpl - 2 (p-l)

= I + kp l-l

(mod pi) ,

I

~

2.

(1)

If the order of r is e, then el(p - I)pl-l = cp(i). Since r is a primitive root of p, we see that(p - 1)le. We deduce from (I) that e = cp(Pl); that is r is a primitive root ofi· 4) m = 2pl. We take g to be a primitive roqt of pl. If g is odd, then g is also a primitive root of 2pl; if g is even, then g + pi is a primitive root of 2pl. D Theorem 9.2. Let I > 2. Then the order of 5 with respect to the modulus 21 is 21- 2.

Proof We first prove that, for a

52a - 3

~

3,

= I + 2a -

1

(mod2 a ).

51

3.9 The Structure of a Reduced Residue System

This clearly holds when a 5 2a - 2 = (5 2a - 3 f

Therefore 521-3 (mod 21). D

=1=

= 3,

and we now proceed by induction. We have

== (1 + 2a- 1 + k2a)2 == 1 + 2a (mod2 a+ 1 ).

1 (mod 21) and 52' - 2 == 1 (mod 21). That is, the order of 5 is 21- 2

Theorem 9.3. Let I > 2. Then, given any odd a, there exists b such that a-I

a == ( - 1)-2-5 b

(mod 21),

b

~

0.

Proof If a == 1 (mod 4), then by Theorem 9.2, 5b (0::;;; b < 21- 2) gives 21- 2 distinct numbers mod 21; moreover they are all congruent 1 (mod 4). Therefore there must be an integer b such that a == 5b (mod 21). If a == 3 (mod 4), then - a == 1 (mod 4), and the required result follows from the above. D

Theorem 9.4. Let m = 21 . pili . .. p~s (standard factorization) with I ~ 0, 11 > 0, ... , Is > 0. We define (j to be or 1 or 2 according to whether 1= 0, 1 or 1= 2 or I > 2

°

respectively. Then the reduced residue system ofm can be represented by the products of s + (j numbers. Proof 1) Suppose that m = m'm", (m', m") = 1. Let ar, .. . , aq>(m') be a reduced residue system mod m', and that ai == 1 (modm") (this is always possible). Let br, ... , bq>(m") be a reduced residue system mod m" and that bj == 1 (modm'). Then aibj represen t a reduced residue system mod mm', and its num ber is q>( m'm"). Also, if aibj == asb t (modm'm"), then ai == as (modm'), bj == b t (modm"). 2) From Theorems 9.1 and 9.3 we know that the reduced residue system modm, where m = pi (p > 2), is the product of a single number. If m = 21 where I > 1, then the reduced residue system is the product of (j numbers. Combining this with 1), the theorem is proved. D

This theorem points out an important principle. In group theory this result is known as the Fundamental Theorem of Abelian groups. Exercise. Prove that if k < p, n, = kp2

+ 1 and

2n -

1

== 1 (modn),

then n is a prime number. Hints: (i) First prove.that n has a prime divisor congruent 1 (modp). Let dbe the least positive integer such that 2d == 1 (mod n). Deduce that d,tk, din - 1 and pld. Then obtain the conclusion from pldlq>(n). (ii) Deduce from n = kp2 + 1 = (up + 1)(vp + 1) that n cannot be composite. Note: Taking p = 2127 - 1, k = 180, Miller and Wheeler proved, with the aid of a computer, that 180(2127 - 1)2 + 1 is prime. (Nature 168 (1951),838).

52

3. Quadratic Residues

The least primitive roots for primes less than 5000. An asterisk indicates that lOis a primitive root. p

p-1

g

p

p-1

g

p

p-1

g

3 5 7* 11 13 17* 19* 23* 29* 31 37 41 43 47* 53 59* 61* 67 71 73 79 83 89 97* 101 103 107 109* 113* 127 131* 137 139 149* 151 157 163 167* 173 179* 181* 191 193* 197 199 211 223* 227 229* 233* 239

2 22 2·3 2·5 22.3 24 2.3 2 2·11 22.7 2·3·5 22.3 2 23 .5 2·3·7 2·23 22.13 2·29 22.3.5 2·3·11 2·5·7 23 .3 2 2·3·13 2·41 23 .11 25 .3 22.5 2 2·3·17 2·53 22.3 3 24 .7 2.3 2.7 2·5·13 23 ·17 2·3·23 22.37 2.3.5 2 22.3.13 2.3 4 2·83 22.43 2·89 22.3 2.5 2·5·19 26 .3 22.7 2 2.3 2·11 2·3·5·7 2·3·37 2·113 22.3.19 23 ·29 2·7·17

2 2 3 2 2 3 2 5 2 3 2 6 3 5 2 2 2 2 7 5 3 2 3 5 2 5 2 6 3 3 2 3 2 2 6 5 2 5 2 2 2 19 5 2 3 2 3 2 6 3 7

241 251 257* 263* 269* 271 277 281 283 293 307 311 313* 317 331 337* 347 349 353 359 367* 373 379* 383* 389* 397 401 409 419* 421 431 433* 439 443 449 457 461* 463 467 479 487* 491* 499* 503* 509* 521 523 541* 547 557 563

24 .3.5 2.5 3 23 2·131 22 ·67 2.3 3 .5 22.3.23 23 .5.7 2·3·47 22.73 "2.3 2.17 2·5·31 23 .3.13 22.79 2·3·5·11 24.3.7 2·173 22.3.29 25 ·11 2·179 2·3·61 22.3.31 2.3 3 .7 2·191 22.97 22.3 2·11 24.5 2 23 .3.17 2·11·19 22.3.5.7 2·5·43 24.3 3 2·3·73 2·13·17 26 .7 23 .3.19 22.5.23 2·3·7·11 2·233 2·239 2.3 5 2.5.7 2 2·3·83 2·251 22 ·127 22.5.13 2.3 2.29 22.3 3 .5 2·3·7·13 22 ·139 2·281

7 6 3 5 2 6 5 3 3 2 5 17 10 2 3 10 2 2 3 7 6 2 2 5 2 5 3 21 2 2 7 5 15 2 3 13 2 3 2 13 3 2 7 5 2 3 2 2 2 2 2

569 571* 577* 587 593* 599 601 607 613 617 619* 631 641 643 647* 653 659* 661 673 677 683 691 701* 709* 719 727* 733 739 743* 751 757 761 769 773 787 797 809 811* 821* 823* 827 829 839 853 857* 859 863* 877 881 883 887*

23 .71 2·3·5·19 26 .3 2 2·293 24 .37 2·13 ·23 23 .3.5 2 2·3·101 22.3 2·17 23 .7.11 2·3·103 2.3 2.5.7 27 .5 2·3·107 2·17·19 22 ·163 2·7·47 22.3.5.11 25 .3.7 22.13 2 2·11·31 2·3·5·23 22.5 2·7 22.3.59 2·359 2.3.11 2 22.3.61 2.3 2.41 2·7·53 2.3.5 3 22.3 3 .7 22.5.19 28 .3 22 ·193 2·3·131 22 ·199 23 ·101 2.3 4.5 22.5.41 2·3·137 2·7·59 22.3 2.23 2·419 22.3.71 23 ·107 2·3·11·13 2·431 22.3.73 24.5.11 2.3 2.72 2·443

3 3 5 2 3 7 7 3 2 3 2 -3

:,

11 5 2 2 2 5 2 5 3 2 2 11 5 6 3 5 3 2 6 11 2 2 2 3 3 2 3 2 2 11 2 3 2 5 2 3 2 5

53

3.9 The Structure of a Reduced Residue System

p

p-1

g

p

p-1

g

p

p-1

g

907 911 919 929 937* 941* 947 953* 967 971* 977* 983* 991 997 1009 1013 1019* 1021* 1031 1033* 1039 1049 1051* 1061 1063* 1069* 1087* 1091* 1093 1097* 1103* 1109* 1117 1123 1129 1151 1153* 1163 1171* 1181* 1187 1193* 1201 1213* 1217* 1223* 1229* 1231 1237 1249 1259* 1277 1279

2·3·151 2'5'7·13 2'3 3 '17 25 ·29 23 '3 2'13 22'5.47 2'11·43 23 '7'17 2·3·7·23 2·5'97 24 ,61 2·491 2.3 2-5-11 22'3'83 24 '3 2'7 22 ·11·23 2'509 22. 3· 5 ·17 2'5·103 23 .3.43 2·3·173 23 ·131 2'3'5 2'7 22'5'53 2'3 2'59 22'3'89 2'3·181 2'5·109 22'3'7'13 23 ·137 2'19·29 22 ·277 22'3 2'31 2·3·11·17 23 '3'47 2'5 2'23 27 .3 2 2'7·83 2'3 2'5'13 22'5'59 2·593 22 ·149 24 '3'5 2 22.3'101 26 ·19 2·13·47 22,307 2·3·5·41 22'3'103 25 .3.13 2·17'37 22'11.29 2.3 2'71

2 17 7 3 5 2 2 3 5 6 3 5 6 7 11 3 2 10 14 5 3 3 7 2 3 6 3 2 5 3 5 2 2 2 11 17 5 5 2 7 2 3 11 2 3 5 2 3 2 7 2 2 3

1283 1289 1291* 1297* 1301* 1303* 1307 1319 1321 1327* 1361 1367* 1373 1381* 1399 1409 1423 1427 1429* 1433* 1439 1447* 1451 1453 1459 1471 1481 1483 1487* 1489 1493 1499 1511 1523 1531* 1543* 1549* 1553* 1559 1567* 1571* 1579* 1583* 1597 1601 1607* 1609 1613 1619* 1621* 1627 1637 1657

2·641 23 '7.23 2'3'5'43 24 '3 4 22. 52 ·13 2·3·7·31 2·653 2·659 23 .3.5.11 2'3·13·17 24 '5'17 2·683 22'7 3 22'3'5'23 2·3·233 27'11 2'3 2'79 2·23'31 22. 3· 7 ·17 23 ·179 2'719 2'3'241 2'5 2.29 22. 3.11 2 2'3 6 2.3.5'7 2 23 '5'37 2·3·13·19 2'743 24 .3'31 22'373 2'7·107 2·5·151 2'761 2.3 2. 5 ·17 2·3·257 22'3 2'43 24 '97 2·19·41 2'3 3 '29 2·5·157 2'3'263 2·7·113 22. 3· 7 ·19 26 ,5 2 2 ·11· 73 23 '3'67 22'13'31 2·809 22'3 4 '5 2·3·271 22,409 23 ,3 2 ,23

2 6 2 10 2 6 2 13 13 3 3 5 2 2 13 3 3 2 6 3 7 3 2 2 5 6 3 2 5 14 2 2 11 2 2 5 2 3 19 3 2 3 5 11 3 5 7 3 2 2 3 2 11

1663* 1667 1669 1693 1697* 1699 1709* 1721 1723 1733 1741* 1747 1753 1759 1777* 1783* 1787 1789* 1801 1811* 1823* 1831 1847* 1861* 1867 1871 1873* 1877 1879 1889 1901 1907 1913* 1931 1933 1949* 1951 1973 1979* 1987 1993* 1997 1999 2003 2011 2017* 2027 2029* 2039 2053 2063* 2069* 2081

2·3·277 2'7 2'17 22'3'139 22'3 2'47 25 '53 2·3·283 22'7'61 23 '5'43 2·3'7·41 22'433 22'3'5'29 2· 32·97 22'3'73 2'3'293 24 '3'37 2.3 4 '11 2·19'47 22'3'149 23 '3 2.5 2 2·5·181 2·911 2'3·5·61 2·13'71 22'3'5'31 2'3'311 2'5·11'17 24 '3 2'13 22'7.67 2·3'313 25 '59 22. 32'19 2'953 23 ·239 2·5·193 22'3'7'23 22 ·487 2'3'5 2'13 22'17'29 2·23·43 2·3·331 22'3'83 22'499 2.3 3 .37 2·7·11·13 2·3·5·67 25 .3 2.7 2 ·1013 22'3'13 2 2·1019 22.3 3 '19 2·1031 22 ·11·47 25 .5'13

3 2 2 2 3 3 3 3 3 2 2 2 7 6 5 10 2 6 11 6 5 3 5 2 2 14 10 2 6 3 2 2 3 2 5 2 3 2 2 2 5 2 3 5 3 5 2 2 7 2 5 2 3

54

3. Quadratic Residues

p

p-I

g

p

p-I

g

p

p-I

g

2083 2087 2089 2099* 211l 21l3* 2129 2131 2137* 2141* 2143* 2153* 2161 2179* 2203 2207* 2213 2221* 2237 2239 2243 2251* 2267 2269* 2273* 2281 2287 2293 2297* 2309* 2311 2333 2339* 2341* 2347 2351 2357 2371* 2377 2381 2383* 2389* 2393 2399 2411* 2417* 2423* 2437* 2441 2447* 2459* 2467 2473*

2·3·347 2·7·149 23 .3 2.29 2·1049 2·5·21l 26 .3 ·Il 24.7.19 2·3·5·71 23 .3.89 22.5.107 2.3 2.7.17 23 ·269 24.3 3 .5 2.3 2.1l 2 2·3·367 2·1l03 22.7.79 22.3.5.37 22.13.43 2·3·373 2·19· 59 2.3 2.5 3 2·11·103 22.34.7 25 ·71 23 .3.5.19 2.3 2.127 22.3.191 23 .7.41 22.577 2·3·5·7·1l 22. II· 53 2·7·167 22.3 2.5.13 2·3·17·23 2.5 2 .47 22 .19.31 2·3·5·79 23 .3 3 ·Il 22.5.7.17 2·3·397 22.3.199 23 .13.23 2· 11·109 2·5·241 24 ·151 2·7·173 22 .3.7.29 23 .5.61 2 ·1223 2 ·1229 2.3 2.137 23 .3.103

2 5 7 2 7 5 3 2 10 2 3 3 23 7 5 5 2 2 2 3 2 7 2 2 3 7 19 2 5 2 3 2 2 7 3 13 2 2 5 3 5 2 3 II 6 3 5 2 6 5 2 2 5

2477 2503 2521 2531 2539* 2543* 2549* 2551 2557 2579* 2591 2593* 2609 2617* 2621* 2633* 2647 2657* 2659 2663* 2671 2677 2683 2687* 2689 2693 2699* 2707 271l 2713* 2719 2729* 2731 2741* 2749 2753* 2767* 2777* 2789* 2791 2797 2801 2803 2819* 2833* 2837 2843 2851* 2857 2861* 2879 2887 2897*

22.619 2.3 2.139 23 .3 2.5.7 2·5·1l·23 2.3 3 .47 2·31·41 4.7 2.13 2.3.5 3 .17 22.3 2.71 2·1289 2·5·7·37 25 .3 4 24.163 23 .3.109 22.5.131 23 .7.47 2.3 3 .7 2 25 .83 2·3·443 2·1l 3 2·3·5·89 22.3.223 2.3 2.149 2·17·79 27 .3.7 22.673 2·19·71 2·3·1l·41 2·5·271 23 .3.113 2.3 2.151 23 .11.31 2·3·5·7·13 22.5.137 22.3.229 26 .43 2·3·461 23 .347 22.17.41 2.3 2.5.31 22.3.233 24.5 2.7 2·3·467 2 ·1409 24.3.59 22 ·709 2.7 2.29 2.3.5 2.19 23 .3.7.17 22.5. II· 13 2 ·1439 2·3·13·37 24.181

2 3 17 2 2 5 2 6 2 2 7 7 3 5 2 3 3 3 2 5 7 2 2 5 19 2 2 2 7 5 .3 3 3 2 6 3 3 3 2 6 2 3 2 2 5 2 2 2 II 2 7 5 3

2903* 2909* 2917 2927* 2939* 2953 2957 2963 2969 2971* 2999 3001 301l* 3019* 3023* 3037 3041 3049 3061 3067 3079 3083 3089 3109 3119 3121 3137* 3163 3167* 3169 3181 3187 3191 3203 3209 3217 3221* 3229 3251* 3253 3257* 3259* 3271 3299*' 3301* 3307 3313* 3319 3323 3329 3331* 3343* 3347

2·1451 22.727 22.3 6 2·7·1l·19 2·13·1l3 23 .3 3 .41 22.739 2 ·1481 23 .7.53 2.3 3 .5 ·Il 2 ·1499 23 .3.5 3 2·5·7·43 2·3·503 2 ·151l 22·3·1l·23 25 .5.19 23 .3.127 22.3 2.5.17 2·3·7·73 2.3 4.19 2·23·67 24 ·193 22.3.7.37 2·1559 24.3.5.13 26 .7 2 2·3·17·31 2·1583 22·3 2.1l 22.3.5.53 2.3 3 .59 2·5·1l·29 2·1601 23 .401 24.3.67 22.5.7.23 22.3.269 2.5 3 .13 22.3.271 23 .11.37 2·3·181 2·3·5·109 2·17·97 22.3. 52. II 2·3·19·29 24.3 2.23 2·3·7·79 2·1l·151 28 .13 2.3 2 .5.37 2·3·557 2·7·239

5 2 5 5 2 13 2 2 3 10 17 14 2 2 5 2 3 II 6 2 6 2 3 6 7 7 3 3 5 7 7 2 II 2 3 5 10 6 6 2 3 3 3 2 6 2 10 6 2 3 3 5 2

55

3.9 The Structure of a Reduced Residue System

p

p-1

g

P

p-1

g

3359 3361 3371* 3373 3389* 3391 3407* 3413 3433* 3449 3457 3461* 3463* 3467 3469* 3491 3499 3511 3517 3527* 3529 3533 3539* 3541 3547 3557 3559 3571* 3581* 3583 3593* 3607* 3613 3617* 3623* 3631 3637 3643 3659* 3671 3673* 3677 3691 3697 3701* 3709* 3719 3727* 3733 3739 3761 3767 3769

2·23·73 25 '3.5.7 2·5·337 22.3.281 22. 7 .11 2 2·3·5·113 2·13·131 22'853 23 • 3 ·11·13 23 ·431 27 ,3 3 22'5'173 2·3·577 2·1733 22. 3 .17 2 2'5'349 2·3·11·53 2'3 3 '5'13 22'3'293 2·41·43 23 ,3 2,7 2 22 ·883 2·29·61 22'3.5'59 2'3 2.197 22.7.127 2·3'593 2·3·5'7·17 22.5.179 2.3 2.199 23 '449 2·3·601 22'3'7'43 25 '113 2'1811 2.3'5.11 2 22. 32. 101 2·3·607 2·31'59 2·5'367 23 '3 3 '17 22'919 2'3 2'5'41 24 .3'7.11 22'5 2'37 22 • 32·103 2.11.13 2 2· 34 ·23 22'3'311 2·3·7·89 24 '5'47 2'7·269 23 '3'157

11 22 2 5 3 3 5 2 5 3 7 2 3 2 2 2 2 7 "2 5 17 2 2 7 2 2 3 2 2 3 3 5 2 3 5 21 2 2 2 13 5 2 2 5 2 2 7 3 2 7 3 5 7

3779* 3793 3797 3803 3821* 3823 3833* 3847* 3851* 3853 3863* 3877 3881 3889 3907 3911 3917 3919 3923 3929 3931 3943* 3947 3967* 3989* 4001 4003 4007* 4013 4019* 4021 4027 4049 4051* 4057* 4073* 4079 4091* 4093 4099 4111 4127 4129 4133 4139* 4153* 4157 4159 4177* 4201 4211* 4217* 4219*

2 '1889 24 '3'79 22 ·13· 73 2 ·1901 22'5'191 2'3'7 2'13 23 '479 2·3·641 2· 52. 7·11 22. 32·107 2·1931 22'3'17'19 23 '5'97 24 '3 5 2.3 2'7'31 2·5·17·23 22 ·11· 89 2·3·653 2·37'53 23 ·491 2·3·5·131 2'3 3 '73 2 ·1973 2·3·661 22 ·997 25 .5 3 2·3·23·29 2·2003 22'17'59 2'7 2'41 22'3'5'67 2·3·11·61 24 .11.23 2.3 4 '5 2 23 • 3 '13 2 23 '509 2·2039 2'5·409 22.3.11'31 2·3·683 2·3·5·137 2·2063 25 • 3 ·43 22 ·1033 2·2069 23 .3.173 22 ·1039 2.3 3 . 7'11 24 .3 2'29 23 '3'5 2'7 2'5'421 23 '17'31 2·3·19'37

2 5 2 2 3 3 3 5 2 2 5 2 13 11 2 13 2 3 2 3 2 3 2 6 2 3 2 5 2 2 2 3 3 10 5 3 11 2 2 2 17 5 13 2 2 5 2 3 5 11 6 3 2

p

4229* 4231 4241 4243 4253 4259* 4261* 4271 4273 4283 4289 4297 4327* 4337* 4339* 4349* 4357 4363 4373 4391 4397 4409 4421* 4423* 4441 4447* 4451* 4457* 4463* 4481 4483 4493 4507 4513 4517 4519 4523 4547 4549 4561 4567* 4583* 4591 " 4597 4603 4621 4637 4639 4643 4649 4651* 4657 4663

p-1

g

22'7'151 2'3 2'5'47 24 '5'53 2·3· 7 ·101 22 ·1063 2'2129 22'3.5'71 2'5'7·61 24 .3.89 2·2141 26 '67 23 '3'179 2·3'7·103 24 .271 2'3 2.241 22 '1087 22. 32.11 2 2·3·727 22 ·1093 2·5·439 22'7'157 23 ·19·29 22. 5·13 ·17 2· 3 ·11· 67 23 • 3· 5· 37, 2'3 2'13'19 2'5 2'89 23 '557 2·23·97 27 '5'7 2'3 3 '83 22 ·1123 2·3'751 25 .3'47 22 ·1129 2.3 2.251 2·7'17·19 2'2273 22'3'379 24 .3.5'19 2'3'761 2·29'79 2· 33 • 5 ·17 22'3'383 2·3 ·13'59 22 .3.5'7.11 22'19'61 2'3'773 2·11·211 23 '7'83 2'3'5 2'31 24 .3'97 2.3 2'7.37

2 3 3 2 2 2 2 7 5 2 3 5 3 3 10 2 2 2 2 14 2 3 3 3 21 3 2 3 5 3 2 2 2 7 2 3 5 2 6 11 3 5 11

5 2 2 2 3 5 3 3 15 3

56

3. Quadratic Residues

p

p-I

g

p

p -I

g

p

p-I

g

4673* 4679 4691* 4703* 4721 4723 4729 4733 4751 4759 4783* 4787 4789

26 .73 2·2339 2·5·7·67 2·2351 24 .5.59 2·3·787 23 .3.197 22 .7.13 2 2.5 3 .19 2·3·13·61 2·3·797 2·2393 22 .3 2 .7.19

3 II 2 5 6 2 17 5 19 3 6 2 2

4793* 4799 4801 4813 4817* 4831 4861 4871 4877 4889 4903 4909 4919

23 .599 2·2399 26 .3.5 2 22 .3.401 24 .7.43 2·3·5·7·23 22 .3 5 .5 2·5·487 22 .23.53 23 .13.47 2·3·19·43 22 .3.409 2·2459

3 7 7 2 3 3 II II 2 3 3 6 13

4931* 4933 4937* 4943* 4951 4957 4967* 4969 4973 4987 4993 4999

2·5·17·29 22 .3 2 ·137 23 .617 2·7·358 2·3 2 ·5 2 ·II 22 .3.7.59 2·13·191 23 .3 3 .23 22 ·II·II3 2.3 2 .277 27 .3.13 2.3.7 2 .17

6 2 3 7 6 2 5 II 2 2 5 3

Chapter 4. Properties of Polynomials

4.1 The Division of Polynomials We consider polynomialsf(x) with rational coefficients and we denote by 13°f the degree of the polynomial.

Definition 1.1. Let./{x) and g(x) be two polynomials with g(x) not identically zero. If there is a polynomial h(x) such that./{x) = g(x)h(x), then we say that g(x) divides j{x), and we write g(x)I'/{x) or glf If g(x) does not divide ./{x), then we write g,tf Clearly we have the following: (i)flf; (ii) ifflg and gil, thenfand g differ only by a constant divisor, and we call them associated polynomials; (iii) if fig and glh, then Jlh; (iv) if fig, then 13°f ~ aOg. Ifflg and g,tI, then we callfa proper divisor of g and it is easy to see that, in this case, 13°f < 13° g. Theorem 1.1. Let./{x) and g(x) be any two polynomials with g(x) not identically zero. Then there are two polynomials q(x) and r(x) such that f = q . g + r, where either r = 0 or aOr < aOg. Proof We prove this by induction on the degree off If 13°f < aOg, then we can take q = 0, r =f If aOf~ aOg, we let f=

IXnXn

+ ... ,

g = Pmxm

+ ... ,

aOf= n, 13° g = m,

so that

From the induction hypothesis, there are two polynomials h(x) and r(x) such that

where either r

so that f

=

0 or aOr < aOg. We now put

= qg + r as required. D

58

4. Properties of Polynomials

Definition 1.2. By an ideal we mean a set I of polynomials satisfying the following conditions: (i) If f, gEl, then f + gEl; (ii) IffE I and h is any polynomial, then fh E I. Example. The multiples of a fixed polynomial fix) forms an ideal.

Theorem 1.2. Given any ideal I, there exists a polynomial f E I such that any polynomial in I is a multiple off; that is I is the ideal of the set of multiples off Proof Let f be a polynomial in I with the least degree. If g is a polynomial in I which is not a multiple off, then, according to Theorem 1.1, there are polynomials q(x) and r(x) (1' 0) such that g

= qf + r,

Since f E I, it follows from (ii) that qfE I, and hence from (i) that g - qfE I, that is rEI. But this contradicts the minimal degree property of f The theorem is proved. D Definition 1.3. Let f and g be two polynomials. Consider the set of polynomials of the form mf + ng where m, n are polynomials. From Theorem 1.2 we see that this set is identical with the set of polynomial which are multiple of a polynomial d. We call this polynomial dthe greatest common divisor offand g, and we write (f, g) = d. For the sake of uniqueness we shall take the leading coefficient of (f, g) to be I, that is a monic polynomial. Theorem 1.3. The greatest common divisor (f, g) has the following properties: (i) There are two polynomials m, n such that (f, g) = mf + ng; (ii) For every pair of polynomials m, n we have if, g)lmf + ng; (iii) If Ilf and Ilg, then 11(f, g). D Definition 1.4. If(f, g) = I, then we say thatfand g are coprime. Theorem 1.4. Let p be an irreducible polynomial. If plfg, then either plf or pig. Proof If p,tf, then (f, p) = I. Thus, from Theorem 1.3 there are polynomials m, n such that mf + np = 1 so that mfg + ngp = g. Since plfg, it follows that pig. D

4.2 The Unique Factorization Theorem Theorem 2.1. Any polynomial can be factorized into a product of irreducible polynomials. If associated polynomials are treated as identical, then, apart from the ordering of the factors, this factorization is unique. D

59

4.2 The Unique Factorization Theorem

The theorem can be proved by mathematical induction on the degree of the polynomial. Theorem 2.2. Letj(x) and g(x) be two polynomials with rational coefficients, and that j(x) be irreducible. Suppose that f(x) = 0 and g(x) = 0 have a common root. Then j(x)lg(x). Proof Sincefand g have a common zero, it follows that (f, g) # l. Let d(x) be the greatest common factor of j(x) and g(x). Then d(x) and j(x) are associated polynomials, because j(x) is irreducible. Therefore j(x)lg(x). 0

From this theorem we deduce the following: Ifj(x) is an irreducible polynomial of degree n, then the zeros

are distinct. Moreover, if 9(i) is a zero of another polynomial g(x) with rational coefficients, then the other n - I numbers are also the zeros of g(x). Theorem 2.3. Let f and g be monic polynomials:

where Pv are distinct irreducible monic polynomials. Then

where

Cv

= min (a v , bv )' 0

Definition 2.1. Letfand g be two polynomials. Polynomials which are divisible by bothfand g are called common multiples offand g. Those common multiples which have the least degree are called the least common multiples, and we denote by [f, g] the monic least common multiple. Theorem 2.4. Under the same hypothe~is as Theorem 2.3 we have

where dv

= max (a v , bv ). 0

From this we deduce: Theorem 2.S. A least common multiple divides every common multiple. Theorem 2.6. Let f, g be monic polynomials. Then fg

=

[f, g](f, g).

0

0

60

4. Properties of Polynomials

4.3 Congruences Let m(x) be a polynomial. If m(x)lfix) - g(x), then we say that fix) is congruent to g(x) modulo m(x) and we write

fix)

= g(x)

(modm(x)).

With respect to any modulus m(x) we have: (i)f=f(modm); (ii) iff= g (modm), then g =f(modm); (iii) iff= g, g = h (modm), thenf= h (modm); (iv) iff= g, fl gl (modm), thenf ±fl g ± gl,ffl ggl (modm). Being congruent is an equivalence relation which partitions the set polynomials into equivalence classes. From (iv) we see that addition and multiplication can be defined on these classes. We denote by 0 the class whose members are divisible by m(x). If m(x) is irreducible we can even define division on the set of equivalence classes (except by 0, of course). Specifically, if fix) is not a mUltiple of m(x), then there are polynomials a(x), b(x) such that a(x}f{x) + b(x)m(x) = 1 which means that there is a polynomial a(x) such that a(x)f(x) = 1 (modm(x)). We state this as a theorem.

=

=

=

Theorem 3.1. Let m(x) be irreducible. Then any non-zero equivalence class has a reciprocal. That is, if A is a non-zero equivalence class, then there exists a class B such that for any polynomials fix) and g(x) in A and B respectively we have fix)g(x) = 1 (mod m(x)). D We now give an example to illustrate the ideas in this section. Let m(x) = x 2 + 1, an irreducible polynomial. Each equivalence class contains a unique polynomial ax + b which we may take as the representative. The addition and subtraction of classes is given by ax + b ± (alx + b l ) = (a ± al)x + (b ± bl)' Multiplication is given by (ax + b)(alx + b l ) = aalx 2 + (ab l + alb)x + bb l = (ab l + alb)x + bb l - aal (modx 2 + 1). Using the ordered pair (a, b) to denote the class containing ax + b we then have

(a,b)

± (abb l ) =

(a, b)(ah b l )

(a

± abb ± bl),

= (ab l + bal, bb l - aal)'

From

(ax

+ b)( -

ax

. . ( we see thatthe Inverse of (a, b) IS

+ b) = a2 + b2

(modx 2

+ 1),

b)

a 2' 2 2 2 ' In other words we have the a +b a +b arithmetic of the complex number ai + b. Extending the idea here, if m(x) is a monic polynomial of degree n, then each equivalence class possesses a unique polynomial with degree less than n, say -

and the arithmetic of the congruence modulo m(x) becomes the arithmetic of these

61

4.4 Integer Coefficients Polynomials

polynomials. The sum of two such polynomials is obtained by adding the corresponding coefficients, and the product is the ordinary product polynomial reduced modulo m(x). Exercise 1. Let OCl, OC2, OC3 be distinct. Determine a quadratic polynomial j(x) satisfying j(OC1) = /31 '/(OC2) = /32, j(OC3) = /33'

Answer: The Lagrange interpolation formula ft..x) = /31

(x - O(2)(X - O(3) (OCI - O(2)(OCl - O(3)

+ /32

(x - O(3)(X - OCl) (OC2 - O(3)(OC2 - OCl)

(x - OCl)(X - O(2)

+ /33...,..-----,---(OC8 - OCl)(OC3 - O(2)

Exercise 2. Let ml(x) and m2(x) be two non-associated irreducible polynomials. Let fl(X) andf2(x) be two given polynomials. Prove that there exists a polynomialj(x) such thatj(x) =/;(x) (modmi(x)), i = 1,2.

4.4 Integer Coefficients Polynomials It is clear that the set of integer coefficients polynomials is closed with respect to addition, subtraction and multiplication. A set of integer coefficients polynomials is called an ideal if (i) f + g belongs to the set whenever f and g belong to the set, (ii) fg belongs to the set whenever f belongs to the set, and g is any integer coefficients polynomial. Theorem 4.1. (Hilbert) Every ideal A possesses a finite number of polynomials fl' ... ,J,. with the following property: Every polynomial f E A is representable as f = glfl + ... + gnfn where gb' .. , gn are integer coefficients polynomials.

Proof 1) Denote by B the set ofleading coefficients of members of A. We claim that B forms an integral modulus. To see this, we observe that if a, bEB, where ft..x) = axn + .. " g(x) = bxm + .. " then by (ii) we know thatj{x)xm, g(x)x" E A so that

j(x)xm ± g(x)xn

=

(a

± b)xm+n + ...

are in A. Therefore a ± bEB which proves our claim. From Theorem 1.4.3 members of B are multiples of an integer d. Let the corresponding polynomial with leading coefficient d be

2) Let fEA. Then there are two polynomials q(x) and r(x) such that ft..x) = q(X)fl (x) + r(x) where oOr < OOfl or r = O. This is certainly so if the degree of fis less than that offl' Ifj(x) = axn + ... + an (n ~ I), then by 1) we see that dla, and

62

4. Properties of Polynomials

is a polynomial with degree at most n - I. If the degree here is greater than or equal to I, then its leading coefficient is again divisible by d. Continuing the argument we see that our claim is valid. 3) If every member of A has degree at least I, then the theorem is proved. Otherwise we let d' be the greatest common divisor of the leading coefficients of . members of A whose degree are less than I, and we let f2

= d'xl' + d'lX"-l + ...

(did')

be the corresponding polynomial in A. From the above, we see that members of A whose degree lies between l' and I can be written asfix) = Q(X)f2(X) + r(x) where aOr < a 2f2 or r = O. Continuing this argument the theorem is proved. 0

4.5 Polynomial Congruences with a Prime Modulus In this section all the polynomials have integer coefficients and p is a fixed prime number. Definition 5.1. If the corresponding coefficients of two polynomials fix) and g(x) differ by multiples of p, then we say thatf(x) and g(x) are congruent modulo p, and we writefix)~g(x) (modp). By the degree aOfofj(x) modulo p we mean the highest degree of f(x) whose coefficient is not a multiple of p. For example 7x 2 + 16x + 9~2x + 2 (mod 7), and a°(7x 2 + 16x + 9) = I (mod 7). But with respect to the modulus 3, a 2(7 x 2 + 16x + 9) = 2. Clearly we have (i) j(x)~j(x) (modp); (ii) if f~g (modp), then g~f (modp); (iii) if f~g, g~h (modp), thenf~h (modp); (iv) iff~g,Jl ~gl (modp), thenf ±fl ~g ± gl and ffl ~ggl (modp). We note particularly that (f(xW

~j(xP)

(modp).

Definition 5.2. Letf(x) and g(x) be polynomials with g(x) not identically zero mod p. If there is a polynomial h(x) such thatj(x) ~h(x)g(x) (modp), then we say that g(x) dividesf(x) modulo p. We call g(x) a divisor ofj(x) modulo p, and we write g(x)lj(x) (modp). Example. From XS + 3x4 - 4x 3 + 2 ~ (2X2 - 3)(3x3 - x 2 + I) (mod 5) we see that 2X2 - 31x s + 3x4 - 4x 2 + 2 (mod 5). We have the following: (i) f(x)lj(x) (modp); (ii) if j(x)lg(x) and g(x)lf(x) (modp), thenj(x) and g(x) differs only by a constant factor; that is, there exists an integer a such thatj(x)~ag(x) (modp). In this case we say thatj(x) and g(x) are associated modulo p. It is easy to see that every polynomial has p - I associates

63

4.6 On Several Theorems Concerning Factorizations

modulo p. Moreover, there is a unique monic associated polynomial. (iii) Ifflg, glh (modp), thenflh (modp). (iv) Letfix) and g(x) be two polynomials with g(x) not identically zero modulo p. Then there are two polynomials q(x) and r(x) such that fi.x)~q(x)g(x) + r(x) (modp), where either aOr < aOg, or r(x)~O (modp). Definition 5.3. If a polynomial fix) cannot be factorized into a product of two polynomials with smaller degrees modp, then we say that f(x) is an irreducible polynomial modp, or thatf(x) is prime modp. Example. We take p = 3. There are three non-associated linear polynomials, namely x, x + 1, x + 2, which are irreducible. There are nine non-associated quadratic polynomials, namely x 2 , x 2 + x, x 2 + 2x, x 2 + 1, x 2 + X + 1, x 2 + 2x + 1, x 2 + 2, x 2 + X + 2, x 2 + 2x + 2. Of these there are 6 (= (x + a)(x + b)) which are reducible, and the three irreducible ones are x 2 + 1, x 2 + X + 2, x 2 + 2x + 2.

We note that if a polynomial is irreducible mod p, then it is irreducible and from this we deduce that x 2 + 2x + 2 has no rational zeros. The determination of the number of irreducible polynomials modp of degree n is an interesting problem which we shall solve in §9. Theorem 5.1. Any polynomial can be written as aproduct of irreducible polynomials modp, and this product representation is unique apartfrom associates and ordering of the factors. 0 We can define, similarly to §1, the greatest common divisor and the least common multiple. If we denote by (f, g) the monic greatest common divisor, then we have Theorem 5.2. Given polynomials j(x) and g(x), there are polynomials m(x) and n(x) such that m(x)f(x) + n(x)g(x)~(f(x), g(x)) (modp). 0

4.6 On, Several Theorems Concerning Factorizations Definition 6.1. Letj(x) = anxn + an_1x"-1 + ... be a polynomial. The polynomial + (n - 1)an_lxn- 2 + ... is called the derivative ofj(x) and is denoted by

nanx"-l f'(x).

Clearly we have (f(x) + g(x))' = f'(x) that (f(x)g(x)), = f'(x)g(x) + g'(x)j(x).

+ g'(x),

and it is not difficult to prove

Definition 6.2. If a polynomial j(x) is divisible by the square of a non-constant polynomial modp, then we say thatfix) has repeated/actors modp. For example, x 5 + X4 - x 3 - x 2 + X + 1 has the repeated factors (x 2 + 1)2 modulo 3.

64

4. Properties of Polynomials

Theorem 6.1. A necessary and sufficient condition for j(x) to have repeatedfactors is that the degree of (j(x),f'(x» is at least 1. D Theorem 6.2. Ijp,(n, then X' - 1 has no repeatedfactors modp. Theorem 6.3. Let (m,n)

=

d. Then (x'" - 1, xn - 1) =;xd - 1.

D

D

Theorem 6.4. Let (m, n) = d. Then

4.7 Double Moduli Congruences Definition 7.1. Let p be a prime number and q>(x) be a polynomial. Iff1 (x) - fix) is a multiple of q>(x) mod p, then we say that f1 and f2 are congruent to the double moduli p, q>(x) and we write

f1(X) §. f2 (x)

(moddp, q>(x».

For example, x 5 + 3x4 + x 2 + 4x + 3 §. 0 (modd 5, 2X2 - 3). Double moduli congruences have the following properties: 1) j(x)§.j(x) (moddp, q>(x»; 2) If f§.g (moddp, q», then g§.f(moddp, q»; 3) If f§.g and g§.h (moddp, q», thenf§.h (moddp, q»; 4) If f§.g and f1 §.gl (modd p, q», then f ±f1 §.g ± gl and ff1 §.ggl (moddp, q»; 5) Suppose that the degree of q>(x) (modp) is n. Then every polynomial is congruent to one of the following polynomials

0::;;; ai::;;;p - 1.

(1)

It is clear that there are pn polynomials in (1), no two of them are congruent (moddp, q>(x», and any polynomial must be congruent to one of them (moddp, q>(x». Definition 7.2. We call the pn polynomials in (1) a complete residue system (moddp, q>(x». By discarding those polynomials which are not coprime with q>(x) we have a reduced residue system (moddp, q>(x».

Theorem 7.1. Let (g(x), q>(x» = 1. Then, asj(x) runs through a complete (or reduced) residue system (moddp, q>(x», so does f(x)g(x). Proof If g(X)f1 (x) §. g(X)f2(X) (moddp, q>(x», then from (g(x), q>(x» = I we deduce that f1 (x) §. f2 (x) (moddp, q>(x». The required result follows easily from this. D

65

4.8 Generalization of Fermat's Theorem

4.8 Generalization of Fermat's Theorem Let p be a prime number, and
(1)

Given any polynomial f(x) , we have (f(xW"~f(x)

(moddp,
(2)

and in particular, we have xp"~x

(moddp,
Proof Letfl(x), ... ,1P"-l(X) (moddp, (x). Then ffl' ... ,jJp" _ I is also a reduced residue system. Therefore p"-l

p"-l

n /;(x) n (f(x)f;(x)) ~

i= I

(moddp,
i= I

or p"-l

n

«f(xW"-1 - 1)

/;(x)~O

(moddp,
i= I

and hence (j(XW"-1

~

1

(modd p,
0

This theorem is a generalization of Fermat's theorem in Chapter 1. We note that (2) is a special case of (1), but we observe that (1) can also be deduced from (2), since (f(xW"~f(xP")~f(x)

(moddp,
Exercise. Generalize Euler's theorem in Chapter 2. Theorem 8.2. Any irreducible polynomial of degree n must divide Xp"-l - 1 (modp).

0

Theorem 8.3. The number of roots degree offiX).

off(X)~O

(moddp,
Proof Let g(x) be a root of the congruence, and let

so that

66

4. Properties of Polynomials

j(X) - j(g(x)) = an(Xn - (g(x)Y) =

+ an_l(xn- 1 -

(g(x))n-l)

+ ...

(X - g(x))h(X).

If gl(X) is another root distinct from g(x), then h(g 1 (X)) ~O (moddp, cp(x)), and the required result follows. D Theorem 8.4. x pn - 1 is not divisible by any irreducible polynomial of degree greater than n, modp. Proof Let I/J(x) be an irreducible polynomial with degree m > n, modp, and suppose, if possible, that xpn~x (moddp, I/J(x)). There are pm incongruent polynomials j(x)moddp, I/J(x). From (j(x))P~j(xP) (modp) we deduce that (j(x))pn~j(xpn)~j(x) (moddp, I/J(x)). This means that the number of roots of Xpn~X(moddp, I/J(x)), being pm, exceedspn. This is impossible by Theorem 8.3 so that the theorem is proved. D

Theorem 8.5. Let I/J(x) bean irreducible polynomial ofdegree I, modp. IfI/J(x)lxpn.- x (modp), then lin. Proof From Theorem 8.2 and the hypothesis, we have I/J(x)l(x pn -

1 -

1,xP1 -

1 -

1)

(modp),

and from Theorem 6.3, d = (n, I).

Moreover, from Theorem 8.4 we see that I lin. D

~

d = (n, I) so that 1= d, and hence

Exercise. Let I/J(x) and cp(x) be irreducible polynomials modp. Then a necessary and sufficient condition for the solubility of I/J(X) ~O (moddp, cp(x)) is that oOI/Jloocp. Prove further that if it is soluble then it can be factorized into a product of linear factors.

4.9 Irreducible Polynomials mod p Theorem 9.1. The product of all the irreducible polynomials of degree n (modp), is equal to (xpn/QIQ2 - x) xpn - X Ql,Q2 (modp),

TI

where qb q2,' .. run over the distinct prime divisors of n.

67

4.1 0 Primitive Roots

Proof By Theorem 6.1 the polynomial x p " - x has not repeated factors, so that it can be factorized into a product of various distinct irreducible polynomials of the form

where t/I(x)lx Pd - x, din. We now apply the inclusion-exclusion principle of §1. 7. We already know that x p " - x is a product of various irreducible polynomials of degree m where min. We exclude all those polynomials whose degrees divide n/ql; but those polynomials whose degrees possess n/qlq2 as divisors have been excluded twice, so that we have to re-include them, and so on. D Theorem 9.2. The total number of irreducible polynomials of degree n (modp), is equal to

~ (pn _

Lpn/q, ql

+

L pn/Q,q2 - Lpn/Q,Q2Q3

+ ... ).

Qt,Q2

Here the sums are over the distinct prime divisors qi of n. Proof The degree of the polynomial in Theorem 9.1 is

N = pn - L pn/Q, +

... ,

(1)

Q,

and each of its factor has degree n, so that the result follows.

D

Let n= qlt' ... q~s, where qi are the distinct prime divisors of n. Now

Therefore N> 0, so that we have: Theorem 9.3. There always exists an irreducible polynomial ofdegree n (modp).

D

4.10 Primitive Roots The content of this section is very similar to §3.8, and we shall therefore omit the details. Let (fix), q>(x)) = 1. Suppose that there exists a polynomial g(x) such that (g(x))m ~fix) (moddp, q>(x)). Then we call fix) an m-th residue moddp, q>(x). A polynomial fix) is, or is not, a quadratic residue according to whether (fix))t(P"-l)~ 1

(moddp, q>(x)),

or (fix))t(P"-l) ~ - 1 (moddp, q>(x)).

68

4. Properties of Polynomials

Definition. The least positive integer I satisfying (fix))'~ 1 (moddp, q>(x)) is called the order of fix). As before, it can be proved that I divides pn - 1, and that there are precisely q>(l) polynomials having order I. There are therefore q>(pn - 1) polynomials with order pn _ 1, and these polynomials are called the primitive roots (moddp, q>(x)). Iffix) is a primitive root, then (fix)) v, v = 1,2, ... ,pn - I represent all the non-zero incongruent polynomials, moddp, q>(x). It is not difficult to prove that the product nv (X - fv(x)), where!., runs over all the primitive roots, is equal to

n

x pn - 1 _

n

1

(X(pn_1)/q -

(X(pn_1)/qq, -

1)

1)

(1)

q

where qi runs over all the distinct prime divisors of pn - 1. Exercise. Prove that the product of all the non-zero incongruent polynomials is congruent to - I (moddp, q>(x)).

4.11 Summary We may summarize the discussions of this chapter in the language of modern algebra or abstract algebra. We have a set of objects which we denote by R. The number of objects in R may be finite or infinite. 1. If we can define the operations of addition and subtraction in R and that these operations are closed in R, then we call R an integral modulus. For example: The set of even integers forms an integral modulus; the set of polynomials with even integer coefficients forms an integral modulus. An integral modulus is also known as an Abelian group. 2. If we can define the operations of addition, subtraction and multiplication which are closed in R, then we call R a ring. For example: The set of integers forms a ring; the set of integer coefficients polynomials forms a ring. 3. By an ideal E, we mean a subset of a ring R which satisfies the following conditions: i) If a,bEE, then a - bEE; ii) If aEE and rER, then arEE. For example: The subset of even integers forms an ideal in the ring of integers. In the ring of integer coefficient polynomials, we may form the ideal of polynomials having the formfix)(x 2 + 1) + 2g(x)x, wherefand g run over all integer coefficient polynomials. 4. If in R we can define the operations of addition, subtraction, multiplication and division (except by 0), and that these operations are closed in R, then we call R a field.

4.11 Summary

69

For example: The set of rational numbers forms a field. The residue classes modulo a fixed irreducible polynomial forms a field, which is known as an algebraic extension field in modern algebra. Next, take a prime number p and an irreducible polynomial qJ(x) of degree n. The residue classes with respect to the double modulus p and qJ(x) forms a field with pn elements. Students who master the various concrete examples discussed in this chapter will find it easier to learn the abstract concepts of modern algebra.

Chapter 5. The Distribution of Prime Numbers

In this chapter we give some basic results concerning the distribution of prime numbers. The reader will only require some knowledge of the calculus - this chapter is a first introduction to analytic number theory and we shall omit all the deeper investigations.

5.1 Order of Infinity In the discussion of the distribution of prime numbers we must understand the notion of the comparison of the order of growth between two functions. We often use the symbols .

«,

0,

0,

the meanings of which we shall now give. Let n be a positive integer which tends to infinity (or x a continuous variable which tends to infinity). Let
IfI ~ A
f« If f

-

Also f

g

=

<po

«
o(
lim f(n)
=

0 and 1 respectively

n"'co

lim f(x) = 0 and 1 respectivelY).
x'" co

71

5.2 The Logarithm Function

We have the following examples: sin x « 1,

x

1

1

x+-«x«x+-, x x

1

+ - = O(X2),

x

X

x

+ sinx =

x

+ sinx '" x,

+ 0(1).

Naturally "x tending to infinity" may be replaced by "x tending to /" where / is a finite number. For example, as x -+ 0, we have x2

=

O(x),

sin x'" x,

l+x",l.

HOVl:'ever, unless otherwise stated, we shall assume that the variable is tending to infinity. It is easy to verify the following properties: (i) ({) « ({); (ii) iff « ({) and ({) « 1/1, then f« 1/1; (iii) if f« ({) and g« 1/1, then f + g « ({) + 1/1 and fg «({)1/1. The properties (ii) and (iii) still hold if we replace « by o( ). We also have (iv) ({) '" ({); (v) if 1/1 '" ({), then ({) '" 1/1; (vi) if ({) '" 1/1, and 1/1 '" X, then ({) '" X; (vii) if 1/1 '" ({) and 1/1 1 '" ({) b then 1/11/1 1 '" (()({) l'

5.2 The Logarithm Function The logarithm function log x frequently enters in the discussion of the distribution of prime numbers. We assume the reader already knows the definition oflogx and we shall recall the following simple properties. Since

x" eX =I+x+"'+-+ n!

X"7,1

(n+1)!

+"',

it follows that for positive x and for all n

Since, for any fixed n, the right-hand side tends to infinity as x -+ 00, it follows that ~ grows faster than any fixed power of x. We can therefore write x" = o(e X ). If IX is positive, then x!1. = 0(x[!1.1+ 1) = o(e X ). Since log x is the inverse function of eX, on substituting logy for x in the above, we see that (logyy = o(y), or

In other words log x grows slower than any fixed positive power of x. It is easy to see that log log x is even smaller than log x.

72

5. The Distribution of Prime Numbers

Theorem 2.1. x

1

n~ 1

n

I - ~ logx.

Proof The result follows at once from x

x

dt log x = f - ~ I

x

t

n~ 1

- ~ 1 + fdt - = 1 + log x. 1

n

0

t

Theorem 2.2. Le t

Then

.

x

hx~--.

logx

Proof We have

Ii x (li x)' lim - - = lim -,----:-x-+ 00

10: x

x-+

00

Co: x)'

log x

= lim----logx

=1.

log2 x

0

5.3 Introduction The distribution of prime numbers is the most interesting branch of number theory. The various conjectures and theorems are mostly the result of empirical observations. We now consider several problems and the ancient conjectures associated with them. (i) Let n(x) denote the number of primes not exceeding x. Then we have the following table which suggests: 1) There are infinitely many primes; that is n(x) -+ 00. 2) However, there are relatively few primes comparing with all the integers. That is, almost all numbers are not primes in the sense that

73

5.3 Introduction

X

x

n(x)

1000 10000 50000 100000 500000 1000000 2000000 5000000 10000000 20000000 90000000 100000000 1000000000

168 1229 5133 9592 41538 78498 148933 348513 664579 1270607 5216954 5761455 50847478

Jix

logx 145 1086 4621 8686 38103 72382 137848 324149 620417 1 189676 4913 897 5428613 48254630

n(x)

178 1246 5167 9630 41606 78628 149055 348638 664918 1270905 5217810 5762209 50849235

--+

n(x)

n(x)

Jix

x

0.94 ... 0.98 ... 0.993 ... 0.996 ... 0.9983 ... 0.9983 ... 0.9991. .. 0.9996 ... 0.9994 ... 0.9997 ... 0.99983 ... 0.99986 ... 0.99996 ...

0.1680 0.1229 0.1026 0.0959 0.0830 0.0785 0.0745 0.0697 0.0665 0.0635 0.0580 0.0576 0.0508

O.

X

3) The number of primes not exceeding x is asymptotically Ii x; that is .

X

n(x) '" II x '" - - .

logx

We note that 3) implies I) and 2). 4) The best approximation to n(x) is Ii x. 5) n(x) < Ii x. In this chapter our deepest result is Chebyshev's theorem which states that

x x - - « n(x)« - - . logx logx This result implies 1) and 2). The statement 3) is the famous prime number theorem which we shall prove in Chapter 9. The problem raised in 4) belongs to a difficult branch of analytic number theory and its discussion is outside the scope of this book. Finally, despite the convincing evidence from the table, 5) is actually false; this was proved by Littlewood. (ii) We know that

5,13,17,29, ... ,10006721, are all primes congruent 1 mod 4. A natural question is whether there are infinitely many such primes. Associated with this problem Dirichlet's theorem gives the following general answer: Let a, b be coprime integers. Then there are infinitely many primes of the form an + b. In this chapter we shall only discuss particular examples of this theorem, the proof of which is given in Chapter 9. (iii) We have 6 = 3 + 3,

8 = 3 + 5,

10 = 5 + 5,

12 = 5 + 7,

74

5. The Distribution of Prime Numbers

+ 7, 22 = 3 + 19, 14

=

7

16=3+13,

18

=

5 + 13,

20

=

7

+ 13,

24 = 5 + 19,

This suggests the following: Every even integer greater than 4 must be the sum of two odd prime numbers. This is the famous Goldbach's problem. If this problem is settled to be true, then we can deduce that every odd integer greater than 7 must be the sum of three odd primes. This is because if n is an odd integer greater than 7, then n - 3 is an even integer greater than 4 so that n - 3 = PI + P2 or n = 3 + PI + P2' The unsolved Goldbach's problem is extremely difficult. I. M. Vinogradov proved that every sufficiently large. odd integer is the sum of three primes. The author proved that "almost all" even numbers are the sum of two primes. V. Brun proved that every sufficiently large even integer is the sum of two numbers each having at most 9 prime factors. (See Notes.) (iv) We also note that 3,5;5,7; 11,13; 17,19;29,31; ... ; 10016957, 10016959; ... ; 10 9 + 7, 109 + 9; ... are all pairs of primes having difference 2; we call such pairs prime twins. More specifically we know that there are 1224 pairs less than 100,000 and 8164 pairs less than 1,000,000. At present (1957) the largest pair known to us is 1000000009649, 1000000009651. From the evidence here it is natural to conjecture that there are infinitely many pairs of prime twins. This too is a famous unsolved problem. (See Notes.) In the theory of numbers we shall always have more unsolved problems than solved ones. For example we also have 5,7,11; 11,13,17; 17,19,23; ... ;101,103,107; ... ; 10014491, 10014493, 10041497; ... all primes. It is conjectured that there are infinitely many primes P such that P + 2, P + 6 are also primes. Advancing even further: (v) We can verify that n 2 - n + 17 is always prime when 0 ::;;; n ::;;; 16, and that 2 n - n + 41 is always prime when 0 ::;;; n ::;;; 40. We now suggest the following interesting problem: Let N be any given number. Can we always find a prime P such that

is always prime when 0 ::;;; n ::;;; N? This too is an unsolved problem and, in the author's view, it is even more difficult than (iii) and (iv). If this problem is solved affirmatively, then (iv) can also be settled. Let us see why. In order for the polynomial n 2 - n + P to (successively) take prime values, n must be restricted to

75

5.4 The Number of Primes is Infinite

the integers from 0 to P - 1. We now construct a sequence of polynomials - n + Pi with the following property: When 0::;;; n ::;;; Pi _ b the number - n + Pi is always prime. We note that if (v) is solved, then this construction is certainly possible. Now taking n = I and 2 will give Ph Pi + 2 both primes, and taking n = 1,2,3 will give Pi,Pi + 2,Pi + 6 all primes. This shows that (iv) follows as a consequence of (v). (vi) Another difficult unsolved problem is whether there are infinitely many primes of the form n 2 + 1. We know that n2 n2

2,5,17,37, ... ,65537, ... are all primes of this form and it is conjectured that there are infinitely many such primes. (See Notes.) (vii) Let Pn denote the n-th prime. We may ask about the distribution of the values Pn - Pn-l' From (iv) we see that Pn - Pn-l may be as small as 2, but what about its maximum value - that is, an order estimate for Pn - Pn _ 1 as n --+ 00. (viii) The so-called Bertrand's postulate states that there always exists a prime in any interval from n to 2n. This is comparatively easy and we shall prove it in §7. A more delicate conjecture is that "there always exists a prime in any interval from n2 to (n + 1)2." This is a difficult unsolved problem.

5.4 The Number of Primes is Infinite Theorem 4.1. The number of primes is infinite; that is n(x)

--+ 00

as x

--+ 00.

Proof Let 2,3, ... ,p be all the primes not exceeding P and let q=2·3·····p+1.

Then q is not a mUltiple of2, 3, ... ,p and hence either q is prime or q is divisible by a prime between P and q. Therefore there always exists a prime greater than p, and so it follows that the number of primes is not finite. 0 This method can be generalized to give the following: Theorem 4.2. Let f(x) be any polynomial with integer coefficients. Then the numbers

f(l), f(2), f(3), ... contain infinitely many distinct prime divisors. Proof Let n~l.

If an = 0, then our sequence of numbers contains all the primes as divisors. We assume therefore that an i= O.

76

5. The Distribution of Prime Numbers

Suppose that the sequence of numbers has only finitely many prime divisors PI, P2,· .. , Pv· We considerf(p1 .. 'PvanY), a polynomial iny with all the coefficients a multiple of an' Let

where g(y) = 1 + A 1 y

+ A2y2 + ... + Anyn

is a polynomial with integer coefficients such that PI>' .. ,Pv divide AI> A 2, ... , An. If there exists an integer Yo such that g(yo) ¥- ± 1, then g(yo) must contain a prime divisor distinct from PI> ... ,Pv, and so the theorem follows at once. Butg(y) = ± 1 has at most 2n solutions so that the theorem is proved. D A different method of proof of Theorem 4.1 was given by Euler. This method, which we give below, opens the door for analytic number theory.

Lp

Theorem 4.3. The series lip is divergent; here the summation is over all primes p. Therefore the number of primes is infinite.

We first prove: Theorem 4.4 (Euler's identity). Letf(n) be definedfor all positive integers n, andf(n) not identically zero. Suppose that f(nn')

= f(n)f(n')

whenever

(n, n')

= 1.

Then we have the following identity 00

L fen) = f1 (l + f(p) + f(p2) + ... ); n=l

p

the condition for the validity of this identity is either 00

L

(i)

converges

If(n)1

n=l

or

(ii)

f1 (l + If(p)1 + If(p2)1 + ... )

converges.

p

Moreover, if f(nn') = f(n)f(n') for all conditions, we have that

n, n', then, subject to the same convergence 1

00

L fen) = f11 - f( P)' p

n= 1

Proof We have, for all n,f(l)f(n) Therefore f( 1) = 1.

=

f(n) , and there exists n such that fen) ¥-

o.

77

5.4 The Number of Primes is Infinite

I) Suppose that the series 00

L If(n)1

(I)

n= 1

converges to the sum S. Now consider

P(x)

=

TI (1 + f(p) + f(p2) + .. '). p~x

For any p, the series L:'= 1 If(pn)1 is part of the series (1) so that it must also converge. This means that P(x) is a finite product of absolutely convergent series. Therefore

P(x) = L'f(n) where the summation is over all integers n having prime factors ::;:; x. Let 00

L f(n)

S=

n=1

so that

L

IS - P(x)l::;:;

If(n)l·

n>x

When x --+ 00, IS - P(x)I--+ 0 so that P(x) Using this result on If(n)1 we see that

--+

S.

TI (1 + If(p)1 + If(p2)1 + ... ) p

converges to S. 2) Suppose that

TI (I + If(p)1 + If(p2)1 + ... ) p

converges to P. Then

P(x)

=

TI (I + If(p)1 + If(p2)1 + ... ) p~x

= L' If(n)1

~

L

If(n)l·

n~x

Therefore 00

L

If(n)1

n=1

converges. From our result in I) we see that the first part of the theorem is proved. The last part follows from I

+ f(p) + f(p2) + ... = I + f(p) + (f(p»2 + ... I I - f(p)

D

78

5. The Distribution of Prime Numbers

Proof of Theorem 4.3. We putf(n) = l/n in the above theorem. If I l/p converges, then we deduce that

11

and

( P1)-1 1-

converge, and we infer from the theorem that 00

1

I-n

n= 1

also converges, which is impossible. Therefore Theorem 4.3 is proved.

D

From 0 < 1 - -; < 1 we deduce: Theorem 4.5.

11(1 - -;) diverges to zero.

D

Exercise 1. Prove that there are infinitely many primes of the form 6n - 1. Exercise 2. Prove that there are infinitely many primes of the form 4n - 1. Exercise 3. Prove that

00

(Note that

I

n=l

1 2"

n

n2

= -.) 6

5.5 Almost all Integers are Composite Theorem 5.1. lim n(n) 00 n

=

o.

n-+

That is, the ratio of the number ofprimes in 1,2, ... , nand n tends to zero as n tends to infinity, or almost all integers are composite. Proof We prove the slightly more general result

lim n(x) x--'oo

=

0,

X

where x tends to infinity through all real numbers. We first observe the following useful and simple fact. The number of integers not exceeding x that are divisible by ais [x/a]. Here [~] denotes the integer part of~.

79

5.6 Chebyshev's Theorem

Denote by w(x, r) the number of positive integers not exceeding x and not divisible by the first r primes 2,3,5, ... ,Pro Then, from Theorem 1.7.1 we have

I

w(x,r)=[x]-

"'i"'r

[Pi-x] +

[- x ]

I

_00'

"'i<j"'r PiPj (it is not difficult to give a direct proof of this). Clearly then 1

n(x)

~

1

W(X, r)

+ r,

so that x x n(x)<x-I-+I-- ... +r+2r Pi PiPj

=

x.n (1 - ~) +

<x

,~1

p,

i~ 1

Pi

n(1 - ~) n(1 -~)

From Theorem 4.5 we know that, as r

r

+

2 r

+ 2r + 1.

--+ 00,

--+

Pi

i~1

O.

Let e > O. We can take r = r(e) so that

and therefore, for sufficiently large x, n(x) < eX.

The theorem is proved.

0

5.6 Chebyshev's Theorem The theorem in this section is an important result in elementary number theory and one should try to give the most elementary argument to prove it. Theorem 6.1. When n

~

2 we have

~ ~ n(n)H(n) < 6 8""

n

'

where .

H(n) =

n

1

I -.

v~2 V

That is n(n) is about the same as the reciprocal of the average of (t, t, t, ... ,!).

80

5. The Distribution of Prime Numbers

We shall require the following two lemmas: ~

Lemma 1. When k

0 we have

Proof When x > 9 we have, by considering even and odd numbers, that n(x) Also n(2) = 1 = 2°,

n(8)

~

x/2.

= 4 = 22. 0

Lemma 2. When 1 > 0 we have

H(2 1) =

(1 + -1) + (1- + -1+ -1+ -1) + ... + -2'1"" (1- + -1) + (41+ 41+ 41+ 41) +... + ( 1 + . . . + 1) + 2!1 -

2

3

4

5

6

~

7

2' -

2

2

2' -

1

~ I.

1

o

Proof of Theorem 6.1. We first prove that

n

pl(2n) =

n
n

(2,n):1

n

pro

(1)

n.n. pr~2n<pr+l

(i) Any prime in the interval from n to 2n must divide (2n)! but not n!, so that the left hand side of the formula holds.

(ii) The power of p in

C:)

is

since each term in the sum is at most 1. This proves the right hand side of the formula (1). From (1) we now have n 1t (2n)-1t(n)

<

n

n
p

~ (2n) ~ n

n

pr~2n<pr+l

pr

~ (2n)1t(2n),

n

~

1.

(2)

81

5.6 Chebyshev's Theorem

Since (

2n) n

= 2n(2n - I)·· ·(n + I) n(n - 1)···1 =2(2+_1) ... ( 2 +V_ ) n-I n-v

•••

(2+~)~2n I

and

(~n)::s:; (I + 1)2n = 22n, we deduce from (2) that

n ~ l.

(3)

Let n = 2k, k = 0, 1,2, ... , so that we have k~O,

or (4)

From Lemma I we have k~O.

Taking k

= 0, I, . .. , k and adding the corresponding results we have (k

+ l)n(2k+1) <

3(20

+ 21 + ... + 2k) <

3·2 k+1,

k~O.

(5)

From (4) and (5) we have k~O.

(6)

Let n be an integer greater than I and choose k so that k~O.

From Lemma 2 we have 2k + 2 2k+ 1 n k 2 n(n) ::s:; n(2 + ) < 3 k + 2 ::s:; 6 H(2k+2) ::s:; 6 H(n)'

(7)

and I 2k+l I 2k+2 n(n) >-: n(2k+1) >-: _ _ _ - _ ..,....,.,..._ _ 7 72 k + 1 - 8 t(k + I)

1 2k + 2

>-: -

I

n

>-: - - -

78 H(2 k+1) 78 H(n)·

(8)

82

5. The Distribution of Prime Numbers

This holds for all n

~

2. Therefore I

H(n)

8

n

0

-~n(n)--<6.

Theorem 6.2. 1

n(n)

8

n

-~--~

12,

logn

Proof When n

~

2, we have n

n log - = 2

n

fdt- < -1 + -1 + ... + -I < fdt- = log n. t

2

n

3

t

2

When n ~ 4, we have

Also

t log 3 ~ t + t, so that the required result follows from the previous theorem.

0

We note, of course, that Theorem 4.1 and Theorem 5.1 are consequences of this theorem.

5.7 Bertrand's Postulate Bertrand's postulate was first proved by Chebyshev. Theorem 7.1. Given any real x

~

1, there exists a prime in the interval x to 2x.

Proof I) We begin by giving a good estimate for the binomial coefficient ( 2n) = (2n)! , n n!n! namely, for n

~

5, we have that

~22n < (2n) < ~22n. 2n

n

4

The left hand side inequality follows from

2n) (2n) ( n

2 3 4 5

2n - I 2n - I 2n 2n

=1"1"2'2" ... '~'~'~'~>22n,

(1)

83

5.7 Bertrand's Postulate

and we shall use induction for the right hand side inequality in (1). When n have

= 5, we

1 210. ( 2n) n = 252 <,256 = 4' Since

1)) = (2n)!(2n + 1)(2n + 2) < 4 (2n) ,

( 2(n + n+l

(n!f(n+ l)(n+ I)

n

the inductive argument is complete. 2) Let b ~ 10. We denote by {~} the least integer

We then have a1

~

a2

~

...

~

ak

~

~ ~,

and we set

.. " and

b b ak < 2k + 1 = 2 2k + 1 + 1 ~ 2ak + 1 + 1. Since both the outsides are integers we have (2) Let m be the greatest integer such that am am < 10. Since 2a1 ~ b, the m intervals

covers the whole interval 10 < 1]

~

TI

~

5, so that am + 1 < 5, and hence, by (2),

b. Therefore

TI

p ~

TI

p < (2n) < 22 (n-l), n

p

TI

p" .

TI

p.

From n
we have

TI

p

~

22(a l -1+a 2 -1+"'+a m -1)

10
3) We already proved earlier that the power ofpin

e:)

(3) does not exceed r, where

r is the greatest integer satisfying pr ~ 2n. It follows that if p > .. (2n) not dIVIde n .

.j5z, then p2 does

84

5. The Distribution of Prime Numbers

We further observe that, when n

~

3, the primes p satisfying in < p ::;:; n cannot

divide Cnn) . This is because 3p > 2n, so that only p and 2p, and not other mUltiples of p, may occur among the divisors of (2n)!, whereas p2 clearly is a divisor of (n !)2. Therefore such a prime p cannot divide Cnn) . (This is the most important point in this proof.) Collecting our results we have

(~n)::;:; p!3~pr ~~~~fnP n
n

(2n)

n

p

fo ~ 10),

From (1) and (3) we see that, for n ~ 50 (so that

n 121" n

22n < (2n)~~+1

< (2n)~~ +

n

p

fo < p :s::; in

p.

p

n < p ~ 2n

p.

(4)

n
If there is no prime number between nand 2n, then

or (5)

But this is clearly impossible ifn is sufficiently large. We now determine an explicit bound for the validity of this inequality. We use n ::;:; 2"-1 (this can be proved by induction) to give (6)

From (5) we have (using n ~ 50) that

that is (2n)! < 20 or n < t· 20 3 = 4000. Thus (5) can hold only if n < 4000 and we have therefore proved that, if n ~ 4000, there is always a prime p satisfying n
2,3,5,7,13,23,43,83,163,317,631,1259,2503,4001

(7)

is a chain of prime numbers, each one being smaller than twice its predecessor. Now, given any n (1 ::;:; n < 4000) we can select the smallest prime p in (7) which

85

5.8 Estimation of a Sum by an Integral

exceeds n, and we denote by p' its predecessor. Then we have p'

~

n
~

The proof of the theorem is complete.

2p'

~

2n.

D

Theorem 7.2. There exist two positive constants

n < n(2n) - n(n) < logn

IX--

IX

and p such that

n logn

p--,

n ~ 2.

Proof The right hand side inequality in the theorem follows at once from Theorem 6.2. We now prove the remaining inequality. The theorem is trivial if n < 4000. Suppose then that n ~ 4000. From (4) and (6) we have that

>

•

21\2n - 19(2n)')

~ 2in(1-19/20) =

2io n •

From

TI

p <

(2n )"(2n) - ,,(n),

n
we have log2 n n(2n) - n(n) > -_. - - , 30 log2n and the theorem is proved.

D

Note: Although Theorem 7.1 settles Bertrand's postulate, it is not a very sharp result. Deep analytic methods can be used to give much better results concerning the gaps between successive primes, but these are beyond the scope of this book. Exercise. Use differential calculus to determine the bound for the validity of (5).

5.8 Estimation of a Sum by an Integral Theorem 8.1. Letf(x) be increasing and non-negative for x

have ~

la.,~.,/(n) -

ff(X)dxl a

~f(e).

~

a. Then,for

e~ a, we

86

5. The Distribution of Prime Numbers

Proof We set b

=

[n Then i+ 1

b

f f(x) dx

= :t~

f f(x) dx

a

{

~ bi1f(i)

~ ~i:

f(i

+ 1),

i;:::;:a

or b

f(a)

+ ... + f(b

- 1)

~ ff(X)dX ~f(a + 1) + ... + f(b); a

also ~

o ~ ff(X)dX ~f(e), b

and so the theorem follows. Example 1. Let A ~ O,f(x)

0

= x". Then

II

a<Sn<S~

n" -

e+l - a"+l

A+ 1

I

~

e.

From Example 1, we have, for A ~ 0, <

I

l<Sn<S~

n"

e+ 1 = --

+ O(e).

(1)

A+ 1 _

This implies that

Example 2. Letf(x)

= log x, e ~ 1 and

T(e)

= In<s~logn. Then we have

~

IT(e) - flOgXdxl

~ loge,

or IT(e) - eloge

+e-

11

~

(2)

loge·

In particular, if e is an integer n, then nlogn - n

+ 1 -logn ~ logn! ~ nlogn -

n

+ 1 + logn, I

87

5.8 Estimation of a Sum by an Integral

or (3) Exercise 1. Let ~ be an integer. Determine one further dominating term in (1); that is, find c so that the following holds for 2 ~ 1 : ~H1

I

nA = - 1";n";~ 2+1

+ ce + O(e- 1 ).

Exercise 2. Use Theorem 8.1 to study the sum

I

log10gn.

Concerning decreasing functions we have: ~

Theorem 8.2. Let f(x) be decreasing and non-negative for x

a. Then the limit

N

;~~ C~/(n) - f f(x) dX) = a

(4)

a

exists,andthatO::;;; a ::;;;f(a). Moreover, iff(x) have,

--+

Oasx--+

00, thenfor~ ~

a

+ 1, we

~

la,,;~,,;/(n) -

f f(v) dv -

al ::;;;f(~ -

1).

a

Proof Let ~

g(~) = a~~~/(n) -

ff(X)dX. a

Then n+1

g(n) - g(n

+ 1) =

-

f(n

+ 1) +

f

f(x)dx

n

~

- f(n

+ 1) + f(n + 1) = O.

Also n+1

g(N)

=

:t~ (f(n) -

f

f(x) dX)

+ f(N)

N-1

~

I

n=a

(f(n) - f(n))

+ f(N) = f(N)

~ 0,

(5)

88

5. The Distribution of Prime Numbers

so that g(n) is a decreasing function, and that

o ~ g(n) ~ g(a) = f(a). Therefore g(n) has a limit which we denote by oc, so that 0 Suppose now thatf(x) --+ 0 as x --+ 00. Then ~

g(~) -

oc

=

a~~~/(n) -

~

oc

~f(a).

N

;~ ctf(n) -

ff(X)dX a

f f(X)dX) a

[~l

~

N

= n~/(n) - f f(x)dx - f f(x)dx -

;~~ C~/(n) -

a

[~l

a ~

= - ff(X) dx - lim (

f f(X)dX)

N

I

f(n) - ff(X) dX)

n=[~l+ 1

N ... "" [~l

[~l

~

n

I

= - ff(X) dx + lim

f (f(x) - f(n» dx

N ... oo n=[~l+ 1 ~

n-l n

N

L

~ lim

f (f(n - I) - f(n»dx =

f([~J) ~f(~ -

I)

N ... oo n=[~l+l

n-l ~

~-

f f(x) dx

~ - (~ - [~J)f([~J) ~ - f(~ -

I),

[~l

and so the theorem is proved.

0

Example 3. We take a = I, f(x) = I/x. Then the number oc is known as Euler's constant, and is usually denoted by y. Therefore 0 ~ y ~ I, and

1

L ~ = log ~ + y + 0 (~) . ~

~n~~

Example 4. Let 0 < u # I,/(x) = x-". Then there is a constant oc depends on a and u, such that when a ~ 1 we have

1 ~l-" I ~L~ ~ -n" 1-

a 1 -"

-

a

u

n

I

I -a ~ . "" (~ - I)"

From this we deduce the following: If u > I, then the series 00

1

L--;; n

n= 1

(6)

= oc(a, u) which (7)

89

5.9 Consequences of Chebyshev's Theorem

converges, and when e;?; 1 we have

J~ ~a = (u - :)ea-1 + O(;a).

(8)

The four results (1), (3), (6), (8) are used very frequently and the reader is advised to remember them. Exercise 1. Prove that, for e ;?; 2,

I

l';;;n';;;~

log n 1 e). -_=-10g2e+Cl+ -0 (lOg

n

e

2

Exercise 2. Prove that, for e ;?; 2,

I

_1_ = logloge + C2 +

Hn';;;~ nlogn

0(_1_). eloge

5.9 Consequences of Chebyshev's Theorem The letters Cl> C2," . used in this section represent absolute constants. Theorem 9.1. There exists a constant c 1 such that, for e ;?; 1,

I logp -logel < Cl' IP';;;'; P Here Ip';;;~ represents the summation of all primes p not exceeding

e.

Proof 1) We assume first that e = x is an integer. From Theorem 1.11.1, we have T(x) = logx! = log

n p[;]+[f,]+ ... = p';;;x

I ([::] + [~] + p';;;x

P

.. . )lOgP.

P

From x p

p

p

x] + ... ~ x + p2 x + ... ~ x + p(p x_ 1) , 1 < [x] ji + [ p2

we have x logp I -- I p';;;x

P

logp < T(x) ~ x

p';;;x

(lOgp

I -

p';;;x

P

+I

From Theorem 6.2, we have

I p~x

logp ~ logx . n(x) ~ C2 X •

p';;;x

logp ) p(p - 1)

.

(1)

90

5. The Distribution of Prime Numbers

We also have "Iogn L... 2 Hn""'x+l (n - I)

"Iogp

1... - - - ~

p"",xp(p -

I)

+ I)

;, log(n

~ L...

n

n=1

2

_ -

C3,

so that we now have, from (I), that logp I~ IT(x) - x L: -p

C4 X •

p""'x

From Example 8.2 we have IT(x) - xlogxl < logp - xlogx I IT(x) Ix L: -~

p""'x

logp I+ IT(x) L: --

x

p

But

CsX.

p""'x

p

so that logp -Iogx I< I L: -p

C6'

p""'x

2) Let

~

be real. Then

L:

logp

P""'~

P

=

L:

logp.

p""'[~l

P

From our earlier result we have

L: -logp -Iog[e] I< I pq P

C6'

But ~

Ilog[~J -log~1 =

~

f

d(logt) =

~

f~t ~ f

dt

[~l

[~l

so that

-IOg~I
The theorem is proved.

D

Theorem 9.2. There exists a constant

C7

such that, for

L: ~ = loglog~ + +

p"",~p

Proof Let

C7

~ ;?;

0(_1_). log~

2,

~ I,

xlogx

I

91

5.9 Consequences of Chebyshev's Theorem

so that, by Theorem 9.1, S(n) = logn

+ rm

rn = 0(1).

Therefore

I

I

~

p~~ P

p~~

_ -

logp. _1_ = I S(n) - S(n - 1) P logp Hn~~ logn

"Iogn-Iog(n-I) L., 2~n~~ logn

+

" r n -rn -1_" L... - L.,1 2~n~~ logn

"

+ L.,2·

(2)

Now the function

-~)

IOg(1

f(x) = - - - - -

x~2,

logx

is decreasing, andf(x)

0 as x

-+

-+ 00.

Therefore, by Theorem 8.2, we have

Since

I

f(x) = - xlogx

+0

(I) x 2 10gx

"

the integral

2

converges to

C9,

so that

~

f

I1 = ~ + xlogx 2

~

Cs

+

f

- log (I -

~) - ~ x

logx

x dx

+0

(_I) eloge

2

= logloge + C10 + 0(_1_), ,

elog e

(3)

92

5. The Distribution of Prime Numbers

where we have used

Next, from the convergence of the positive terms series

n~2 00

and

rn

(

1

I) + I)

logn -Iog(n

= 0(1) we deduce that the series

n~2 rn 00

converges to

Cll.

(I

I) +

logn -Iog(n

I)

Also

n~/nCo~n -lOge: + 1») oC~Jlo~n -lOge: + 1)1) =

=

oC~~ nlo~2 n) = oCo~e).

Therefore

L2 =

2.,~.,/nCo~n -lOge: + I») + oC:~e)

=

n~z'nCo~n -lOge: + I») - J/nCo~n -lOge: + I») + oCo~e)

=

Cll

+ oCo~e).

(4)

From (2), (3) and (4) we arrive at

L ~=

logloge

+ CI0 + Cll + 0(-1-1_)

=

logloge

+ C7 +

P"~P

The theorem is proved.

oge

0(_1_). loge

0

Theorem 9.3. There exists a constant

l}~

( I)

C12

such that, for

e~ 2,

(I)

C 1 2+ 0 - 1-- - p - log e log2 e .

93

5.9 Consequences of Chebyshev's Theorem

Proof Since

I

p>~

(lOg (I -

~) + P~)

0 (

=

P

I ~)

p>~P

0

=

(I ~) n>~n

=

0

(~), ~

it follows from the previous theorem that log

n (I -~) I P =

p";~

=

-loglog~ I

p>~

~) =

log (I -

p";~

C7

+

-

P

0(_1_) log~

I P~ + p";~ I [lOg (I - P~) + P~J

p";~

+I

(IOg(1

p>2

-~) +~) P P

-~) +~) = -loglog~ +

(IOg(1

C13

P

P

+0(_1_), log~

where C13

= -

C7

+ I

p>2

(lOg (1

-~) + ~). P P

Therefore

I

p";~

( P1) 1--

(1) = __

eCl3 'c o ( log~ 1)

=e-logloge+cl3+o log~

log ~

= ~(1 + o log~

(_1_)) log ~

(C1 2

= eC[3),

where we have used

eOCo~~)= I + The theorem is proved.

0(_1_). log~

D

Theorems 9.2 and 9.3 are quantitative elaborations of Theorems 4.3 and 4.5. Exercise 1. Let Pn denote the n-th prime. Prove that there are constants that n

Exercise 2. Prove that there exists a positive constant ({)(n) >

cn

loglogn

,

Exercise 3. Prove that the infinite series 1

~ p(log logp)h

n ~ 3.

~

C

2.

such that

Cl, C2

such

94

5. The Distribution of Prime Numbers

converges or diverges according to whether h > 1 or h summation over all the prime numbers.

~

1. Here

Lp represents the

5.10 The Number of Prime Factors of n Let n be a positive integer. We denote by w(n) the number of distinct prime factors 'Of n and by Q(n) the total number of prime factors of n. That is, if n = p~1 ... p~', then Q(n)

w(n) = s,

If n is a prime, then w(n) of 2, then

= Q(n)

= at + ... + as.

(1)

= 1; but as n tends to infinity through power.s

Q(n)

logn log2

= - - --+

00;

and if n = PtP2 ... Ps is the product of the first s primes, then as n --+ 00, = s --+ 00. Thus the behaviours of w(n) and Q(n) are rather irregular and there is certainly no asymptotic formula for them. However, we do have the following: w(n)

Theorem 10.1. There are positive constants

L w(n)

:;=

Ct, C2

xloglogx

such that

+ Ct + o(x),

(2)

n:::=;x

L Q(n) = xloglogx +

C2

+ o(x).

(3)

n:.%.x

Proof 1) We have

L w(n) = L L 1 = L [~J = L ~ + O(n(x»

P p.sx P and so (2) follows from Theorem 9.2 and Theorem 6.2. 2) We have n.sx

n.sx pin

p.sx

and, by Theorem 6.2, logx

[ IOgX]

P log2 .sx

Therefore

L n:::=;x

Q(n)

=

x

L w(n) + L m + o(x). n:S;x

logx

r=

1 ~ - - L 1= - n ( y x) = o(x). log2 p2.sx log2

pm:s;x m~2

P

95

5.10 The Number of Prime Factors of n

But the series

~"1_,,(1+1+ ... )_,,

m'-:2

'7 pm - '7

p2

p3

-

'7 p(p 1-

-c 1) -

converges, so that

L

Q(n) =

n:::;:;:x

L w(n) + x(c + 0(1)) + o(x) =

x10g10gx

+ C2X + o(x). 0

n:::=;x

Theorem 10.2 (Hardy-Ramanujan). Let e > 0, and letf(n) denote either w(n) or Q(n). Then the number of positive integers n

~

x satisfying

If(n) - 10glognl > (loglogn}!-+£ is o(x), as x

(4)

~ 00.

Proof(Turan). Since 10glogx - 1 < 10glogn ~ 10glogx when xl/e < n ~ x, and the number of positive integers n ~ xl/e is [xl/e] = o(x), it suffices to prove that the number of positive integers n ~ x satisfying If(n) -loglogxl > (loglogx)t+£

(5)

is o(x) as x ~ 00. Next, from Q(n) ;::: w(n), and by (2) and (3)

L (Q(n) -

w(n))

= O(x)

n~x

so that the number of positive integers n ~ x satisfying Q(n) - w(n) > (log 10gx)t is

o ((lOg l:g x)t )

=

o(x) ..

Therefore we need only consider the casef(n) = w(n). We consider a pair p, q of distinct prime divisors of n (p, q and q,p are treated as two different pairs). Each p may take w(n) values and for each fixed p, q may take w(n) - 1 values. Therefore we have w(n)(w(n) -

1) =

L 1 = L 1 - L 1. pqln p¢q

Summing over n

=

pqln

p21n

1,2, ... , [x] we have (6)

Since

96

5. The Distribution of Prime Numbers

and

L [~J = x L ~ + O(x), pq pq

pq';'x

pq';'x

it follows from (2) and (6) that I

L w 2(n) = x L - + O(x log log x). n';'x

pq';'x

(7)

pq

Now

L ~)2 ~ L ~ ~ (L ~)2, ( P.;.J; P pq p pq';'x

and Lp';'~ lip = log log

p';'x

e+ 0(1), so that both the outsides in the above are

(loglogx

+ 0(1))2 = (loglogx)2 + O(loglogx).

It now follows from (7) that

L w 2(n) =

x(loglogx)2

+ O(x log log x),

(8)

n:::;:;:x

and so

L (w(n) -loglogx)2 = L w 2(n) -

2 log logx

L w(n) + [x](loglogx)2 n~x

n:::=;x

= x(loglogx)2 + O(xloglogx) - 210glogx(xloglogx + O(x)) + (x + 0(1))(loglogx)2 = O(x log log x). Given any (j > 0, if there are (jx positive integers n

~ x

(9)

such that (5) holds, then

L (w(n) -loglogx)2 ~ (jx(loglogX)1+2"

(10)

n~x

which contradicts with (9). Therefore the number of positive integers n that (5) holds is o(x), and the theorem is proved. D From this we see that w(n) '" log log n

and

Q(n) '" log log n

for almost all n.

5.11 A Prime Representing Function Theorem 11.1 (Miller). There exists a fixed number 2~o

then

[!Xn ]

is always prime.

= !Xl>""

!X

such that

if

~

x such

97

5.12 On Primes in an Arithmetic Progression

Proof We construct a sequence of primes {Pn} by induction: Take PI Theorem 7.1 there exists a prime Pn+ 1 satisfying

If Pn + 1 + 1 = 2Pn + 1, then Pn + 1 = 2Pn + 1 divisor 2'!-(Pn+ 1 ) - 1). Therefore

-

2Pn < Pn+ 1 < Pn+ 1

=

3. By

1 cannot be prime (because it has the

+ 1<

2Pn +1.

Using logarithm base 2 we define log(n) X = log(n - 1) (log X). Consider the sequences

Un = log(n) Pm Frompn < 10gPn+l < 10g(Pn+l + I) so that Un and Vn are monotonic sequences. Therefore there exists IX such that limn_ oo Un = IX, and Un < IX < Vn' That is, Pn < IXn < Pn + I and so [lXn] = Pn' 0 Exercise 1. Prove that there does not exist a non-constant polynomial f(n) with . integer coefficients which takes prime values for all n. Exercise 2. Let P(Xl' X2, ... ,Xk) be a polynomial with integer coefficients. Let f(n) = P(n, 2n, 3n, .. . , kn). Prove that if f(n) -+ 00, as n -+ 00, then f(n) represents infinitely many composite numbers.

5.12 On Primes in an Arithmetic Progression We saw in the exercises in §5 that there are infinitely many primes of the form 4n - I and 6n - I. This suggests the following: If a and b are coprime integers, then there are infinitely many primes of the form an + b. This is the famous Dirichlet's theorem which we shall prove in Chapter 9. Here we study the following special situation. We assume that a, b are positive and that b is fixed. We observe that if, given any a, there is always a prime of the form an + b (n > 0), then Dirichlet's theorem follows. For if there exists n such that an + b = PI (> b) is prime, and (replacing a by apr) there exists n such that apln + b = P2 (> PI) is prime, and so on, then there are infinitely many primes of the form an + b. Theorem 12.1. Let k > l. Then there are infinitely many primes of the form kn + l. From what we said earlier it suffices to prove that there always exists a prime of the form kn + l.

98

5. The Distribution of Prime Numbers

The roots of the equation Xk

1 are given by

=

a

= 0, 1, ... ,k - 1.

Let (a,n)= 1

where the product is over a reduced set of residues a mod n. Clearly we have Xk - 1 =

f1 Fn(x)

nlk where the product is over the divisors n of k, since each root on the left hand side must occur on the right hand side, and conversely without any repetition. Let

where Gk(x) is the least common multiple of the various polynomials xn._ 1 (n Ik, n < k), and its leading coefficient is 1. Therefore Gk(x) is an integer coefficient polynomial, and by Theorem 1.13.2 we see that Fk(X) is also an integer coefficient polynomial. If x is an integer not equal to ± 1, then

that is, Fk(X) and Gk(x) are non-zero integers. Lemma 1. Let n be a proper divisor of k. Then for all integers x -:f

± 1, we have

Proof Let xn - 1 = y, k = nd. Then Xk - 1

--= ~-l

(y

+ l)d y

1 =yd-l

== d (mody).

+

(d).,d-2 + ... + (d) y+d 1

y

2

0

Lemma 2. Let x be an integer not equal to Fk(X) and Gk(x) must be a divisor of k.

± 1. Then each common prime divisor of

Proof Let pl(Fk(x), Gk(x)). From pIGk(x)

=

f1 Fn(x)

nlk n
(nlk,n < k),

99

Notes

so that plxn -

1.

Again, from pIFk(x), we have

Therefore

pi

(xn -

1,:: =:)

and the required result follows from Lemma I.

0

Proof of Theorem 12.1. Let x = kyo Then

We can select y such that Fk(X) -:f ± I; this is possible because the equation Fk(x) = ± I has only finitely many solutions. There must be a prime divisor pin Fk(x), and, by Lemma 2, p does not divide Gk(x). In other words, for each proper divisor n of k, xn =1= I

(modp).

xk == 1

(modp).

(1)

But

We now prove that kip - I. Suppose otherwise. Then there are integers sand t such that (k,p - 1)

That is, corresponding to n xn

= (k,p -

=

sk

+ t(p -

1).

I), we have

== (Xk)'(xP~ i)' == 1

(modp),

which contradicts (1). Therefore p == 1 (mod k); that is there exists a prime of the form kn + 1. As we already observed, this proves the theorem. 0 Exercise. Prove that there are infinitely many primes of the form 8n

+ 5.

Hint: Consider q = 32 • 52 • 72 • • • • • p2 + 2 2 , and prove that each prime p of the form x 2 + y2 must be congruent I (mod 4).

Notes 5.1. There has been much progress towards the Goldbach problem in recent years using sieve methods. Perhaps the most exciting is the following result of J. R. Chen [19J, [20J.

5. The Distribution of Prime Numbers

100

Let n be a sufficiently large even integer and denote by Pn(l, 2) the number of primes P :::; n such that either n - P is a prime or a product of two primes. Then P n (1, 2)

> 0.67

~ TI TI plnp-2 p

>2

(1 - (P-I) 1 2)~2 . logn

p>2

It follows, of course, from this that every sufficiently large even integer is a sum of a

prime and an integer having at most two prime factors. The proof of Chen's theorem is given in the book "Sieve Methods" by H. Halberstam and H. E. Richert [28] where there is also a comprehensive bibliography. 5.2. Concerning the prime twins problem J. R. Chen [20] also proved that there are infinitely many primes P such that P + 2 is either a prime or has two prime factors. 5.3. H. Iwaniec (unpublished) has proved that there are infinitely many integers n such that n2 + I is either a prime or has two prime factors. 5.4. The principle of the "large sieve" was invented by Yu. Linnik and A. Renyi, and was substantially developed by K. F. Roth [50] and E. Bombieri [9] (see also the books by H. L. Montgomery [44] and E. Bombieri [10]). From his result Bombieri deduced the following theorem on the average value of n(x; k, I): Given any A > 0, there exists B = B(A) > 0 such that

I

I

lix = 0 max n(x;k,/) .....:--

k:S;x-5-/1 og B x (I, k)= 1

I


(x) log x -A-

.

(A. I. Vinogradov [59] independently proved a slightly weaker result). 5.5. There has also been much recent work on the distribution of dn = Pn + 1 - Pn where Pn is the n-th prime number. For example, H. L. Montgomery [44] proved that dn = O(Pl+e), where e is any positive number, with the implied constant depending on e; M. N. Huxley [31J improved this to dn = O(ptz+e) and very recently this has been improved to dn = O(pfo+e) by H. Halberstam, D. R. HeathBrown and H. E. Richert. We observe that dn = 2 whenever Pn, Pn+ 1 are prime twins. Concerning unconditional lower bounds for dn , E. Bombieri and H. Davenport [IIJ proved that E

d I . = inf inf _ n _ :::; - (2 + )3) = 0.46650 ... , n-+oo

10gPn

8

and this has been improved to E :::; ±(! + I) = 0.4463 ... (see [32]). 5.6. Besides the problems on the distribution of primes mentioned in the text there is also the problem of the least prime in an arithmetic progression, that is the estimate of the least prime P(k, I) in the arithmetic progression kn + 1 (n = 1,2, ... ) where k, 1are coprime positive integers. S. Chowla has conjectured that P(k, /) = O(kl +e) and Yu. Linnik was the first to prove that there is an absolute constant c such that P(k, I) = O(kC). Later C. T. Pan [45J gave a computable estimate for the value of c, and the present best estimate gives c < 15 which is due to J. R. Chen (unpublished).

Notes

101

5.7. In 1922 G. H. Hardy and J. E. Littlewood conjectured that every sufficiently large integer is the sum of two squares and a prime. This was proved by Yu. Linnik [40] using rather complicated methods. However there is now a simpler proof, based on E. Bombieri's mean value theorem for n(x; k, I), of this conjecture (see P. D. T. A. Elliot and H. Halberstam [23]). Many of the problems mentioned in these notes are also discussed in the author's book [30].

Chapter 6. Arithmetic Functions

6.1 Examples of Arithmetic Functions Definition 1. By an arithmetic functionj(n) we mean a function whose domain is the set of positive integers. Examples. Any sequence an is an arithmetic function. Specifically we can have n!, sin n, d(n) = Ldln 1 or r(n) where r(n) is the number of solutions to the equation n = x 2 + y2.

Definition 2. Letf(n) be an arithmetic function such that if (a, b) = 1, then j(a, b) = j(a)j(b).

(1)

Then we callf(n) a multiplicative function. If (1) holds regardless of the condition (a, b) = 1, then we say that j(n) is completely multiplicative. From this definition we see that if j(n) is a mUltiplicative function and if PI, ... ,Pr are distinct prime numbers, then

so thatj(n) is determined by the values it takes at the prime powers. Moreover, if j(n) is completely multiplicative, then

so thatj(n) is determined by the values it takes at the primes. It is clear that the product of two mUltiplicative functions is multiplicative and the product of two completely mUltiplicative functions is completely multiplicative. Example 1. The function LJ(n)

=

{~

if n = 1, if n # 1,

is completely multiplicative. Example 2. The function E;.(n)

= n A is completely multiplicative.

103

6.1 Examples of Arithmetic Functions

Example 3. The Mobius function is defined by:

if n = 1, if n is the product of r distinct primes, if n is divisible by a prime square. It is easy to see that

Jl(l) = 1, Jl(7)

= - 1,

Jl(2)

= - 1,

Jl(3)

= - 1,

Jl(S)

= 0,

Jl(9)

= 0,

Jl(4) Jl(10)

= 0,

Jl(5)

=- 1,

Jl(6)

= 1,

= 1, Jl(ll) = - 1, ....

Here Jl(n) is multiplicative, but not completely multiplicative. Example 4. The number of positive integers not exceeding n and coprime with n is

denoted by cp(n), and it is called Euler's function. This function is also mUltiplicative, but not completely multiplicative. Example 5. The divisor function d(n) = Ldln 1 is also multiplicative, but not completely multiplicative. More generally, the function O';.(n) = Ldln d). is mUltiplicative. We note that O'o(n) = d(n). Example 6. Von Mangoldt's function is defined by: A(n)

=

{lOgp,

if p is the only prime factor of n, otherwise.

0,

We have A(1)

= 0,

A(2)

= log2,

= log 3,

A(4)

= log 2,

A(5)

= log 5,

A(6)

= 0,

A(7)

= log 7, A(S) = log 2,

A(9)

= log 3,

A(10)

= 0, ...

A(3)

and we see that A(n) is not mUltiplicative. Example 7. We define

if n is the m-th power of a prime, otherwise. We have A 1 (1)

= 0,

Al(2)

= 1,

Al(3)

= 1,

A 1 (4)

A 1 (7)

= 1,

A 1 (S) =

t,

Al(9)

= t,

A 1 (10)

=

t,

Al(5)

= 1,

Al(6)

= 0,

= 0, ... ,

and that Al (n) is not multiplicative. Example S. Let p be a fixed prime number. If palin, we define Vp(n)

= p-a. This

104

6. Arithmetic Functions

function is completely multiplicative and it is not difficult to prove that Vp(n + m) ~ max(Vp(n), Vp(m». Example 9. Let r(n) denote the number of solutions to the equation n = x 2 + y2. We shall prove in §7 that i-r(n) is a mUltiplicative function. However, from r(3) = 0, r(9) = 4 we see that it is not completely multiplicative.

6.2 Properties of Multiplicative Functions Theorem 2.1. Letf(n) be a multiplicative function which is not identically zero. Then fll) = 1. Proof Letfla) -:f 0. Fromfla) =fla)f(l) we deduce thatfll) = 1.

0

Theorem 2.2. Let g(n) and hen) be multiplicative functions. Then the function fln) =

Lg(d)h(~) = Lg(~)h(d)

d~

(1)

~n

is also multiplicative. Proof The second equation in (I) follows from the substitution d' = n/d. Suppose that (a, b) = l. Then f(a, b) = L g(d)h (ab). dlab d

Let u = (a, d), v = (b, d) so that uv flab)

=

=

d and hence

L Lg(UV)h(ab) uv

ula vlb

= L g(u)h ula

= f(a)flb).

(~) L g(v)h (~) u

v

vlb

0

Theorem 2.3. Letf(n) be a multiplicative function which is not identically zero. Then L J1.(d)fld) din

=

TI (l -

f(p»,

(2)

pin

where p runs through the prime divisors of n. Proof We put g(n) = J1.(n)fln), hen) = I in Theorem 2.2, so that the left hand side of (2) is a multiplicative function. It is clear that the right hand side of (2) is also multiplicative. It follows that we only need to prove (2) when n = 1 and n = pi, and these two cases can be verified easily. 0

105

6.3 The Mobius Inversion Formula

Theorem 2.4. Let j(n) be multiplicative. Then

j(m, n»j([m, n]) = f(m)f(n) , where [m, n] is the least common multiple of m and n. Proof Let

Then f(m) = f(plt') ... f(p!s), f(n) = f(p~l) ... f(p~s),

Since f(i)f(pr) = f(pmaX(l,r)f(pmin(I,r), the theorem follows.

0

6.3 The Mobius Inversion Formula Theorem 3.1. Let n > O. We have

LJl(d) = LJl(n/d) = L1(n) = din

din

{I, 0,

if n = I, if n # 1.

Proof This follows from takingf(d) = 1 in Theorem 2.3.

0

Theorem 3.2. Let 0 < '10 ::;:; '11 and let h(k) be a completely multiplicative function which is not identically zero. If for any '1 satisfying '10 ::;:; '1 ::;:; '11 we have

g('1)

j(k'1)h(k), L "'k"'ql/q

(I)

1

Jl(k)g(k'1)h(k) ; L ",k"'ql/q

(2)

1

=

then f('1) the converse also holds.

=

106

6. Arithmetic Functions

Proof From (1) we have

L

L

Jl(k)g(k'1)h(k) =

L

Jl(k)h(k)

f(mk'1)h(m).

Let mk = r. From Theorem 3.1 we have 1

""k~~I/~ Jl(k)g(k'1)h(k) = ""k~~I/~ Jl(k) ""k~~li~f(r'1)h(k)h G·) 1

1

klr

L

f(r'1)h(r)

L

f(r'1)h(r)

Jl(k)

LJl(k) klr

l""r""~li~

L

L

f( r'1)h(r)LJ(r)

= f('1)h(l) = An)

which proves (2). Suppose instead that (2) holds. Then

L

L

f(k'1)h(k) =

h(k)

L

L

L

Jl(m)g(mk'1)h(m)

Jl(r/k)g(r'1)h(k)h(r/k)

1 ""k""~I/~ 1 ""k""~li~

klr

L

g(r'1)h(r)

l""r""~I/~

L 1

which proves (1).

L

Jl(r/k)

l""k""~I/~

klr

g(r'1)h(r)LJ(r) = g('1)

""r"" "I.l/~

0

We can extend this theorem as follows: Theorem 3.3. Let ~o not identically zero.

~

1 and let H(k) be a completely multiplicative function which is all real ~ satisfying 1 :::; ~ :::; ~o we have

Iffor

G(~)

L

=

F(~/k)H(k),

(3)

Jl(k)G(~/k)H(k);

(4)

l""k""~

then we have, for such

~,

F(~) =

L l""k""~

the converse also holds. Proof Letf('1) = F(lN) and g('1) = G(I/'1)' Then from (3) and (4) we have g('1) = G(l/'1) =

L

l""k""l~

F(

~) H(k) = L

'1

l""k""l~

f('1k)H(k) ,

107

6.4 The Mobius Transformation

f{1'/)

= =I F(1/1'/)

l"k"l!~

J1.(k)G

(~) H(k) = I

l"k"l!~

1'/

These are just formulae (1) and (2) with 1'/1 = I

~

J1.(k)g(1'/k)H(k).

Igo = 1'/0.

D

We now apply this to the following:

Theorem 3.4. When

~ ~

I we have

II

J1.r)

1 H"~

Proof In (3) we set

F(~)

~ ~

(5)

= =I H(k) I

If I

I ~ l.

so that GW

I

=

J1.(k)

1"kq

=

[~].

[t]·

(6)

< 2, then (5) clearly holds. Suppose now that ~

IxI

k= 1

J1.(k) k

From (4) we have

~

2, and let x

= [~]. T~en

-11=1 I J1.(k)(~-[~])1 k

k= 1

k

=IIJ1.(k)(~-[~])I~ k k k=2

II=x-l.

k=2

Therefore

xl I k=l

J1.(k) k

and the required result follows.

I~ I + (x -

1)

=

x,

D

6.4 The Mobius Transformation Another consequence of Theorem 3.3 is the following:

Theorem 4.1. Let h(k) be a completely multiplicative function which is not identically zero, and let no be a positive integer. If for all n satisfying I ~ n ~ no, we have g(n)

=

If(d)h(~),

(I)

din

then, for such n, we have f{n) =

I din

J1.(d)g('!.)h(d); d

(2)

the converse also holds. Proof We define F(~) by setting F(~) = f(~) when ~ is an integer and F(~) = 0 if ~ is

108

6. Arithmetic Functions G(~)

not an integer, and we define G(n) = g(n) =

similarly. We can rewrite (1) and (2) as

Ij(d)h(~) = If(~)h(k) = I F(~)h(k) d k k

din

kin

l';k';n

and F(n) =j(n)

=

IJ1.(d)g(~)h(d) = IJ1.(d)G(~)h(d) d

din

=

d

din

1.;~.;/(d)G(~)h(d).

From the definition of F(~) and

G(~)

these two formulae can also be written as

G(~) = I

F(i)h(k),

F(~) = I

J1.(k)G(i)h(k).

l';kq

l';k';~

Here ~ satisfies 1 :::; ~ :::; no. Conversely (1) and (2) can be deduced from these formulae. The theorem now follows from Theorem 3.3 with ~o = no. 0 Definition. If

g(n) = If(d) = din

If(~)'

din

then we call g(n) the Mobius transform ofj(n). We also callj(n) the inverse Mobius . transform of g(n). From Theorem 4.1 we have j(n) =

IJ1.(d)g(~) = IJ1.(~)g(d).

din

din

From Theorem 2.2 we see that the Mobius-- transform, and the inverse Mobius transform, of a multiplicative function is multiplicative. Example 1. From Theorem 3.1 we see that A(n) is the Mobius transform of J1.(n). Example 2. From u;.(n) = Idln d\ we see that u;.(n) is the Mobius transform of the multiplicative function E;.(n) = n\ and therefore u;.(n) is a mUltiplicative function. Since 'I

U;.(pl)

=

I

p;'(l+I)_1

pm;,

= --:-;,--

(2 # 0),

P - 1

m=O

we deduce that if n = TIvP~v, then u;,(n) ~

TI v

p;'(lv+ 1) _

v

;,

Pv - 1

1 •

109

6.4 The Mobius Transformation

In particular, when A = 0, we have d(n)

= (J'o(n) =

TI (Iv + 1),

which we already proved in an earlier exercise. Example 3. The function Eo(n) = 1 is the Mobius transform of LI(n). Example 4. Let n be fixed and let the integers 1,2, ... , a, ... , n be partitioned into distinct classes according to the value of t!le greatest common divisor (n, a). If d = (n, a), then we can write n = dk and 1 = (k, a/d). Now the number of integers a satisfying 1 = (k, a/d) is precisely
=

I
din


din

In other words, the function El (n) = n is the Mobius transform of
Theorem 4.2.
Jl(d)

= nI - · D din

d

Example 5. More generally we denote by
n = TIvP~v, we have
=

n).

I Jl(~) = n). TI (1 - ~). din

d

pin

P

We leave the verification for this to the reader. Example 6. Consider a prime moduluS'p. Let the polynomial x p "

x be factorized into a product of irreducible factors. If m is the degree of one of its factors, then we know that min. Conversely any irreducible polynomial of degree m must be one of its factors. Denote by
That is, the function pn is the Mobius transform of n
=

I

Jl(m)pn/m,

min

which gives another proof of Theorem 4.9.2.

110

6. Arithmetic Functions

Example 7. We seek the Mobius transform of A(n). Let n = pll' ... p~v be the standard factorization of n. Then I,

IA(d) =

Ir

I

I

din

A(p~'

... p:r)

Sr=O I,

=

Ir

I

A(p~')

+ ... + I

lr

=

lr

I

S1:::::

A(p:r)

Sr= 1

" =I

lOgPI

+ ... + I

1

logPr

Sr= 1

= IllogPI + ... + IrlogPr =

logn,

that is logn is the Mobius transform of A(n). Example 8. Since A(n) is the inverse Mobius transform of logn, it follows that A(n)

= I J1.(d) logn/d = lognIJ1.(d) din

=

din

LI(n) log n -

I

I

J1.(d)logd

din

J1.(d) log d.

din

Since LI(n) logn is always zero, it follows that A(n) is the Mobius transform of - J1.(n)logn. Collecting our results we have the .following table, where g(n) represents the Mobius transform of fin). fin) g(n)

- J1.(n)logn A(n)

A(n) logn

Exercise 1. Let g(n) and gl(n) be the Mobius transforms of f(n) and fl(n) respectively. Prove that .Ig(d)fl din

(~) = If(d)gl (~). din

Exercise 2. Evaluate the inverse Mobius transform of g(n)gl(n). Exercise 3. The Mobius transform of the Mobius transform of fin) is given by

If(a)d(~). a

aln

Exercise 4. Use the method of Example 6 to prove formula (1) of §lO, Chapter 4.

111

6.5 The Divisor Function

6.5 The Divisor Function Theorem 5.1. We have, for all positive integers m, n, d(m, n)

~

d(m)d(n).

Proof If p is a prime, then

Since den) is a multiplicative function, the result follows. Theorem 5.2. Let

B

> O. Then den)

Here the O-constant depends on Proof Let n =

If pe

~

D

=

(1)

O(ne).

B.

TIpln pa be the standard factorization of n. We have

2, then pae

~

+ 1. Therefore

2a ~ a

~

TI

1

pin

l(a

pE<2

a + 1 TI + 1)e1og2 pin

a

a

+ 1 ~ TI _2_, + 1 P£<2 e1o g 2

pC~2

and the required result follows.

D

Theorem 5.3. Let q be a non-negative integer and

~ ~

2. Then (2) (3)

Proof We first prove (3) by induction on q. We know that the result holds when q = 0, and we now assume that it holds when q is replaced by q - 1. Then

I l";n";~

(d(n»q n

=

I l";n";~

(d(n»q- 1 n

I 1 uln

112

6. Arithmetic Functions

Let n = uv and using d(uv) ::;:; d(u)d(v) we see that

L

(d(n»q::;:;

l"'n"'~

n

L

(d(U»q-l

L

(d(vW- 1

l"'u"'~

U

l"'v"'~/u

V

To prove (2) we again use induction on q:

L

(d(n»q

= L (d(n»q-l L 1 L 1

::;:;

uln (d(n»q-l

L

"'u"'~ 1 "'n"'~ uln

L

(d(U»q-l

::;:;~ L

L

(d(V»Q-l

(d(U»Q-l O((lOg~)2q-1-1)

1 "'u"'~

U

= 0J:Wog ~)2q-l). D This theorem can be made much sharper. We give only a very important special case as an example. Theorem 5.4.

If ~ ~

1, then

L

d(n) = ~log~

+ (2/, - l)~ + O(jh

where /' is Euler's constant. Proof We have

L 1 = L 1. uln In other words Ll "'n",~d(n) is the number of lattice points in the first quadrant which lie below the rectangular hyperbola uv = ~. Bya lattice point we mean a point with integer coordinates. By erecting two perpendiculars to the axes passing through the point (,fi, ,fi) the region concerned is divided into a square together with two regions each having the same number of lattice points inside. That is L

d(n) =

L

1 "'n"'~

[A]

L

1 = [,fi]2

+2

L

L

u = 1 [J~] < v '" elu

113

6.6 Two Theorems Related to Asymptotic Densities

Since

IJ {-U =l l-log ~ + y + 0 2

u=I

(1) rr' V~

it follows that

I

d(n)

= ~ log ~ + (2y

- l)~

+ O(.,fi).

Exercise 1. Prove that, for ~ ~ 2, d(n)

I -

l~n~~ n

=

1

-log2 ~ 2

+ 2ylog~ + c + O(ctlog~).

Exercise 2. Prove that, for any positive e, we have

(J(n) = O(nl +e). Exercise 3. Prove that, for

~ ~

2,

1 (J(n) = - n 2 l~nq 12

I

(The reader may use the result Exercise 8.7.1.)

I:,= 1 l/n2 =

e+

O(~ log ~).

n 2 /6, a formula which will be proved in

6.6 Two Theorems Related to Asymptotic Densities Definition 1. Let there be a set of positive integers, and denote by N(x) the number of elements in the set not exceeding x. Suppose that . N(x) ltm--= x-+

IX.

X

00

Then we say that the set has asymptotic density

IX:

Examples. The set of odd positive integers has asymptotic density t. The set of all perfect squares has asymptotic density O. In this section we shall use the result ;. Jl(n) L..

n=1

n

2

=~ n

2'

(1)

the proof of which is given in Exercise 8.7.1. Definition 2. A positive integer which is not divisible by any prime square is called a square-free number. The set of square-free numbers has asymptotic density 6/n2. More precisely we have

114

6. Arithmetic Functions

Theorem 6.1. Let Q(x) denote the number of square free numbers not exceeding x. Then, as x --+ 00,

Q(x)

6x r: = 2 + O(y x).

(2)

n

Proof We partition the set of positive integers not exceeding x into subsets according to their largest square divisor q2. The number of positive integers not exceeding x having largest square divisor q2 is Q(X/q2) so that

[J~]

L

[x] =

(x)

Q 2

Let x

.

q

q= 1

= y2. Then

From Theorem 3.3 we have

L J1~~) + L

= y2

l~k~y

2

= 6 y2 + y20( n

0(1)

l~k~y

L ~2) + O(y)

k>y

6 n

= zy 2 '+ O(y), where we have used formula (5.8.8). The required result follows.

D

We can restate Theorem 6.1 as: Theorem 6.2.

If x

~

1, then

L

n~x

1J1(n)1

r:

6x

= 2 + O(y x). D

(3)

1I

The number of pairs of integers x, y satisfying 1 ~ x ~ y ~ n is equal to + 1)/2. Let us denote by 4>(n) the number of those pairs satisfying (x,y) = 1. We can prove that n(n

r n->oo

6

4>(n)

1m 1 (

"2n n

+

1)

,.~2·

We can interpret this result by saying that the probability that two given integers are coprime is 6/n2. Here we prove a sharper theorem.

115

6.7 The Representation of Integers as a Sum of Two Squares

Theorem 6.3.

L qJ(n) =

=


3n 2

.

-2

+ O(n logn).

1t

m:::;;n

Proof We have
=

i

m

m=l

=

dtl

1

L J1.(d) dim

J1.(d)

=

d

L

dd'~n

:%: d' = ~

00 J1.(d) =_n 2 2 2 d=l d

L

d'J1.(d)

dt

J1.(d)

+ 0 (00 n2 L

([~J + [~J)

1) +

2"

n+l d

O(nlogn)

3n 2 = - 2 + O(n) + O(n logn) 1t

3n 2 = - 2 + O(nlogn) 1t

as required.

0

6.7 The Representation of Integers as a Sum of Two Squares We first introduce the function

O,

x(n)

= { (_ lyHn-l),

if 21n, if 2,tn.

It is easy to verify that x(n) is multiplicative. We write J(n) =

L X(d), din

the Mobius transform of x(n), so that J(n) is also multiplicative. If n = npln pi is the standard factorization of n, then J(n)

=

n(1 + X(P) + X(p2) + ... + X(pl)). pin

Using the function x(n) we can restate Theorem 3.5.1 as follows:

116

6. Arithmetic Functions

Theorem 7.1. Let V(n) denote the number of solutions to the congruence x 2 == - 1 (modn). Then V(n)

=

{

O'

n(l + X(p)),

if 41n, if 4%n.

pin

In the product here p runs through all the distinct prime divisors of n.

D

It is not difficult to deduce this theorem from Theorem 3.5.1 and Theorem 2.8.1. The main aim of this section is to prove:

Theorem 7.2. Let r(n) denote the number of solutions to the equation n = x 2 + y2 in integers x, y. Then r(n) = 4c5(n). We shall require two auxiliary results for the proof of this theorem.

Theorem 7.3. We have the identity

Proof Direct multiplication gives the result at once.

D

Exercise 1. Prove the identity: (xi

+ x~ + x~ + x~)(Yi + y~ + y~ + y~) = (X1Yl + X2Y2 + X3Y3 + X4Y4)2 + (X1Y2 - X2Yl + X3Y4 - X4Y3)2 + (X1Y3 - X3Yl + X4Y2 - XzY4)2 + (X1Y4 - X4Yl + X2Y3 - X3Y2)2.

Exercise 2. Prove the identity: (xi

+ x~ + x~ + x~ + x; + x~ + x~ + x~) x (yi + y~ + y~ + y~ + Y; + y~ + y~ + y~) = (X1Yl + XzY2 + X3Y3 + X4Y4 + XsYs + X6Y6 + X7Y7 + xsYS)2 + (X1Y2 - X2Yl - X3Y4 + X4Y3 - XSY6 + X6YS - X7YS + XSY7)2 + (X1Y3 + X2Y4 - X3Yl - X4Y2 + XSY7 - X6YS - X7YS + xSY6f + (X1Y4 - X2Y3 + X3Y2 - X4Yl - XsYs - X6Y7 + X7Y6 + xsYs)2 + (X1Ys + X2Y6 - X3Y7 + X4YS - XSYl - X6Y2 + X7Y3 - XSY4)2 + (X1Y6 - X2YS + X3YS + X4Y7 + XSY2 - X6Yl - X7Y4 - XSY3)2 + (X1Y7 + X2YS + X3YS - X4Y6 - XSY3 + X6Y4 - X7Yl - XSY2)2 + (X1Ys - X2Y7 - X3Y6 - X4YS + XSY4 + X6Y3 + X7Yz - XSY1)2.

117

6.7 The Representation of Integers as a Sum of Two Squares

Theorem 7.4. Let n > 1 be such that the congruence

f2 == - 1 (modn)

(1)

has a solution. Then there exists a unique pair of integers x, y satisfying

x> 0,

y>O,

(x,y)

= 1,

y

== Ix

(modn).

(2)

Proof Clearly if (2) is soluble, then so is (1). A necessary condition for (1) to be soluble is that n is representable as a

= 0 or 1,

and Pi (i = 1,2, ... ,s) is a prime == 1 (mod 4). We now use induction to prove the theorem. 1) We consider first the case n = pA. If A. = 1, then from 12 + 1 == 0 (modp) we see that when (x,p) = 1, we have x 2/2 + x 2 == 0 (modp). We shall presently choose y and x so that x 2f2 == y2 (modp), and x 2 < p, y2 < p. Let x and y take the values 0,1, ... , and consider the various differences xl- y. Since there are + 1)2> p such differences, there must be two which are congruent modp. Let xII - YI == X21 - Y2 (modp), or (Xl - x2)1 == YI - Y2 (modp), and we can assume that Xl - X2 > 0 so that Xl - X2 < IYl - Y21 < and this then gives our desired x and y. For this pair x, Y we have x 2 + y2 = tp, and it is easy to see that t = 1, (x,y) = 1. The congruence Y == mx (modp) is soluble, and from x 2(1 + m 2) == 0 (modp) we see that m == ± I. Ifm = I, then we take the pair (x,y), while ifm = - I, then we take the pair (y, x). Now assume that p ¥- 2 and thatthe theorem holds for n = pA. Let ( - /)2 == - 1 (mod pH I) so that there exist u, v such that

([..JP]

[..JP]

..JP,

u > 0,

v> 0,

(u, v)

..JP

= 1,

v

== -

lu

(modpA).

When n = pA+l, we have pHI

=

(xu

+ YV)2 + (xv

_ yU)2

= X2+

y2

(X> 0, Y> 0).

First we have (X, Y) = 1, since otherwise pl(X, Y), but X

== xu + yv == xu -

flxu

== xu(1

- fl) =1= 0

(modp),

which is impossible. Next, because (X, p) = 1, the congruence Xm == Y (mod pA + I) is soluble. Thus X 2 + Y 2m 2 == 0 (modpHI) or 1 + m 2 == 0 (modpHI). From Theorem 2.9.3 this congruence has only two solutions, so that m = ± l. The desired result follows from the discussion in the case A. = 1.

118

6. Arithmetic Functions

2) Let n = ab, a > 1, b> 1, (a, b) = 1, and suppose that 12 == - I

(modn),

u2 + v 2 = a,

u> 0, '

v> 0,

(u,v)

= I,

v == lu

(mod a),

x 2 + y2

x> 0,

y>O,

(x,y)

=

1,

y == Ix

(mod b).

- YV)2

=

= b,

From Theorem 7.3 we have n

= ab = (xv + yuf + (xu

X 2 + y2.

(If xu - yv > 0, then let xu - ·yv = Y; otherwise we let xu - yv = - Y.) We now prove the following: (i) (X, Y) = 1. Let pl(X, Y). Then xv

+ yu =ps,

xu - yv =pt,

or x(u 2 + v 2)

= p(sv + tu),

y(u 2 + v 2) = p(su - tv).

Since (x,y) = I, we must have pl(u 2 + v 2), that is pia. Similarly plb. But this contradicts (a, b) = l. (ii) X == IY (mod n). From our assumption we have xv

+ yu == Ixu -

Iyv == I(xu - yv)

(mod a),

xv

+ yu ==

+ Ixu == I(xu

(mod b).

-Iyv

- yv)

Since (a, b) = I, it follows that X == IY (mod n). 3) Uniqueness. Suppose that there are two pairs (X, Y), (X', Y') both satisfying the conditions. Then n 2 = (XX'

+

yy')2

+ (XY'

_ YX')2.

But XX'

+

YY' == XX'(l

+ [2) == 0

(modn),

so that XX'

From XY' - YX'

=

+ YY' =n,

XY'- YX'=O.

0, we have

X

Y

-=-=c X' Y' ,

119

6.7 The Representation of Integers as a Sum of Two Squares

so that X 2 + y2 = C 2(X,2 + y'2) giving C = ± 1. Also from X > 0, X' > 0 we see that C = 1. The proof of our theorem is complete. 0

Proof of Theorem 7.2. From Theorem 7.1 and Theorem 7.4 we see that the number of solutions to x 2 + y2 = n, (x, y) = 1 is 4 V(n). We now consider the equation x 2 + y2 = n, and we partition the various solutions into sets according to (x, y) = d. The number of solutions satisfying (x,y) = d is equal to the number of solutions satisfying X)2 (d

(y)2

+ d

=

n d2

'

that is 4 V(n/d 2 ). Therefore

r(n)

= 4

I d21n

v(-;) d

= 4

I V(~)2(d), d

din

where 2(d) = I or 0 according to whether d is a square or not. Since V(n) and 2(n) are both mUltiplicative it follows that r(n)/4 is multiplicative. Since ben) is also multiplicative the theorem will follow if we show that r(n) = 4b(n) when n = p'. Now, if 21m, then

r(pm) = V(pm) + V(pm-2) + ... + V(p2) + V(l) 4

0+ ... + 0 + I = I, + ... + 0 + I = I, 2+"'+2+1= m =-·2+I=m+l 2 '

°

if p = 2, if p == 3

(mod 4),

if p == 1

(mod 4),

and if 2,tm, then

I,

=

{

°~ + I,

if p = 2, if p == 3 if p == 1

(mod 4), (mod 4).

On the other hand we have

b(pm) = 1 + X(p) + ... + X(pm)

I +0+0+ ... +0= 1, _ { 1 - 1 + ... + I = 1, I - I + ... - I = 0, 1 + 1 + ... + 1 = m + I, The theorem is proved.

0

if if if if

p=2, p==3 p==3 p==l

(mod 4), (mod 4), (mod 4).

21m, 2,tm,

120

6. Arithmetic Functions

Theorem 7.5. Denote by A and B the number ofdivisors ofn which are congruent I and 3 (mod 4) respectively. Then r(n) = 4(A - B). Proof This is an immediate consequence of Theorem 7.2.

0

Theorem 7.6. Let e > O. Then r(n) Proof Since r(n)

~

= O(n').

4d(n), the required result follows from Theorem 5.2.

0

6.8 The Methods of Partial Summation and Integration Theorem 8.1 (Abel). Let a numbers and

~

b and let n vary in a

~

n

~

b. Let 'l'n and en be complex

Then

IJa 'l'nenl ~ a~::b ISnl C"'m~b-l lem Proof Let Sa-l

=

em+11

+ lebl ).

(I)

O. Then b

b

n=a

n=a

L 'l'nen = L (sn =

Sn-l)en

b

b-l

n=a

n=a

L Snen - L Snen+l b-l

=

L sn(en -

en+d

+ Sbeb,

n=a

so that

Theorem 8.2. In the previous theorem if en is a positive decreasing sequence, then

Int 'l'nenl ~ a~::b ISnlea· We now apply this to the following:

0

(2)

121

6.8 The Methods of Partial Summation and Integration

Theorem 8.3.

If s >

0, then

"L... x(n)s I -....::::~~s' In~a n a so .that the series

I:'= 1 x(n)/n s converges when s> 0.

Proof We have x(a) + x(a + I) + x(a + 2) + x(a + 3) = 0,

so that

From Theorem 8.2 we deduce that

I ±X(7)1~~· n a n=a

Since the right hand side is independent of b, the theorem follows.

D

Note: In the next section we shall require x(n)

I

00

-=

n= 1

n

I

I

I

n

1--+---+'" =-. 3 5 7 4

This can be proved using the series expansion for tan - 1 X in ordinary calculus. Analogous to Theorems 8.1 and 8.2 we have: Theorem 8.4. Let ~ ~ '1 and let x vary in ~ ~ x ~ '1. Suppose thatf(x) and g(x) are continuous and g(x) is differentiable. Let x

11 (x) =

f fit) dt.

Then q

q

Iff(X)g(X)dxl ~

Moreover, if g'(x) ~

~ ~~::ql/l(x){flg'(X)ldX + Ig('1)I). ~

°

and g(x) > 0, then q

Iff(X)g(X)dxl

~ g(~) ~~::ql/l(X)I.

122

6. Arithmetic Functions

Proof From integration by parts we have ~

~

= I g(x)dl1 (x)

II(x)g(X)dX

~

= g(rO/l (1]) - III (x)g'(X) dx, and hence

II ~

fix)g(x) dx

I~ ~~::~

~

III (x)1 (lg(1])1

+I

~

Ig'(x)1 dX).

~

The last part of the theorem is also clear.

D

Example. Let a > O. Prove that 00

II

I cOS~/~Y I~ ~ maxi 00

COSX2dxl

=

I

2y

2a

a2~~

~

a

~

ICOSYdyl

~~. a

~

6.9 The Circle Problem' Theorem 9.1.

L

r(n)

=

nx

+ o(fi)·

Proof From Theorem 7.2 we have

L

r(n)

=4

l~n~x

L LX(d) l:::=;n~xdln

=4

L 1 ~d:::=;x

= 4

x(d)

L 1 ~n:::;;x

L X(d)[~J.

l~d~x

Here we divide the sum into two parts. From Theorem 8.3 we have

123

6.9 The Circle Problem

= 4x

I: d=l

= 1tX

X(d)

+ O(Jx)

d

+ O(Jx);

the other part is

and from Theorem 8.2 we have The theorem is proved.

D

Another proof of the theorem is the following: Clearly LO";n";xr(n) is the number of pairs of integers u, v satisfying u2 + v2 ~ x. In other words the sum is the number of lattice points inside the circle centre at the origin with radius Jx. This circle has area 1tx. We partition the plane into unit squares with orthogonal lines passing through the lattice points. To each point (u, v) in our circle we assign the square whose four corners have the coordinates (u, v), (u + 1, v), (u, v + 1), (u + 1, v + 1). These squares must lie inside the circle u2 + v2 = (Jx + J2)2 and they include the circle u2 + v2 = (Jx - J2)2. Therefore

and the required result follows at once. We observe that this second proof can be used as a proof for 1t 1 1 1 1--+---+ ... =-. 3 5 7 4 Concerning the pro blem of the number oflattice points inside a closed curve, the Czech mathematician M. V. Jarnik proved the following: Theorem 9.2. Let I ~ 1 be the length of a rectifiable simple closed curve and let A be the area of the region bounded by the curve. If N is the number of lattice points inside the curve, then

IA - NI < I. Proof (Steinhaus). We first prove the following two simple lemmas. Lemma 1. Let C be a rectifiable curve inside a unit square with the two end points on the boundary of the square. IfC crosses the two diagonals of the square, then its length must be at least 1.

Proof If the two end points are on the opposite sides of the square, then the result follows at once. Suppose next that the two end points are on two adjacent sides of

124

6. Arithmetic Functions

rJ.

P a

b

P

the square as shown in the diagram. It is easy to see that

A similar argument applies when the two end points are on the same side of the square. Lemma 2. Let C be a rectifiable curve inside a unit square with the two end points on the boundary of the square so that the square is partitioned into two regions. Suppose that C does not pass through the centre of the square, and denote by LI the region which does not contain the centre. Then the area of LI must be less than the length of C.

Proof We consider separately the cases shown in the following diagrams:

rJ.

P

q fJ

rJ.

fJ

P

rJ.

P

fJ

P

rJ.

fJ

rJ.

q P

P

Let A be the area of the region LI and I be the length of C. In the first two cases it is easy to see that every point of C is of distance at most I from the base line rxf3 so that LI must lie inside a rectangle with sides 1 and I and hence A < I. In the remaining three cases we see from Lemma 1 that I;?; 1 and so A < 1 ~ l. We can now proceed to prove the theorem. Denote by I the region inside the curve. We form a net of unit squares in the plane with the lines

x=m

+t,

y=n+t

(m,n

=

0,

± 1, ± 2, ... ).

Let Qb Q2,' .. , Qk be those squares which contain part of the boundary of I, let C i be the part of the curve in Qi' let Q i be the intersection of Qi and I, and define

{I,

N.= , 0,

if Q i contains a lattice point, otherwise.

We let Ai be the area of Qi, Ii the length of Ci, so that our theorem will follow if we can prove that IAi - Nil < 1;. Now the case when the whole of Ilies inside a Q follows at once since I;?; 1. We can assume therefore that Ci is made up of a number of sections of the curve and Qi is partitioned into regions DlS).

125

6.10 Farey Sequence and Its Applications

If the lattice point does not lie in any DlS) so that it lies on Ci, then Ni = 0, o < Ai < 1 and Ii ~ 1 so that our required result follows. If the lattice point lies inside a Dl S) we denote by AlS) the area of Dl S). If Dl S) is not in I, then Ni = 0, Ai ~ 1 - AlS); if DlS) is in I, then Ni = 1, 1 - Ai ~ 1 - AlS) and, from Lemma 2, we have 1 - AlS) < Ii' The theorem is proved. D

It is clear that Theorem 9.1 is an immediate consequence of Theorem 9.2. Exercise 1. Find the asymptotic formula for the number of lattice points inside an ellipse centre at the origin. Exercise 2. Prove that the number of lattice points inside the sphere u 2 + v2 + w2 ~ x is given by

1nx 3 / 2

+ O(x).

Exercise 3. Generalize the previous exercise to a sphere in n-dimensions. Exercise 4. Determine the order of Ln.;xr2(n). Exercise 5. The number of lattice points inside the circle u 2 coordinates is given by 6 -x n

+ v2

~

x with coprime

+ O(fi log x).

6.10 Farey Sequence and Its Applications Farey sequence was discovered well over a hundred years ago, but its significance in number theory is revealed only in modern times. "-

Definition 1. By the Farey sequence of order n we mean the fractions in the interval from 0 to 1, whose denominators are ~ n, arranged in ascending order of magnitude. That is, they are numbers of the form a

b'

(a, b) = 1,

arranged into an increasing sequence. We denote by tYn the Farey sequence of order

n. Example:

tY7

is the sequence

The total number offractionsin tYn is 1 + L~= 1qJ(m). These fractions divide the interval 0 ~ x ~ 1 into L~=l qJ(m) parts, and tYn+l is obtained from adding the

126 cp(n

6. Arithmetic Functions

+ 1) numbers a

+ 1) =

(a,n

n + l'

1,

o
Theorem 10.1. Let ~ be an irrational number, 0 < ~ < 1. Let am/b m, a~/b~ be two

successive Farey fractions of order n satisfying a~

am bm

-<~<-.

b~

Then (i) am/bmis an increasingfunction ofn, while a~/b~ is a decreasingfunction ofn, and

(ii) bm and b~ are increasing and unbounded functions of n.

Proof We note that every rational number in the interval [0, 1J is a term in a Farey sequence. The theorem follows once from the definition of a Farey sequence of order n. 0 Theorem 10.2. Let alb, a'/b' be two successive terms in alb < a'/b', then ba' - ab' = 1.

tJn. Then b + b'

~

n

+ 1. If

>

Proof Since (a, b) = 1, there are integers x, y such that bx - ay = 1,

n - b < y::::; n.

(1)

It follows at once that

y> 0,

(x,y)

=

x a 1 a -=-+->-.

1,

y

b

by

b

It suffices to prove that x/y = a'/b'. This is because we can then deduce that x y = b', ba' - ab' = 1 and b + b' > n. Suppose that x/y -:f a'/b'. Then

a

a'

x

b

b'

y

-<-<-. From this we deduce that

x y

a b

x y

a' b'

a' b'

all b+y n ~ + - = - - > -b b'y b'b ybb' ybb'

- - - = - - - +- - But we haveJrom (1),

x y

a b

by'~

giving a contradiction. The theorem is proved.

0

1 by

~-.

=

a',

127

6.10 Farey Sequence and Its Applications

Theorem 10.3. Suppose that alb < a"lb" < a'lb' are three successive Farey fractions.

Then a"

a +a'

b"

b

+ b'

Proof From Theorem 10.2 we have a"b - b"a = 1 and a'b" - b'a" = 1, and so, on subtraction, a"(b + b') - b"(a + a') = O. The required result follows. 0 Definition 2. Let alb and a'lb' be two successive Farey fractions. Then we call

(a

+ a')/(b + b') the mediant of the two fractions.

Theorem 10.4. The mediant lies between the two fractions alb and a'lb', and the distance from them are

b(b

+ b')

and

b'(b

+ b')

respectively. Proof We assume that alb < a'lb'. Then a' b'

a b

+ a' + b'

ba' - ab' b'(b + b')

a b

+ a' + b'

a

a' b - ab'

-

----=

=

~

+ b')

>0

,

1

b = b(b + b')

Theorem 10.5. Let ~ be a real number, 0 <

1 b'(b

=

b(b'

+ b) > O. 0

< 1. Then there always exists alb in

~n

such that

I~ -~I < ;n'

0< b

~

n.

Proof We partition the interval (0, 1) into subintervals by the points in ~n together with their mediants. Now ~ must be in one of these subintervals one of whose end point is alb while the other is (a + a')/(b + b'). Therefore we have

The theorem is proved.

D

~ and t'f be any two real numbers, t'f rational number alb such that

Theorem 10.6. Let

1~-~I
~

1. There always exists a

o < b~t'f. ~

< 1 and the required result follows at

128

6. Arithmetic Functions

Theorem 10.7. Let

~

be any real number. There always exists a rational number alb

such that (2)

If ~

is irrational, then there are infinitely many such alb satisfying this inequality.

Proof Clearly we need only examine the case when ~ is irrational, 0 < anlbm a~/b~ be two successive terms in ~n satisfying

~

< 1. Let

an a~ -<~<-. b~

bn

From the proof of Theorem 10.5 we see that one of these must satisfy the inequality (2). Our theorem now follows from Theorem 10.1. 0 Theorem 10.8. Let ~ be any irrational number. Then there exist infinitely many rational numbers alb such that

I~ -~I < Jb

(3)

2 •

Proof We can assume without loss that 0 < ~ < 1. Let alb and a'lb' be two successive Farey fractions of order n satisfying alb < ~ < a' Ib'. Let w = b'lb and we consider separately the following two cases. 1) Suppose that w> (1 + J"S)/2 or w < 1)/2. Then, from Theorem 10.2, we have

(J"S -

a' a b' - b = bb'

= b2 w .

Since

1 1(1)

- - - 1 +- =

w

J"S

w2

1

---(w 2 -J"Sw+ 1) J"Sw 2

~(J"S + l))(W - ~(J"S -

= - _l_(w -

J"Sw 2

we have

~- ~< a

11

b + J"S b2

J

b2 ( 1 +

a'

>

2

If -

~2) = Js (:2 + b~2 ),

11

J"S b

'2 •

Therefore the two intervals and

2

1)) < 0,

6.11 Vinogradov's Method of Estimating Sums of Fractional Parts

overlap, and so one of them must contain or 2) Suppose that (fi - 1)/2 < b

OJ

egiving 1Ie--a'b' i
129

(4)

< (1 + fi)/2. Then

+ b' > t(fi + l)b,

b

+ b' < t(fi + l)b'.

Therefore we can deal with the intervals

(~b' ~) b + b'

and

with the method in 1). That is, there are three possibilities; apart from the two situations in (4) we also have

Ie - :: :: I< f i (b 1+ b,)2 . e

Therefore, given any n, there always exist a, b such that (3) holds. Since is irrational, band b' tend to infinity with n according to Theorem 10.1, and so our theorem is proved. 0 Exercise. Prove that the denominators of two successive Farey fractions are

different.

6.11 Vinogradov's Method of Estimating Sums of Fractional Parts Let {oc} be the fractional part ofoc; that is {oc} = oc - [ocJ. The purpose of this section is to study sums of the form

L

{fix)}.

A~x
We shall apply the results in the next section. Theorem 11.1. Let m > 0, (a,m)

c ::;:; I/I(x) ::;:; c

= 1, h;::::

+ h,

°

for

and c be real. Suppose that

x=O, ... ,m,

and let

Then

IS - }ml ::;:; h + }.

130

6. Arithmetic Functions

Proof Clearly we have

,I s - ~2 m I~ mill{ax +mtjJ(X)} - ~2 I~ ~2 m. x=O

The theorem therefore follows at once if m ~ 2h + 1. Suppose now that m > 2h + 1. Let r be the least positive residue of ax + [e] modm. We then have

s=

mil {r +
(1)

m

r=O

where
Hence

+ h.

{e} ~
If 0 ~ r < m - [h

+ {e}],

(2)

then

o ~ {e} ~ r +
[h

+ ,{e}] -

1 + {e}

+ h < m,

or o~

+
r

m

< 1;

therefore

or

~ + {e} ~ {r +
+ {e}]

~ r

m

m

m

m

(3)

< m, let r = m - s. Then for s = 1,2, ... , [h + {e}], we have

If
+
and if
s~h

m

+ {e}

+ {e}

- s;

m

- s~ r

+
+ {e} ~ {r +
m

(4)

m

(5)

m

From (4) and (5) we have r {e} {r -1 +-+-~ m

m

+
m

m

(6)

131

6.1 I Vinogradov's Method of Estimating Sums of Fractional Parts

Now from (1), (3) and (6) we arrive at {c} - (h

m-l

r

r=O

m

+ {cn ~ S - L -

~h

+ {c},

and hence - h~S-

The theorem is proved.

t(m -

1) ~ h

+ 1.

D

Theorem 11.2. Let m be an integer, A > 2, 1 ~ m ~ A 1/3, (a, m) = 1, k ~ 1. Suppose that M+m-l

S

=

L

{fix)},

x=M

where fix) has a continuous second derivative in M a 9 f'(M) =-+-,

m

(a,m)

m2 1

A

~

If"(x) I ~

~

x

~

= 1,

M

+m

191 <

- 1 and satisfies

1,

k

-. A

Then

IS - tml

~ t(k

+ 5).

Proof From the mean value theorem of differential calculus we have 2

fiM

+ y) =

fiM)

+ yf'(M) + ~ f"(M + 9'y),

i9'1 <

1.

In Theorem 11.1 we take I/I(y) = m(fi M )

+ ;2 Y + ~y2f"(M + 9'y»).

From the continuity of f"(x) and from 1f"(x)1 > I/A we see that f"(x) does not change sign. We can therefore assume without loss that/"(x) > O. Then we have ( m) (m m "fiM) - m 2 < I/I(y) < m "fiM) + m2

2

) + 21 m A"k ,

or mfiM) - 1 < I/I(y) < mj(M)

+ 1 + tk.

The result follows from taking c = mj(M) - 1 and h 11.1. D

= 2 + k/2 in Theorem

132

6. Arithmetic Functions

Theorem 11.3. Let k ~ I and let fix) have a continuous second derivative in M ~ x ~ M + m, and I

-

A

~

k

If"(x) I ~ -. A

Then M+m-1 S=

L

x=M

I {fix)} = -m 2

+ 0(.1),

where

Proof We take 1: = A 1/3 , M = M 1. We see from Theorem 10.6 that there exist a 1 ,m,8 1 such that (7)

From Theorem 11.2 we have

M,+m,-1

L

x=M,

We next take M2 such that

8'

+ -.!..(k + 5), 2

+ m1 and again from Theorem 10.6 there exist a2, m2, 8 2

M1

=

I {fix)} = -ml 2

and

M2+m2-1

L

X=M2

I {fix)} = -m2

2

8'

+ ~(k + 5), 2

Continuing this way, if after s steps we have

o~ M + m -

I - Ms+l < 1:,

then

IS - t(m1 + ... + ms) - t(M + m - Ms+ 1)1 s

~ 2(k

or (since Ms+1 = M

I

+ 5) + 2(M + m -

M s + 1),

+ m1 + ... + ms) IS - tml < ts(k + 5) + t(1: + I).

(8)

We now have to estimate s. Suppose that 0 < q < 1:, (p, q) = 1. If p, q are given, we can estimate how many m1,'" ,ms are equal to q. From 1f"(x)1 > I/A and its

6.11 Vinogradov's Method of Estimating Sums of Fractional Parts

. 133

continuity we know thatf"(x) does not change sign. It follows that the set of values x satisfying I ---:;;;f'(x):;;;-+-

pip q

forms an interval. Let

Xl> X2

q1:

q

q1:

(9)

be any two points in the interval, so that

Hence X2

I

f

I

f"(t) dt <

:1: '

X,

and so 1

2

-IX2 -

A

xII <-. q1:

This shows that the length of the interval of values x which satisfies (9) is at most 2A/q1:. It follows that the number of mi which are equal to q is at most 2A/q21: + 1. Next, for fixed q, we estimate the number of values P which satisfy (9). Suppose that PI > P2 and

PI 1 PI 1 - - - :;;;f'(XI):;;;- +-, q

q1:

q

q1:

P2 1 P2 - - - :;;; f'(X2) :;;; q

q1:

q

1 + -.

q1:

Then

f XI

I

f"(t) dtl = If'(xd - f'(x2)1

~ PI ~ P2 - :1:'

and so

and hence

PI - P2

kmq

2

A

1:

+ 1 :;;; - - + - + 1.

This shows that the number of P is at most

kmq

2

-+-+ A 1:

1.

134

6. Arithmetic Functions

Collecting our results we see that if we write f'(M i ) as in formula (7), then the number of fractions admi whose denominator mi is q is

2A ~ ( q27:

) (kmq

2

)

+ 1 A +~ + 1

= km (~+~) + (2A + 1)(1 + ~). 2 7:

Summing over q

=

7:

q

q27:

7:

1, 2, ... , [7:] we see that

s~ =

k; (2 oe;

log

7: + 2+ 7:22~ 7:) + o(~)

log A

+~).

The theorem follows from substituting this into (8).

D

6.12 Application of Vinogradov's Theorem to Lattice Point Problems We already proved in Theorem 9.1 that the number R(x) oflattice points inside the circle u2 + v2 ~ x satisfies R(x) = nx + O(fi). In this section we shall prove the following sharper result. Theorem 12.1 (Sierpinski). Let x ;::: 2. Then R(x)

= nx + O(x! logx).

This result is not the best known. Using more complicated analytic tools the author proved in 1942 that, for e > 0, R(x)

= nx + O(x~+e).

(See Note 6.1.) A famous problem in number theory is the conjectUfe that R(x) = nx

+ O(xi +e).

We require the following result for the proof of Theorem 12.1. Theorem 12.2. Letj(x) have a continuous second derivative in the interval Q and let x

u(x)

=

fGo

{t} )dt.

~

x

~

R,

135

6.12 Application of Vinogradov's Theorem to Lattice Point Problems

Then R

I

f(x)

=

ff(X) dx

+ (t -

{R})f(R) -

(t -

{Q})f(Q) - (f(R)f'(R)

Q<x':;R Q

R

+ (f(Q)f'(Q) + f

(f(X)f"(x) dx.

Q

Proof Let Xl be an integer, Q tegration by parts we have p

~

~

oc < 13

R, Xl < oc < 13 < Xl

+ 1.

From in-

p

- ff(X)dX=

'"

ff(x)~G-{X})dX '"

= (t - {f3})f(f3) -

(t -

{oc})f(oc) - (f(f3)f'(/3)

+ (f(oc)f'(oc)

p

+f

(1)

(f(x)f"(x) dx.

'"

Letting oc -+ Xl> 13 -+ Xl +I

Xl

-

+ 1 we have Xl

+ 1) -

f(x)dx = - tf(XI

f

tf(xd

Xl

+

+I

f

(f(x)f"(x)dx.

Xl

From this it follows that [R)

-

f f(x)dx

I

= -

fix)

+ tf([Q] + 1) + tf([R])

[Q)+ I ':;X':; [R) [Q)+ I [R)

+

f

(2)

(f(X)f"(x) dx.

[Q)+ I

If in (1) we let

(J(

=

Q, 13 -+ [Q]

+ 1, then

[Q)+ I

f

fix) dx = -2 1f([Q]

+ 1) -

G-

{Q} )f(Q)

+ (f(Q)f'(Q)

Q [Q)+ I

+

f Q

(f(X)f"(x) dx.

(3)

136

6. Arithmetic Functions

Similarly we have

-f R

j(x)dx

= (t - {R})j(R) - tj([R]) - u(R)f'(R)

IR)

f R

+

(4)

u(x)f"(x) dx.

IR)

The required formula is obtained by adding (2), (3) and (4).

D

Proof of Theorem 12.1. By considering the diagram associated with the circle problem it is easy to see that R(x)

I

= I + 4[Jx] + 8

[Jx - u2 ]

x

-

4[

0<""')#

AT

(5)

Clearly we have

Let us estimate

It. Takej(u) =

Jx - u2 so that from Theorem 12.2 we have

o

)# -x

f

u(u)du (x -

U 2?/2

(1 {A})A - - -I

1t x =-x+-+ --

8

4

2

2

2

2

Jx x+O(l). '\

o

From Theorem 11.3 we have

1

(x

I2 = "2 V2" + O(x 10gx). 1

3

The theorem follows from substituting these estimates into (5).

D

A similar problem to the circle problem is the Dirichlet divisor problem. We already proved in Theorem 5.4 that

I t"'n"'~

den) = eloge

+ (2y -

l)e

+ O(e He ).

137

6.12 Application of Vinogradov's Theorem to Lattice Point Problems

Here we prove:

If ~ ~ 2,

Theorem 12.3 (Voronoi).

L

d(n)

then

= ~ log ~ + (2y

- I)~

+ O(~t log2 ~).

With reference to this problem Yin has improved the result by replacing the error term with O(~H+£). Again the conjecture is that it should be O(xi+£). Proof From the proof of Theorem 5.4 we have

L

L [~J

=2

d(n)

l"n"~

l.;u.;fi

-

(6)

[Jey

We take J(u) = I/u and from Theorem 12.2 we have

J{

L -uI=.lIm -0

l.;u.;fi

£

L

-I =

r. U l-.
+~+

f

-du + (I- 2

U

Ir)-t {v~} ~

1

fi

U(Je)C 1

+2

f

U(X)X- 3 dx.

We note that

f 00

fG00

U(X)X- 3 dx =

~

{x} )X-2 dx

Lf 1

I

I

4

2

=---

00

(n

n= 1

x

+ X)2

dx

o

L

= -l l - o - o {log(n

4

2n=1

I

+ I) -Iogn - -I-} n+l

I

= -4+2 Y' and so we have 2

L ~=~IOg~+2G-{Je})~t+2Y~+O(l). l.;u.;fi

We now estimate

(7)

138

6. Arithmetic Functions

We take to so that [AJ2- to ~ 2~1 ~ [AJ 2- to S=

I

t =0

1•

Then clearly we have

{~} + O( ~1).

I [J{]2-'-'';; u ,;; [J{]2 -,

U

From Theorem 11.3 (replacing m by [AJr t- 1 , and A by [AJ 3 C lr(3t+ 1)), we have

Therefore

s=

t[AJ + 0(~110g2 ~).

Noting that [AJ 2 = ~'- 2{A}~t (6), (7) and (8). 0

(8)

+ 0(1), we see that the theorem follows from

6.13 Q-Results A number offamous problems in number theory are concerned with the accuracy of various asymptotic formulae; that is the problem of reducing the size of the error term in the formula. These results are generally called O-results, and our Theorem 12.1 and Theorem 12.3 are such examples. On the other hand we may also estimate how large the error term must be; that is we can prove that some error terms cannot be smaller than a certain order. These types of results are called Q-results. In §12 we mentioned that the 'O-term in Theorem 12.1 is conjectured to be O(x i +'). Here we prove that if e > 0, then the formula R(x) = nx

+ O(xi -')

does not hold. Actually we shall prove a very general result. In this section K, Kb K 2 , K3 represent absolute constants. At various places we may use the same symbol to denote different constants, but this should not cause any confusion. Let c> °and let ai, a2,'" be integers satisfying °Theorem : ;:; al ::;:; a213.1::;:; (Erdos-Fuchs). .. '. Let fin) denote the number of solutions to the equation ai

+ aj =

n, and r(x) =

I

f(n)

so that r(x) is the number of pairs of integers ah aj satisfying ai formula cannot hold.

+ aj ::;:; x.

Then the

139

6.13 D-Results

We shall first deal with the following auxiliary results. Theorem 13.2. Let an be real numbers such that co n= -

converges uniformly, and that

00

I:'= -co a; converges.

Then

1t

-1t

Proof Clearly we have co

co

I

1t/I(.9W =

I

anamei(n-m)8.

n=-oo m=-oo

The required result follows from integrating term by term over - n to n.

°

I:"

Theorem 13.3. Let bn ~ and let q>(z) = 0( < n, z = re i8 (0 < r < I), then we have

°<

f

f

at

~ 20(

1

bnzn be convergent for Izl < l. If

1t

1q>(zW d.9

~~ 6n

-at

1q>(zW d.9.

-1t

Proof We introduce the function q(.9) =

{I -I~I, 0,

when

1.91

when

0(

~

0(,

< 1.91

~

n.

Then we have

f at

f 1t

1q>(zW d.9

-at

~

f 1t

Iq(.9WIq>(zW d.9 =

m,~

1

bnbmrn+m

-1t

Iq(.9)1 2 ei(n-m)8 d.9.

-1t

When m =I n, we have a

1t

o

-1t

=

4 O(n - m)2

(

0

1-

sin(n - m)O() O(n - m)

~

0,

140

6. Arithmetic Functions

while when m = n,

f "

Iq(.9)12 d.9

=

23!Y. ,

-1[

and therefore we have

-a

-n

Theorem 13.4. Suppose that

Izl < 1 and let co

n=O

Then there exist constants c, C such that Yn O< c < ----;:-=t
00.

Proof From the binomial theorem we have r(r Yn

+ 1) ... (r + n -

=

1)

1·2 ..... n

Since -!-

v+-!-

f

f

logtdt =

{log (v

v--!-

+ t) + log (v -

t)}dt

0

o

it follows that

f

r+I--!-

In

log (r

+I-

1) =

1= 1

In

log t dt

+0

1= 1

I

1

(n 1= 1

(r

+I -

2

)

1)

r+l-i

r--!-+n =

f

logtdt +-0(1)

r--!-

= (r =

(r -

t + n)log(r - t + n) t + n) log n - n + 0(1)

(r -

t + n) + 0(1)

141

6.13 (.I-Results

and n

I

=

10gn!

(} + n)logn

10g1 =

- n

+ 0(1),

/= 1

= (r

10gYn

and the theorem follows. Theorem 13.5.

If bn =

+ 0(1),

- 1) 10gn

0

o(nt 10g-1 n), then when 0 < r < 1 we have

I

bnrn

=

0

((1 - r)-i 10g -

1_). 1- r

1_

n=O

Proof From the hypothesis we have 00

I

1

I

bnrn :::; K

n=O

I

+ 61(r) 10g-1--

ntrn

l-r

n<>(l-r)-t

ntrn,

n >(l-r)-t

(1 -

where 61(r) --+ 0 as r --+ 1. In the first sum there are at most r)-t terms, each of which is at most (1 - r)-i, so that the sum is at most (1 - r)-!. From Theorem 13.4 the second sum is

1 1- r

:::; 6(r)10g-1--(1 - r)-i.

Together we have 00

I

bnrn:::; K(1 - r)-~

1

+ 6(r)10g-1--(1

- r)-i

1- r

n= 1

o

= O(10g - 1_1_(1 - r)-i). 1- r

Theorem 13.6. Letf(x) and g(x) be two continuous realfunctions in the interval (a, b). Then b

b

b

I ff(x)g(X)dX I:::; (fF(X)dX f a

a

g2(X)dx)t.

a

Proof Let A be any real number and consider b

b

b

A2 f F (X)dX+2A ff(x)g(X)dX+ f g2 (X)dX a

a b

=f a

(Aj{X)

+ g(X))2 dx ~ O.

a

142

6. Arithmetic Functions

The discriminant of the quadratic expression cannot be positive and so the theorem follows. 0 Proof of Theorem 13.1. Suppose that

t < r < 1, z = reiiJ., 1 -

r < oc < n12. Let

00

so that we have at once 00

g2(Z)

=

I

f(n)z"

"=0

and 00

(1 - z) -lg2(Z)

I

=

r(n)z".

"=0

If formula (1) holds, then 00

(1 - Z)-lg2(Z) = c

I

nz"

+ h(z)

"=0

= cz(1 - Z)-2 + h(z),

(2)

where 00

I

h(z) =

v"z",

"=0

We shall now derive a contradiction. From (2) we have

f e<

f ~ f e<

Ig(z)1 2 d.9

-e<

=

Icz(1 - Z)-l

+ (1

- z)h(z)ld.9

-e<

n

C

f e<

11 -

zl- 1 d.9

+

-n

11 -

zllh(z)1 d.9,

-e<

and from Theorem 13.2 and Theorem 13.4 we have

From Theorems 13.6 and 13.5 we have

f e<

~ J 11 e<

11 -

zllh(z)1 d.9

e<

Zl2 d.9

J Ih(zW d.9 -a

-(1

-e<

n

~

(2oc(1

+ r2)

- 4r sin oc)

J Ih(zW d.9

(3)

143

6.14 Dirichlet Series

::;;; {(2a(l - r)2

+ 4r(a -

sina))e(r)(l - r)-! 10g_1_1_}t

1- r

1

::;;; e(r) a!(l - r) -t log-t--, I - r

where e(r)

-4

0 as r -4 I. Therefore, from (3) we arrive at

I a

I ,

Ig(zW d9 ::;;; K1 log - 1-r

+ e(r)a (l 2

, t 1 - r) - 4 log- - - . 1-r

(4)

-a

On the other hand, from Theorem 13.3, we have a

I

n

Ig(zW d9 ~ -

aI

3n

-a

Ig(zW d9

aI

OO

=-

3n k= 1

r 2ak

a 2). = _g(r

3n

-n

From (2) and Theorem 13.4 we have g2(r2) = cr2(1 _ r2) -1 =

cr 2 (l - r 2)-1

+ (l + (I

_ r2)h(r2) - r 2)0(In-}r 2n )

> K(l- r)-l - 0((1- r)l-l)

> K(l

~

r)-l.

Therefore

I a

Ig(zW d9 > K2a(l - r)-4-.

(5)

-a

We take K 2e-1; > 1 + K1 and let a (5), we arrive at

= e-1;(l -

r)tlog(l/l - r). Then from (4) and

which is a contradiction. Our theorem is proved.

D

6.14 Dirichlet Series A Dirichlet series is a series of the form F(s) =

I f(~)n

.

n= 1

Here we call F(s) the generating function of f(n). This book does not discuss the fundamental properties of Dirichlet series. Instead we only deal with the various

144

6. Arithmetic Functions

formulae and their transformations. We do' not even discuss the region of convergence for the series. If fin) is a mUltiplicative function, then F(s)

=

0(1

+f(p) +f(p2) p' p2.

p

+ ... ),

where p runs over all the primes. Also if fen) is completely multiplicative, then F(s)

~

=

(1 _f~)r1

If G(s)

I

=

g(7) ,

n

n=l

then F(s)G(s)

=

I

=

I

f(:)

1= 1

I

00

n= 1

I

1

~ n

g(~)

m= 1

m

(n)

I

f(d)g -d .

din

Therefore F(s)F(s) is the generating function ofIdlnf(d)g(n/d). We can use this to derive Theorem 4.2. Let 00 1 (s) =

I

~.

n This is the famous Riemann zeta function in analytic number theory. We have the product formula n= 1

1

(s) =

~ ( 1 - p'

)-1

(1)

Therefore

(2)

If g(n) is the Mobius transformation offen), then their generating functions G(s) and F(s) are related by G(s) = (s)F(s). The inverse Mobius transform theorem then becomes F(s) = G(s)/(s). We also have 00

dI(n)

n= 1

n

I -. = (2(S),

(3)

145

6.14 Dirichlet Series

and

I n=l

1/t(n)1

=

nS

TI (1 +~) = ry (1- ~) =

ry(1 _;s)

pS

p

((s) .

(4)

((2s)

Taking the logarithmic derivative of (1) we have ('(s) ((s)

= _ " logp -;- pS

= -

I

1

00

I --;;;;

logp

m= 1

p

= _

(1 _pS~)-1 p

I A(~).

n=2

(5)

n

Since 00

logn

I -s' n=2 n

('(s) = -

(6)

these two formulae give a new proof of the Mobius transform relationship between logn and A(n). Now

log~(s) =

-

=I

~ 109( 1 -

I

;s) I A1~n).

~=

p m= 1

mp

n= 1

(7)

n

Also 00

("(s) =

I

log2 n -s.

n

n= 1

From

I

A(n) logn n= 1 nS

=

(('(S))' ((s)

and

I -n1 ( I

(n)) =

00

n= 1

S

din

A(d)A d

("(S))2 -"((s)

,

using ("(s) ((S)

= ~ ('(S) + (('(S))2 ds ((S)

((S)

(8)

146

6. Arithmetic Functions

we arrive at

L: ~(d) log2 ~ = L: A(d) A (~) + A(n) log n. d

din

d

din

The results in §8 can also be expressed as follows. Let

I:

L(s) =

n= 1

X(7) . n

Then we have 00

r(n)

n=1

n

L: -. =

(9)

4L(s)C(s).

In the study of analytic number theory we study the analytic properties of F(s) and use these properties to derive results concerning the function fen). Exercise 1. Discuss the region of convergence for the series in (1) - (9). Exercise 2. Establish the following:

C3 (s)

00

-=

C(2s)

n= 1

C4 (s)

-=

C(2s)

C(s - I) C(s)

=

-

C(s)C(s - a) =

d(n2)

L:00

(d(n»2

n= 1

n'

L: - ~ ({l(n) L.. n= 1

(s>I).

n' '

n' '

00

(TaCn)

!,=1

n

L: -.-,

'

(s> 1).

(s > 2).

s > max(1, a

C(s)C(s - a)C(s - b)C(s - a - b) = C(2s - a - b)

I:

+ 1).

(Ta(n)~b(n),

n= 1

s > max(1,a

n

+ l,b + l,a + b + 1).

6.15 Lambert Series Definition. We call 00

F(x)

=

xn

L: fen) - - n n= 1

1- x

a Lambert series. Here F(x) is the generating function of fin).

(1)

147

Notes

Expanding (l) into a power series we have co

F(x)

=

I

co

f(n)

n=l

I

xmn

m=l

co

=

I

g(n)xn,

n= 1

where g(n) = Idlnj(d). Thus if g(n) is the Mobius transform of j(n), then g(n) is the coefficient of the power series whose sum is the Lambert series generating function of j(n). We now take g(n) = LI(n), giving co

x=

Jl(n)xn

I 11-

(2)

--n°

n=

x

Again, if we take g(n) = ,n, then x nxn=-------;o n= 1 (l - x)2 ' co

I

so that co

cp(n)Xn

n~l 1 -

x

xn = (1 -

(3)

X)2

A similar method gives , x x2 x3 d(n)xn=--+--+--+ ... n= 1 1- x 1 - x2 1 - x3 co

I

(4)

and 3 r(n)xn=4 ( - X- - - -x 3 n= 1 1- x 1- x

Ico

x5 +--5 -'" 1- x

)

.

(5)

Notes 6.1. The present best result on the circle problem is R(x)

=

7tX

+ O(xH+,)

by J. R. Chen [17]. There is a similar result for the Dirichlet's divisor problem (see Yin [65J and G. A. Kolesnik [34J). 6.2. Concerning the ,Q-result with respect to the divisor problem, H. E. Richert [49J has proved the following: Let O(n (n = 1,2,3, ... ) be a complex sequence such that

n:::=;x

148

6. Arithmetic Functions

holds for some (j > O. Then, given any e > 0 and any constant e, the following asymptotic formula cannot hold:

L mn:::;:;:x

OCmOC n

=

x log x

+ ex + O(x}-').

Chapter 7. Trigonometric Sums and Characters

7.1 Representation of Residue Classes Let m be a positive integer. We have seen that the set of integers can be partitioned into residue classes

where As is the set of integers congruent to s mod m. We can define the operation of addition on these residue classes by

s+t u- { s

+ t-m

if s + t < m, if s + t ~ m.

This definition satisfies properties associated with groups. Within the theory of groups there is a representation theory whereby more abstract objects are given concrete representations, and this theory has very useful applications (for example, in electronics). In this section we discuss the method ofrepresentiQ,g residue classes which form an additive group. To replace the more abstract notion of a residue class we assign to each Au a bearing in mind that the representation should have the complex number property that if

eu,

(1)

then (2)

An immediate candidate for such a representation is

The advantages of this representation are: (i) integers belonging to the same residue class are assigned the same number; that is, if u = v + km, then

(ii) if u

+ v = w (modm),

then

150

7. Trigonometric Sums and Characters

After giving this representation the abstract notion of adding residue classes becomes the concrete one of multiplication of complex numbers. Thus it is possible that some results on congruences can be obtained from the results in trigonometric sums. This is the underlying reason for the important place occupied by research in trigonometric sums in the theory of numbers. Let a be any integer. Then

also possesses the properties (i) and (ii), and so there are m different representations. We now prove that there are no other representations. Let '1u be any complex number with the above properties. Then from mu == 0 (mod m) we have '1~ = '10' But '1~ = '10 so that if'1o # 0, then '10 = I and we see that '1u must be an m-th root of unity. If we let '11 = e21tia/m, then

If'1o = 0, then '1u = 0; that is, all the representations are zero which we exclude from our discussion.

Theorem 1.1. We have, according to whether m divides n or not, I

m-l

m

a=O

- L e: = I

0,

or

that is I

m-l

m

a=O

- L

e21tian/m =

I

or

0,

Proof If min, then the theorem is obvious. If m,rn, then m-l

L e: =

I I _

a=O

em J!nn

= O. 0

..

From this theorem we see that the number of solutions to the congruence

o ~ Xv ~ m can be represented by I

m-l

m-l

m-l

m

x,=o

Xn=O

a=O

- L ... L L

I

e 21tia(f(x" ... ,Xn) - N)/m.

After giving this representation the problem of congruence is now given an analytic interpretation. For the system of integers we have:

151

7.2 Character Functions

Theorem 1.2. We have, according to whether n is 0 or not, 1

f e 21[ inX dx = 1 or

O.

D

o

From this theorem we see that the number of sets of integer solutions to the equation

is equal to

L

L

a1 :::;:;:Xl :::;:;:bl

an:::=;xn:::;;b n

fe21[i(f(XI ..... Xnl-NladlX. o

Example l. Fermat's problem is to prove: when k 1

f(

i

e 21[iXk a)2(

x=l

i

~

3,

e- 21[iX k a)dlX = O.

x=l

o

Example 2. Goldbach's problem is to prove: 1

L. e21[iPa)2e-41[iNadlX > O.

f(

p~2N

o

Of course, in these two examples, the new representations do not assist the solutions of the problems. Exercise 1. Let (m, n)

=

I, m-l m-l

S=

L L

~(x)I1(y)e21[iXynlm,

x=o y=o m-l

m-l

x=o

y=o

L 1~(xW = X o,

L II1(xW = Yo·

Show that

7.2 Character Functions We already know that multiplication is closed within a reduced residue system. That is, if

152

7. Trigonometric Sums and Characters

are the residue classes mod m corresponding to (au, m) = 1, then

is still one of these classes. We now ask if there is also a representation for these classes. Definition. By a character x(n) mod m we mean a function on n, defined when (n, m) = 1, and x(n) satisfies the following: 1) x(l) =I 0; 2) If a == b (modm), then x(a) = X(b); 3) x(ab)

=

x(a)x(b).

Sometimes it is convenient to add: if (n,m) > 1, then x(n) = O. Example. x(n) = 1 is clearly a character. We call this the principal character and we denote it by XO. We can deduce from the definition that X(l) = 1, x(n) is also a character, and that the product of two characters is a character. As an example we first take m = p, a prime number. Take g to be a primitive root modp. Then the function Xa(n)

=

e21tiaindn/(p-1)

is a representative because it has the following properties: 1) Xa(l) = 1 =I 0; 2) if n == n' (modp), then indn == indn' (modp - 1), so that 3)

xin)

=

Xa(n'); Xa(nn')

=

e21tiaind(nn')/(p-1)

= e21tia(ind n + ind n')/(p -

1)

More specifically, when p is an odd prime we take a = (p - 1)/2 so that Xt(p-l)(n)

=

e1tiindn

=

(~).

That is the Legendre symbol is a character. From the above we see that there are p - 1 characters modp and it is not difficult to prove that there are only p - 1

distinct characters. We now generalize our discussion to the following:

153

7.2 Character Functions

1) m = pi where p is an odd prime. From Theorem 3.9.1 there exists a primitive root modp', so that if p,rn we can define ind n, that is

n == gindn (modp'). From this we can obtain
= e27tiaindn/'P(pl),

Clearly Xii) = 1, and there exists a character Xl (n)

with the property: if n

= e27tiindn/'P(pl)

i= 1 (modp'), then

XI(n) # 1.

= 2'. 2.1) 1= 1. There is only the principal character. 2.2) I = 2. Besides the principal character there is the character 2) m

x(1)

= 1,

X(3)

= - 1.

2.3) I> 2. By Theorem 3.9.3, when n is an odd prime, there is an integer b such that n == (- 1)t(n-1)5 b (mod 2'), b~ 0. i

We now define

Here a may take two distinct values mod 2 and c may take 2'- 2 distinct values mod 2'- 2, so that there are
has the following property: if Xl,l(n) = 1, then n == I (mod2') or n == - 521-3 (mod 2'). When n == - 52' - 3 (mod 2'), we have XO,I(n) = - I # 1. That is, if n i= 1 (mod 2') then we can select a character XaAn) # 1. 3) The general case. Let m = P't'

... p!s,

Iv> 0,

be the standard factorization for m. Let a character mod p~v be

so that x(n) =

n x(V)(n) v= I

is a character modm. There are thus
(1)

154

7. Trigonometric Sums and Characters

Conversely, if the modulus of a character x(n) is

where k; are pairwise coprime, then there exist characters x;(n) mod k; (i such that x(n) = Xl(n) ... Xv(n).

=

I, ... , v)

In order to understand this we need only prove the case v = 2. From the Chinese remainder theorem, given any n, we can find nl and n2 such that nl == n (modk 1 ),

nl == I

n2 == I

n2 == n (mod k 2).

(modk 1 ),

(modk 2),

We define

and it is not difficult to prove that Xl(n) is a character modk 1 and X2(n) is a character modk 2. From the definition of nl and n2, we have

so that Therefore

Theorem 2.1. The cp(m) characters so constructed are all distinct.

Proof Suppose that

v=l

v=l

From the fact that x(V)(n)/xiV)(n) is also a character modp~v it suffices to prove that if

v=l

is the principal character, then x(V)(n) is the principal character

== I (modp~v), n == a (modp!s),

n

modp~v.

l~v~s-l,

and we see that for all a (ps,./'a),

that is

is) is the principal character modp!s. The theorem is proved.

0

Take

155

7.2 Character Functions

Theorem 2.2. Jfn

=1= 1 (modm), then we can select,Jrom among the cp(m) characters, a x(n) such that x(n) =I 1.

Proof From the hypothesis there must exist a prime pv such that n =1= 1 (modp~v), and from earlier there exists x(V)(n) =I 1. If Jl =I v we take X(I") to be the principal character, and now

n iV)(n)

=

x(n)

v= 1

0

is the required character. Theorem 2.3.

L x(n)

if X = xo, if X =I XO,

= {cp(m), 0,

n

where the sum is over a complete set of residues mod m. Proof The theorem is obvious if X = XO. When X =I XO, there must be an integer a such that (a, m) = 1, and x(a) =I 1. From x(a) Lx(n)

= Lx(an) = Lx(n),

n

n

n

or (x(a) - 1) Lx(n)

= 0,

n

the theorem follows.

0

Theorem 2.4. Let c denote the total number of characters mod m. Then

if n == 1 (modm), if n =1= 1 (modm),

Lx(n) = {c, x 0,

where the sum is over all the characters. Proof From n",(m) == 1 (modm) we deduce that (x(n))",(m)

= 1,

so that the number of characters c is finite. Ifn == 1 (modm), then the theorem is obvious. Ifn =1= 1 (modm), from Theorem 2 there is a character X(a) such that X(n) =I 1. From X(n) Lx(n) x

= LX(n)x(n) = Lx(n), x

x

156

7. Trigonometric Sums and Characters

we have (X(n) - 1) Lx(n) x

= 0,

D

and the theorem is proved.

Theorem 2.5. The total number oj characters is
L x(n) =

{

n

= c,

X

D

L Lx(n) =
n,X

Definition. We call (l) the standardJactorization oja character. More specifically we let x(n,p') =

e21tiindn/q>(pl)

TIpv

(the definition of b is given in Theorem 3.9.3). Let m = 2a p~v be the standard factorization of m. Then any character x(n) mod m has the factorization:

TI (x(n,p~v))
if a = 0, 1,

Pv

(Xl (n, 2'))<0

x(n) =

TI (x(n,p~v))"v,

if a = 2,

Pv

(Xl (n, 2'))"v(X2(n, 2'))"0'

TI (x(n,p~v))"v,

if a

~

3,

Pv

(co

= 0, I,

Exercise 1. If X =I Xo, then for any two positive integers u and v (v

~

u) we have


-

Exercise 2. If (/, m) = 1, then L x(n) x X(/)

=

{
0,

when when

== I

(modm),

n =1= I

(modm).

n

7.3 Types of Characters Definition. A character x(n) modmis said to be primitive if, for every divisor M ofm, < M < m, there exists an integer a satisfying

°

a

== I

(modM),

(a,m) = 1,

x(a) =I 1.

157

7.3 Types of Characters

A character which is not primitive is called an improper character. Example 1. If m > 1, then the principal character modm is improper, since 1 is a divisor of m. Example 2. If m = p, then any non-principal character modp is primitive. Example 3. If m = pi (/ > 1) and p is an odd prime, then a necessary and sufficient condition for the character xin)

=

e 27tia ind n/",(m)

to be improper is that pia. Thus, every improper character mod pi induces a character mod p'- 1. Example 4. m = 2/. If 1= 1, then there is only the principal character. If 1=2, then the non-

principal character x(l)

=

X(3)

1,

= - 1

is primitive. When I ;::: 3, if Xa.in)

= ( - 1yn - 1)a/2 e 27ticb/2'- 2

is an improper character, then Xa,in) = xa.in

+ 2 / - 1)

and the converse also holds. That is n-1

( _ 1)-2- a e27ticb/2·-2

= (_ =

1)ta(n-1 + 2·-1)e27ticb'/2·-2

(_l)ta(n-1)e27ticb'/2.-2,

or c(b - b') == 0

(mod2 /- 2 ),

where the definition of b' is given by n

+ 2 /- 1 == (-

n-1

(mod 2 / ).

1)-2-5b '

From n+2 / - 1 ==n+n2 /-

1

(mod2/)

== n(l + 2 /- 1 ) (mod 2/) == n5 2 ·- J (mod2/), we have

That is, a necessary and sufficient condition for

Xa,in)

to be primitive is that 2,rc.

158

7. Trigonometric Sums and Characters

Let us take a more specific example. When 1=3, n-l

Xa,in) = ( - 1)-2- a+ cb ,

where b = 0, 1, 1,0 when n = 1,3,5,7. If c = 1, then Xa,I(1)

= 1,

Xa,I(5) = - 1,

Xa,I(3)

= - (-

Xa,I(7)

= (- 1)a

l)a,

are primitive characters, and we can simply write them as XO,I(n)

=

(~)

and

Xl,l(n)

=

(~

2) .

When c = 0, a = 1, XI,O(1) = 1, Xl,o(5)

XI,o(3)

= 1,

= - 1,

XI,O(7) = - 1

is an improper character, that is XI,O = ( - lin). In the character representation in §2 we have x(n)

nx(v)(n).

=

If one of the characters x(V)(n) is improper, then x(n) itself is also improper. Conversely, if X(n) is an improper character, then at least one of the characters x(V)(n) is improper. We next investigate the situation under which there is a real valued primitive character. If a character is real, then each of its factor characters is also real. When p is an odd prime, in

the value C v must be a multiple of ({J(P')/2. If this character is also primitive, then from Example 3, I must be equal to 1. Suppose that

is a real character. Then we must have

If this character is also primitive, then from Example 4, we must have I ~ 3. Therefore there can be no real primitive character if I > 3. There cannot be any real primitive character either if I = 1. For if m = 2m', 2,rm', then from n

== n' (mod m'),

(n,m) = 1,

(n',m) = 1

159

7.4 Character Sums

we deduce that n == n' (mod m) giving x(n) = x(n') so that x(n) is improper. Summarizing, the possibility for the existence of real primitive character occurs when

where Pi are distinct odd primes and a = 0,2,3. Moreover, if the character is primitive, then Cv = q>(p)/2 or

(~).

(x(n,p))"Hp-l) = e"iindn =

Thus, if a = 0, then the real primitive character is the Jacobi symbol (n,m)

=

1.

If a = 2, then the real primitive character is n-l ( n )

(- 1)-2- m/4 '

and if a

=

(n,m) = 1,

3, then there are two types of real primitive character:

)~n2 - (m~8) ,

(- 1

1)

n - 1 n - 1 ( __ n ) (_ 1)-2-+-82

m/8

= (_

(n,m)

1)~(n-2)2-9)

=

1,

( _n ) ,

m/8

(n,m)

=

1.

7.4 Character Sums Let m

S(a, X) =

L x(n)e21tian/m. n=1

Theorem 4.1. Let (mt. m2) = 1 and let X be factorized into

where Xl(n) is a character modml and X2(n) is a character modm2' Then

Proof Let n = mln2 + m2nl' Then as nt.n2 run over the complete sets of residues modmt. modm2 respectively, n runs over the complete set of residues modmlm2'

160

7. Trigonometric Sums and Characters

Therefore ml

Sea, X)

=

Xl (m2)X2(ml) L nl

m2

L Xl (ndxin2)e21tia(mln2 +m2 n d/mlm2

=1

n2::::::

1

Thus the study of character sums mod m is reduced to that of character sums to a prime power modulus.

Theorem 4.2. Let m = pl. If pia and X is a primitive character, or if p,ra and X is an improper character (but we exclude the case I = I, X = Xo), then S(a,x)

0.

=

Proof We make the substitution n = x(l

+ pl-ly).

When I ~ x ~ pl-l, p,rx and I ~ y ~ p, the number n runs over the reduced residue system mod i, and conversely. Therefore o

p'-l

P

Sea, X) = L x(x)e21tiaX/P' L x(l

+ pl-ly)e21tiaXY/P.

y=l

x=l p,/'x

If x(n) is improper, then x(l

+ i-ly) = I,

Sea, X) = {

so that

O'

if p,ra,

p L x(x)e21tiax/P',

if pia.

p'-l

x=l

If x(n) is primitive, then there exists u such that x(l from p

+ pl-1U) #

p

x(l +pl-1U)L x(l +i-ly)

= L x(l +pl-l(y+U»

y=l

y=l p

=

L x(l +i-ly), y=l

we have p

L x(l Therefore Sea, X) =

°also.

I; now pia and so

+ pl-ly) = 0.

y=l

0

We shall write T(X) = S(I, X)·

161

7.4 Character Sums

If (a,m)

= 1, then m

x(a)S(a, X)

L x(an)e21tian/m

=

n=l

= S(l,X)· Theorem 4.3. Let

L

Cq(n) = (a,

e21tian/q,

q)= 1

where a runs over a reduced set of residues mod q. Then 1) cq(n) is a multiplicative function of q; that is if (qt. q2) = 1, then Cq,(n)Cq2 (n) = Cq,q2(n);

i 2)

Cpl(n)= {

pl-l,

if iln,

_pl-l,

if pl,tn, pi-lin,

0,

if pl-l,tn;

3)

Proof 1) can be proved by the substitution a = qla2 method described earlier. 2) follows from Cpl(n)

=

3) follows from I) and 2). Theorem 4.4.

pI

p'-'

a=l

a=l

+ q2al

with the familiar

L e21tian/pl - L e21tian/pl-l. D

If x(n) is a primitive character, then

Proof First consider the case m = pl. We have easily

1't'(xW =

't'(X)i(X) p'

=

L

p'

x(n)e21tin/pl

q=l

n=l p'

=

L

pI

x(n)e21tin/pl

L

x(nq)e-21tinq/pl

q=l

n=l p'

=

L x(q)e-21tiq/pl

pI

L X(q) L e21ti(1-q)n/pl. q= 1

n

=1

p,tn

If pl-l ,t(q - I), then from Theorem 4.3, the inner sum on the right hand side in the above is O. We need therefore only examine the situation wh enpl-ll(q - I), that is

162

q

=

7. Trigonometric Sums and Characters

I

+ pl- 1U,

0

~ U ~

P - I. But now clearly p-1

1-c(xW

=

pi - pl- 1

L:

_

i(l + pl- 1 U)pl- 1

u= 1 p

=

L:

pi _ pl-1

i(l + i - 1u).

u= 1

Now if x(n) is primitive, then there exists v such that x(l

i(l + pl-1 V) # 0, 1. From p

p

L:

i(l +pl-1 V)

+ pl-1 V) #

L:

i(l +i- 1u)=

u=l

0, I so that

p

L:

i(l +pl-1(U + v)) =

. u= 1

i(l +i- 1u),

u=l

we have p

L:

i(l + pl-1U) = o.

u= 1

Therefore the case m Theorem 4.1. 0

=

pi is proved, and the general case follows at once from

We see therefore that -c(x) =

evlm-,

lei =

1.

However, the determination of e is no easy matter. For real primitive characters we know much more and in the next section we shall determine e when X is a real primitive character. Theorem 4.5. Let X be a real primitive character. Then, for odd m, we have

-c(X)

=

{± ~

if m == I (mod 4), if m == 3 (mod 4).

±lym Proof This is similar to the proof of Theorem 4.4. If m p

(-C(X))2 =

=

L:

X(q)

q=l

L:

e 21ti (1 +q)n/p = X( - I)p.

n=l

We already have x( - I)

so that the theorem follows.

= ( ~ I ) = ( _ I )p; 1,

0

7.5 Gauss Sums The trigonometric sum m-1

S(n, m) =

p, then

p-1

L:

x=o

e21tiX2n/m,

(n,m) = I

163

7.5 Gauss Sums

is the famous Gauss sum. In this formula the summation can be taken over any complete set of residues mod m. Theorem 5.1. If(m,m') = 1, then

S(n, mm') = S(nm', m)S(nm, m'). Proof Let x

=

my

+ m'z.

Then mm'

S(n, mm') =

L

e21tix2n/mm'

x=l m'

=

m

L L e21tin(my+m'z)2/mm' y= 1 z= 1

=

and hence the result.

m'

m

y=l

z=l

L e21timny2/m' L e21tim'nz2/m

D

We see that in order to evaluate a Gauss sum we need only deal with the case m=pl. Theorem 5.2. Let

b= {

1, 2,

when p is an odd prime, when p = 2.

Then, for 1 ~ 2b, we have

Proof Let x = y

+ p'-bZ. Then, from

2(1- b) ~ I, we have

y= 1 z= 1 pl-d

=

L

pd

L e41tiyzn/pd

e21tiy2n/pl.

y=l

z=l

pl-c;

=

pb

L

e21tiy2n/pl

y=l ply

p'-d-l

=

pb

L

e21tix2n/pl-2.

x=l

When p > 2, this is what is required. When p pl- 3

P

L

x=l

the result also follows.

D

=

2, then from

pl- 2 e21tix2n/pl-2

=

L

x=l

e21tix2n/pl->,

164

7. Trigonometric Sums and Characters

From this theorem we see that the crucial points in the evaluation of a Gauss sum rest on the determination of S(n,2),

S(n,4),

S(n,8)

and p an odd prime.

S(n,p), Theorem 5.3. If 2,rn, then

= 0, S(n,4) = 2(1 + in), S(n,2)

7ti

= 4e4"n.

S(n,8) Proof Clearly we have 2Jti

S(n,2)

= 1 + eTn = 1 - 1 = 0,

S(n,4)

=

S(n,8)

= 2(1 + esn + es4n + es9n )

27ti

1 + eTn

27ti 4

27ti 9

+ eT n + eT n = 1 + in + 1 + in = 2(1 + in), 27ti

2ni

27ti

Theorem 5.4. If p is an odd prime, then

= (;)S(I,P) =

S(n,p)

(;)T(X).

Here x(a)

=

(~).

Proof The number of solutions to the congruence x2

== u (modp)

is

and therefore

±

e27tix2n/p

=

x=1

f (1 + (~))e27tiun/p = f (~)e27tiun/p P P

u=1

= (':.)

p

which is the required result.

u=1

±(~)

v=1

0

P

e27tiv/p,

165

7.S Gauss Sums

Theorem 5.5.

=

S(l,p)

if if

{JP, iJP,

== 1 (mod 4), p == 3 (mod 4). p

Proof From the above theorem and Theorem 4.5 we have S(l,p) =

{±±iJP, JP,

if p == 1 (mod 4), if p == 3

(mod 4),

which, combining into a single formula, gives

t(1 + iP)(l -

i)S(1,p)

=

± JP.

If we can prove that

+ i P)(1

91H(1

- i)S(l,p)} > -

JP,

where 91{x} represents the real part of x, then the theorem will follow. Now itis easy to see that p-1

I

S(1,p) - 1 =

t(p-l)

I

e27tix2jp =

x= I

(e27tix2/p

+ e 27ti(p-X)2/ p)

x= 1

t(p-l)

=

2

I

(1)

e27tix2/p.

x=l

Let j(x) be any function. Then t(p-l)

I

t(p-l)

j(x)

x=l

(p x ) = I f (x) - . p-l

+ I f -x=l

2

x=l

2

This formula clearly holds because the first term on the left hand side is merely the sum of those terms on the right hand side when x is even, and the second term is the sum on the right hand side when x is odd. We take j(x) = e27tix2/p and note that j(~ - x) = iPe27tix2jp. Then, from (1), we have p-l

t(1 + iP)(S(l,p) -

I

1) =

+ Z,

(2)

e27tix2/4P.

(3)

e27tix2/4p = W

x=l

where

W

=

I

e27tix2/4p,

x.;;Jp

Z

I

=

JP<x.;;p-l

From (2) we have

t(1 + i P)(1 Since 91H(l

+ i P)(1

- i)S(l,p) -

t(1 + i P)(l

- i) = (1 - i)(W + Z).

- i)} is 1 or 0, it follows that

91H(l + i P)(l - i)S(1,p)} ~ 91{(1 - i)(W + Z)} ~ 91(1- OW -

filZI.

(4)

166

7. Trigonometric Sums and Characters

From cos x

+ sin x ;::::

1 when 0

9l{(1 - i)W}

~

~

x

n12, we deduce that

nx2 nx2) 1 r L - ( cos+ sin- ;:::: [vPJ;:::: -yp. 2p 2p 2

=

(5)

Jp On the other hand, if we write in Z, x:S;;

nx 2p

= cosec-,

Wx

then (6)

Therefore, from (3) and (6) we have p-l

L

2iZ =

x~q+

(v x -

Vx -

dwx,

1

that is

21Z1

=

Pil

I

viwx -

+ Vp-lWp -

Wx + l )

VqWq+ll

x~q+l

p-l

I

~

(Wx -

Wx+l)

+ Wp + W q + l = 2wq + l

x~q+l

r:

2p q+l

~--~2vp

(because

Wx

(7)

is decreasing). From (4), (5) and (7) we finally have

The theorem is therefore proved.

0

Summarizing we have the following result: Theorem 5.6. If m is odd, then

S(n,m)=

{ (:)fo, fo, .(n)

if m == 1 (mod 4), if m == 3

(mod 4).

1 -

m

Proof We use induction on the number of distinct prime divisors of m. If m = pi, then we have by Theorems 5.2 and 5.4, that I

S(n,p) =

{'

p2,

if 21/,

pt(l-1)S(n,p) =

(~)pt
167

7.5 Gauss Sums

{mi(~)P±' pi.

=

if 2",1,

p=.l

(mod 4),

if 2",1,

p=.3

(mod 4).

Moreover, from Theorem 5.1 and the induction hypothesis, we have S(n, mm')

=

S(nm', m )S(nm, m')

(~)2p = - (nm) - 1.(~)2Fm 2 m'12 m ( nm')

.

m

m'

= (m:,)(:)(:,}(m~lY +(m';l YJmm'

if mm' =. 1 (mod 4), if mm' =. 3 (mod 4). (Here we have used the law of quadratic reciprocity.)

D

Theorem 5.7.

S(n,21) =

r (1

if 1=1

+ i n )2±,

if I is even

1+ 1 ni

2-2-e"4n ,

if I> 1 and odd.

Proof From Theorem 5.3 we see that the result holds when 1= 1,2,3. When I > 3 the result follows from Theorems 5.2 and 5.3. D' Theorem 5.S. Let x(n) be a real primitive character. Then

't"(x)={~ Iym,

if X(-l)=l, if x( - 1) = - 1.

Proof From §3 we know that m can be written as m = 2am', where a = 0, 2, 3 and m' is a product of distinct primes; moreover 1) ifa=O,then x(n) = ( : ) .

(n,m) = 1;

168

7. Trigonometric Sums and Characters

2) if a = 2, then n-l(n) x(n) = ( - 1)-2m' ,

(n,m)

= 1;

3) if a = 3, then x(n) = (_l)t
or

(n,m) = 1.

Here (:) and (;,) are Jacobi's symbols. We now consider the three separate cases. 1) a = O. Let m = PI ... Ps and we use induction on s. When s = 1 the result follows from Theorems 5.4 and 5.5. Let s> 1 and put m = Plm'. Then, from Theorem 4.1 we have

where Xl> X2 have the moduli PI, m' respectively, and x(n) = XI(n)X2(n). Therefore, from Theorem 3.6.4 and the induction hypothesis, we have

{fi:} ifi: . {P} iP ~~ {fi:} {P} ifi: iP

r(x) = ( -m')(PI) - . PI m' = (-

1)

2

2'

•

== 1 (mod 4) if m == 3 (mod 4) 2) a = 2. Let m = 22m'. If m' = 1, then x(l) = 1, if m

{ Jp1m' =Fm, = iJplm' = iFm,

or

X(-l)=l,

or

X( - 1) = - 1.

X(3)

= - 1 so that

4

I

r(x) =

x(n)e21tin/4

= e21ti /4 - e61ti /4 = 2i.

n= I

If m' > 1, then from Theorem 4.1 and 1)

m'-1(4)

r(x) = (- 1)-2- m' 2i

.{P=i

== 1 (mod 4) if m' == 3 (mod 4) if m'

Fm, ip=Fm,

3) a

or

X( - 1)

= - 1,

or

X( - 1)

=

1.

= 3. Let m = 23 m'. When m' = 1, we have B

r(x)=

I

n= I

.

x(n)e 21t1n /B =

{e 21ti /B _ e61ti /B _ el 01ti/8 + eI41ti/8 = j8, if X( - 1) = 1,

.

.

.

.

e21t '/B + e6",/B - el 0",/8 - eI41t ,/8 = ij8, if X( - 1) =

Suppose that m' > 1. If x(n) = (- 1)t
- 1.

169

7.6 Character Sums and Trigonometric Sums

T(X)

= (-

1)~m'2-1)(~,)j8

{P=fo, iP=ifo,

=I m' = 3

if m'

(mod 4)

or

X(-I)=I,

if

(mod 4)

or

X( - I)

If x(n) = (-

I}Hn-l)+~n2-1)(;,), then

= (-

I}Hm'-1)+~m'2-1)(~,}j8

T(X)

.{P=i fo , ip=fo,

= -

1.

if m'

=I

(mod 4)

or

X( - I) = - I,

if m'

=3

(mod 4)

or

X( - I)

Collecting I), 2) and 3) the theorem is proved.

=

1.

D

7.6 Character Sums and Trigonometric Sums We have seen in the previous section the relationship between Gauss sums and character sums. We now proceed to establish certain relationships between trigonometric sums and character sums. Theorem 6.1. Let p be a prime, and dip - I. Then a necessary and sufficient condition for an integer x to be a d-th power non-residue modp is that

~

I

e21tiaindx/d

d a =l

=

o· '

otherwise the formula is equal to I. Proof By Theorem 3.8.1 whether x is a d-th power residue or not depends on whether dlindx or d,rindx. Using trigonometric sums this means that

~ d

I a= 1

e21tiaindx/d

=

{I,

if x is a d-th power residue modp, if x is a d-th power non-residue modp.

0,

D

Theorem 6.2. Let p be a prime, p,ra, (p - I, k) = d. Then d-l

p

I

e21tiaxk/p

x=l

=

I

S(a, l),

b=l

where X(u)

=

= e 21ti ind u/d.

Proof The congruence:x!' u (modp) has either no root, or d Therefore, from Theorem 6.1 we have

=

(p - I,k) roots.

170

7. Trigonometric Sums and Characters

p

I

e 21t ;ax k /p

=

1+

x=1

p-l

I

d

e21tiau/p

u=1

e 21tib ind u/d

b=1 p-l

d

= 1+

I

I I

e 21t ;au/ pi'(u) b=lu=1 p-l d-lp-l = 1 + I e21tiau/p + I I e 21t ;au/ pi'(u) u=1 b=lu=1 d-l = I S(a,i'). 0 b=1

JP so that we have:

From Theorem 4.5 we see that IS(a, i')1 ~ Theorem 6.3. Let d = (k,p - 1). Then

Ixtl e 21t ;ax pI~ (d - l)JP. k

/

Exercise. Study the trigonometric sum m-l I e 21t ;xk n/m, x=O by following Theorems 5.1 and 5.2.

(n,m)

0

= 1·

7.7 From Complete Sums to Incomplete Sums Theorem 7.1. Let g(x) be periodic with period q, and g(x)

={

if if

l,

0,

0 ~ x < m, m ~ x < q.

Then g(x) is representable as 1 q-l g(x) = m + _ I e 21t ;nx/q(l - e- 21tinm/ q)/(l - e- 21tin/q). q q n=1 Proof Clearly 1 q-l

g(x)

=-

I

e 21t ;nx/q

q n=O m 1 q- 1

m-l

I

e- 21tint/q

t=O .

1 - e- 21t;nm/q

= - + - " e21t1nx/q . q q /;;;'1 1 - e- 21t1n /q Theorem 7.2. Let

(J(

be a real number and

S

=

I q'
e 21t ;na.

0

171

7.7 From Complete Sums to Incomplete Sums

Then

lSI::::; min (q" - q', 2<1!y'») ' where
= min(!Y. -

+ 1-

[!Y.], [!Y.]

!Y.).

Proof Clearly we have lSI ::::;q" - q'. If!Y. -:f [!Y.], we let Q = q" - q' so that lSI

=

IQ-lL

e27tina

I= 11 -

e27tiQa . 1 - e 27t1a

n=O

::::;

2

I

1

=---

11 - e 27tia l

Isin n!Y.1

1

~-­

"" 2
(when 0 ::::; ~ ::::;

t, sin n~ ~ 2~, so that Isin n~1 ~ 2< 0).

Theorem 7.3. If2,(q, then

Im-lL

q-lL

I

e27tix2/q - m e27tix2/q ::::; x=o q x=o

Jq log q.

Proof Clearly we can assume that m ::::; q. From Theorem 7.1 we have

m-lL

x=O

e27tix2/q

q-lL q-l =m L =

e27tix2/qg(x)

x=o

e27tix2/q

1

q-l q-lL

+_L

qx=o

e27ti(x2+nx)/q

qn=lx=O

1

-27tinm/q - e . . 1-e 27t1n/q

From the formula for a Gauss sum we have

q-l Ix~o

e 27ti(x 2+nx)/q

I= Iq-l x~o

e27ti(X + tn)2/q 1* ::::;

so that

Iqil

x=o

e27tix2/q _ m

qi

1

e27tix2/q

I

q x=o

q-l ~-L-1

"" Jq n=l 2(~) *

Here

t represents the solution to the congruence 2x == 1 (mod q).

Jq,

172

7. Trigonometric Sums and Characters

I

~-

t(q-l)q

t(q-l)

I

I -=Jq I Jq n=l n n=l n < Jqt('I1)(_IOg(1 -~) + IOg(1 + ~)) n=l 2n 2n t(q-l)

= Jq

I n= 1

+ log(2n + I))

(-log(2n - I)

= Jqlogq.

0

Theorem 7.4 (polya). Let p be an odd prime, I character modp. Then

~

~

m

p, and X be a non-principal

I:t~ X(x) I< Jp logp. Proof From Theorem 7.1 we have

m-l p-l I x(x) = I x(x)g(x) x=o

x=o

m P-

=-

I

1

x(x)

Px=o

IP-l

+- I

x(x)

Px=O

p-l l_e-21tinm/p I e21tinx/p . n=l I-e 21t1n/p

From Theorem 2.3, Theorem 4.4 and Theorem 7.2 we have

m-l I JP-1II -_e-21tinm/p _21tin/p IIP-l I x(x)e21tinx/p I I I x(x) ~ - I x=O Pn=l I e x=O I p-l I ~ r.: I - ( ) < Jplogp. 0 V Pn =12 ~ p

This theorem has the following application: Theorem 7.5. Let p be an odd prime and dl(p - I). Then there is always a d-th power non-residue modp which is less than Jp logp.

Proof Let R represent a d-th power residue not exceeding m. Then R=

where X(x)

=

mid

I

d

m

I - I e 21tia ind x/d = - I I e 21tia ind x/d x=l da=l da=lX=l

e21tiindx/d. From Theorem 7.4, we have d-I r.: IR- dml <-d-vPlogp,

(1)

173

7.7 From Complete Sums to Incomplete Sums

and so

R<

m

r:

d-I

d + -d-vPlogp.

Now if m = JP logp, then

m d-I R<-+--m=m d

d

'

so that a d-th power non-residue less than JP logp exists.

0

In particular there must be a quadratic non-residue less than JP logp. The determination of the smallest exponent c5 such that the least quadratic residue satisfies O(pl» is a famous difficult problem. The result of Vinogradov is:

Theorem 7.6. For sufficiently large p the least quadratic non-residue does not exceed

Proof Let

m

=

JPlog2 p,

and suppose that I, 2, ... , T are all quadratic residues. Since every quadratic nonresidue must have a prime divisor which is also a quadratic non-residue, it follows that every quadratic non-residue not exceeding m must have a prime divisor q satisfying T < q ~ m. Therefore, denoting by N the number of quadratic nonresidues not exceeding m, we have N~

I L [-mJ <m L -, q

T
T
q

and hence, by Theorem 5.9.2, N <

=

m

log _lo_g_m_ log T

m(~ + 2

+0

(_m_) log T

log

I I

+

_4_1~_:g_I:_g_P

)

+0

(_m_)

+ 4Je log logp

log T

logp

= m(~ 2

_

4(Je - 1)IOgIOgp) logp

+ o(~). log T

From (1) we have N

= m + O(JPlogp) = m + o(~) 2

2

~gp

174

7. Trigonometric Sums and Characters

so that m ( -m) -+0 - <m (1-- 4(Je - l)lOglOgp) +0 ( -m-) 2 logp 2 logp logp ,

that is loglogp = 0(1),

0

which is impossible if p is sufficiently large. The theorem is therefore proved.

P (X2 + pax + b) 7.8 Applications of the Character Sum X~1 Theorem 8.1. The number of integers a such that a and a residues mod p is

+ 1 are

both quadratic

Before we prove this theorem we have to evaluate a sum first. Theorem 8.2. Let p >. 2, a 2

-

4b

=1=

0 (modp). Then

±(X2 + + b) ax

1,

= _

p

x=1

where in the formula the value 0 is given to those terms in which plx 2

+ ax + b.

Proof We can assume that a = 0, since otherwise we can use the substitution y = x + a12. Now suppose that p,tb. From Euler's criterion we have

L (X2 -+-b) = L (x P

P

, + b)2(p-l)

(modp). P x=1 Let g be a primitive root of p. If 0 < c < p - 1, then P p-2 1 _ gc(p-l) x< = gCV = C = 0 (modp). x=1 v=o l-g 2

x=1

L

L

Substituting this into (1) yields

L (X2 -+-b) = L x P

x= 1

P

P

P- 1

=

x= 1

=- 1

(modp).

I L (X2-P+-b)1 ~p, x=1

L1

x= 1

Clearly P

p-l

(1)

7.8 Applications of the Character Sum

LP (X2 + ax + b)

x~1

175

P

so that

IP (X2 -+-b) = x=l

P

1 or p - 1.

Since

2 I (X2 -+-b) -_ (b) - +2 !(P-1)(X I -+-b) P

P

x= 1

P

P

x=l

== 1 J(mod2), we have

f (X2 + b)

= _

1.

D

P Proof of Theorem 8.1. The number of integers a with the property stated in the theorem can be represented by x=l

~

:t: (1 + (~))(1 + (a; 1)) ~ :t: (1 + (~) + 1) + =

=~

(a;

(a(a:

1)))

(p _2_(~ 1) _(~) _1)

=~(P_4_(~1)) (because I~= 1 (;) = 0).

D

From Theorem 8.1 we deduce at once: Theorem 8.3. Ifp ~ 2, then there must be a pair of consecutive integers which are both quadratic residues. D Similarly we can prove: Theorem 8.4. The number of integers a such that a and a residues mod p is

+ 1 are both quadratic non-

so ,that, if p ~ 5, then there must be a pair of consecutive integers which are both quadratic non-residues. D

Theorem 8.5. There are t(p - 1) integers a such that a and a quadratic residues nor both quadratic non-residues.

+ 1 are neither both

176

7. Trigonometric Sums and Characters

Proof The theorem follows at once from

Note: The problem concerning three consecutive quadratic residues involves the study of the character sum

xt

e(X

2))

+ ~(X +

which is outside the scope of this book. However, we have the following application of charaCter sums involving cubic polynomials.

== 1 (mod 4).

Theorem 8.6 (Jacobsthal). Let p be a prime equation p

Then a solution to the

= X2 + y2

in integers X, Y is given by 2X = S(r), 2 Y = S(u) where

(~)= 1,

(~)=-l

and S(k)

p-1

L:

=

=

(X(X 2 +

P

x=l

k)) .

Proof Since S(k)

=

t(p- 1)

L:

(X(X 2 + k))

P t(p-1) (X(X 2 +

x= 1

=2

L:

k))

P

x=l

t(p- 1)

+ L:

(p _ y)«p _ y)2

+ k))

P

y= 1

'

we see that X and Yare actually integers. Also, if p,rt, then t)3 ( - S(k) p

Now consider p 1 -=-«S(r))2 2

=L:

+ t 2k))

p-1 (tX«(tX)2

P

x= 1

=L:

p-1 (X(X 2 + t 2k))

t(p-1)

+ (S(U))2) = L:

(S(k)f

k=l

S(t2k).

+ L:

(S(ut2))2

1=1

p-1

L:

=

t(p-1)

(S(rt2))2

1=1

=

P

x= 1

=

p-1 p-1 p-1 (XY(X 2 + k)(y2

L: L: L:

x=l y=l k=l

From Theorem 8.2 we see that the innermost sum here is

={-2(;),

if x ¥=

±y

(modp),

P - 2,

if x ==

±y

(modp).

P

+ k))

.

177

7.9 The Problem of the Distribution of Primitive Roots

Therefore

Pi1(S(k))2 = 2(p -

1)(p - 2) - 2 I

k~l

(Xy)

I

x"±y p (modp)

P-IP-l( ) Y~l ; =

2p(p - 1) - 2 X~l

=

2p(p - 1).

Collecting our results we have

(S(r))2

+ (S(U))2 = 4p. 0

7.9 The Problem of the Distribution of Primitive Roots Theorem 9.1. Let p be an odd prime and p,tn. Ifn is not a primitive root modp, then

i

I klp-l

Jl(k) e27tiaindn/k = O. qJ(k) a~l (a.k)~

(1)

1

Proof The inner sum on the left hand side of (1) is a mUltiplicative function of k, as are the functions Jl{k) and qJ(k). Therefore the left hand side of (1) is equal to

n (1 + Jl(q)

±

qJ(q) a~ 1

qlp-l

(a.q)~

e27tiaindn/q) ,

1

where q runs over the prime divisors of p - 1. If n is not a primitive foot, then (ind n, p - 1) > 1, and so there exists a prime divisor q of p - 1 which divides indn. For this prime number we have

1 + Jl(q) qJ(q)

±

a~l (a.q)~

The theorem is proved.

e27tiaindn/q = 1 + ~. (q - 1) = q- 1

o.

1

0

Theorem 9.2. Let p be an odd prime, 1 ~ A < p. If x(n) is a non-principal character modp, then

-1- I I I A

A

+1

a

a~On~-a

I

A+l x(n) ~pt - t-· P

Proof We already have p-l

I

1"(x)1 = Ih~l x(h)e27tih/p = pt. If p,tn, then

(2)

178

7. Trigonometric Sums and Characters

p-1

L x(h)e21tih/p

x(n}r(x) = x(n)

h=1 p-1

L

= x(n)

x(nh)e21tinh/p

h=1 p-1

L X(h)e21tinh/p. h=1 If we multiply the left hand side of (2) by TW, then =

I L L p-1 L x(h)e21tinh/P I A + 1 a=O n=-a h=1 _ 1 IP~1_ (sin(A+1)nh/p )21 - - - '-' X(h) 1

A

= --

a

A + 1 h= 1

sin nh/p

,

(3)

where we have used the formula

I ±

e21tinh/p

=

a=O n=-a

(sin (~ + 1) nh/p)2 slllnh/p

(4)

the proof of which is not difficult. From (3) and (4) we arrive at

-JP- I LA La A

+

I

1 p-1 (sin (A + 1)nh/p )2 x(n) ~ - - L ---:-.---:-..,.-1 a=O n=-a A + 1 h=1 slllnh/p 1 p-1 A a = - - L L L e21tinh/p A + 1 h=1 a=O n=-a 1=-

LA La (PL e21tinh/p_1 )

+ 1 a = 0 n = - a' = P - (A + 1). 0 A

h= 1

Theorem 9.3. Let h(p) denote the primitive root modp with the least absolute value.

Then

where m is the number of distinct prime divisors of p - 1. Proof Letp > 2. From Theorem 9.1 we have Jl(k)

0=

k

L -- L

Ih(p)l- 1

a

L L'

klp-1q>(k) u=1 a=O n=-a (u,k)= 1

e21tiuindn/\

179

7.9 The Problem of the Distribution of Primitive Roots

where If means that we omit the term n = O. On the right hand side of this equation the term k = 1 is equal to Ih(p)l- 1

I

a=O

a

Ih(p)l- 1

n= -a

a=O

If 1 = I

2a = Ih(p)12 - Ih(p)l·

For those terms in which k -:f 1 we use Theorem 9.2, taking A

I

a

Ih(p)l-l [

=

Ih(p)1 - 1, so that

Ih( )1 2

a~o n~~a x(n) ~ Ih(p)lpt -

;

,

where

Therefore Ih(p)12 - Ih(p)1

~ (lh(P)lpt -

I 1J1((~)1 ({)(k)

2 Ih(P;1 )

p

= 2m (lh(P)lpt

_

klp-l ({)

Ih~;12).

That is Ih(p)1 ~

2mpt

+1

1 + 2m/p

t < 2mpt.

0

From Theorem 9.3 we immediately deduce: Theorem 9.4.

If p == 1 (mod 4),

then we have the primitive root

Proof We have to prove that Ih(p)1 is a primitive root. Suppose otherwise, so that - Ih(p)1 is now a primitive root. But Ih(pW

== 1

(modp),

I