B10 lecture course : Elementary Number Theory

Lectures given by Dr Heath-Brown
Notes taken by Tom Womack, extra material supplied by
Paul Rowe, Duncan Archer and Rob Hladky

October 1996

Table of Contents

1  Introduction

I would like to thank Dr Heath-Brown for giving me permission to publish this set of notes. The copyright in the content is his; the errors in the content are mine. This course is about properties of N, Z and Q; until you get to a much higher level, no analysis pokes its ugly head anywhere near this subject.

2  Properties of Z

Z has a Euclidean algorithm - that is, " a,b Î Z, there is a d with d|a, d|b, s|a, s|b s|d. Moreover, $ a, b Î Z with a a + b b = d.
Corollary 1   Let p be prime. Then p|ab p|a or p|b.


Proof. Suppose p ¬ | a. Then $ d = (p,a), with d|p so p=dd'. But p is prime, so d=1 or d=p. If d=p then d|a by definition of d, but p ¬ | a, so d=1. So $ x,y : px+ay=1. So b=pbx+aby. But p|ab, so ab=pc. So b=p(bx+cy), so p|b.


Theorem 2  [Fundamental Theorem of Algebra]   Every n Î N can be written as a product of increasing prime numbers in exactly one way.
There are two parts to this theorem; that every n can be written in this way, and that the expression is unique. For the first part, let n be the smallest number which can't be written in that way. Then n is composite (since primes are already written in that way), n=pq with n > p,q >1. But p and q are <n, so can be written as products of primes; concatentate the expressions. For the second part, assume that n is the smallest integer with two or more representations :
n = p1e1 p2e2 ... pkek = q1e1 ... qsrs.
If p1 = q1 then n/p1 = n/q1 - but n/p1 factorises uniquely. So p1 ¹ q1. WLOG p1 < q1. Now, p1 | n p1 | q1r1 ... qsrs. Apply the corollary repeatedly until we have p1 | qi. But qi is prime, and, by ordering, qi ³ q1 > p1. Contradiction.
Corollary 3   Let a,b be coprime positive integers. Then ab is a square iff a and b are both squares.


Proof. Let ab=c2, and p1 ... pn be all the primes which divide any of a, b or c. Write a = Õpiei, b = Õpifi, c=Õpigi with ei, fi, gi ³ 0. Now ei + fi = 2gi by definition of multiplication. But, since a and b are coprime, ei and fi are never both non-zero. So ei=2gi or fi=2gi, so a and b are both squares.


This concept doesn't hold universally; for example, over Z [ exp(2ip / 23) ], ab=c23 doesn't mean both a and b are 23-rd powers.

2.1  Prime Numbers

It's very easy to make long lists of prime numbers, using the Sieve of Eratosthenes for example (erase multiples of 2 which are ³ 4, multiples of 3 which are ³ 9 ...).
Theorem 4   There are infinitely many primes


Proof. Assume there are only finitely many primes. Multiply them together and add 1 to get l. If l is prime, it's a prime not on the list; if it's composite, it's divisible by a prime not on the list.


Theorem 5   There are sequences of n consecutive composites for every n


Proof. N!+2 ... N!+N, for N=n+1.


A corollary of 4 is that pn+1 £ Õi=1n pi + 1. It's a lousy estimate, though. At this point, one of the major features of number theory appears; there are an awful lot of unsolved problems about, and a vast number of statements which are easy to make and horrific to prove. For example, we don't know if there are infinitely many primes of the form n!+1, or infinitely many of any prime constellation (for example the twin primes). The answers should be `yes' and `yes', but no-one has the proof. There are earlier sequences of consecutive composites for n; Marek Wolf conjectured in a recent paper that the first set of n composite numbers appears around n exp( n). We define p(x) as the number of prime numbers £ x. For example, p(103)=168, p(104)=1229, p(106)=78498, p(108)=5761455. p(x)/x is decreasing, but only slowly (roughly as 1/logx).

2.2  Estimating p(x)

Theorem 6  [the Prime Number Theorem]   p(x) log x/x ® 1 as x ® ¥
Definition 7   If f(x), g(x) > 0 " x, and f(x)/g(x) ® 1 as x ® ¥, we write f(x) ~ g(x).
So the Prime Number Theorem can be written as p(x) ~ log x/x. There is a better approximation obtained by p(x) » ò2x 1/logt dt; unfortunately, 1/logt can't be integrated using normal functions. Whilst p(x) > x/logx always, p(x)<Li(x) for small x. This is with `small' meaning '<1018'; Littlewood proved that p(x) > Li(x) for infinitely many x, and Skewes showed that the smallest such x was less than 10101034. Fortunately, modern results suggest that x<101700. It's unlikely that x will ever be found, since it's unlikely that x<10500. The Prime Number Theorem was first proved in 1896; there is still no easy proof, though there's one in Hardy and Wright which is merely fiddly rather than actively incomprehensible.

2.3  Corollaries of PNT

Theorem 8   pn ~ n logn


Proof. Recall that p(pn)=n. By theorem 6, n ~ pn/logpn, so n logpn ~ pn. We want to show, therefore, that logpn ~ logn. We know that pn ³ n, so the fraction is always ³ 1. However,
n logpn ~ pn
n logpn
pn
³ 1/2
for large enough n. If e is given, logx £ xe for large enough x, so logpn £ pne for n large enough. So n pne/pn ³ 1/2 for n big enough, so pn1-e £ 2n, and (1-e)logpn < log2n. So
logpn
logn
£
1
1-e
log2n
logn
,
and this tends to 1 as n ® ¥, e ® 0.


Corollary 9   pn < n2 for n big enough, since pn £ 2n logn and 2n logn £ n2
It's not known whether there is always at least one prime between n2 and (n+1)2, though it seems likely. There is always at least one prime between consecutive cubes, though. You can model the sequence of primes well by assuming that primes near x occur following a Poisson process with parameter (logx)-1.

3  Congruences

We write a º b (mod n ) iff n | (b-a). This is an equivalence relation for fixed n. You can add, multiply and subtract congruences, but you can't always divide them (2 º 8 (mod 6 ), but 1 ¬ º4 (mod 6 )). This is just another way of writing arithmetic in Z / nZ; it means you can work with smaller numbers, so you can check that 230 º (25)6 º (-1)6 º 1 (mod 31 ) without ever having to know that 230=1073741824.

3.1  Linear Congruences

You might want to know when you can solve a linear equation like ax º b (mod m ). Start off by noticing that, if d|a and d|m, d | ax-b (since ax-b = km), so d|b. So a necessary condition is that (a,m)|b. If this holds, set d=(a,m), so the equation becomes dAx º dB (mod dM ); we can now divide through by d, since it's not coprime to the modulus, to get Ax º B (mod M ), with (A,M)=1. We can go further, in fact; if we can solve Ax º 1 (mod M ), we have AxB º B (mod M ). So what we need is
Theorem 1   If (a,m)=1 then the congruence ax º 1 (mod m ) always has a solution, and it is unique modulo m.


Proof. (a,m)=1, so, using the Euclidean algorithm, we can find y,z with ay+zm=1. So m | zm = 1-ay, so ay º 1 (mod m ). For uniqueness, suppose that ax º ax' º 1 (mod m ). Then ax º ax', so m|a(x-x'). But (a,m)=1, so m|(x-x'), so x º x' (mod m ).


So we can solve single linear equations. An obvious next question is how far we can get solving multiple linear equations; simultaneous equations to the same modulus are fairly straightforward using the standard elimination methods, but it would be nice to be able to handle several equations to different moduli.

3.2  Simultaneous congruences

Theorem 2  [Chinese Remainder Theorem]   If m1, ..., mk are coprime in pairs, the simultaneous congruences x º b1 (mod m1 ), ..., x º bk (mod mk ) have a unique solution mod M = Õi=1k mi.
Note that there need not be a solution if the mi aren't coprime in pairs; x º 1 (mod 4 ), x º 3 (mod 8 ) is clearly impossible.

Proof. We need to prove existence and uniqueness.
  1. Let M = mi ni (eg n3 = m1 m2 m4 ... mk). Then (mi,ni)=1, since the mi are coprime in pairs, so, by theorem 1, we can solve ni xi º 1 (mod mi ) for each i. Now, let
    x = x1 n1 b1 + ... + xk nk bk.
    Working modulo each mi in turn, we have mi | nj for j ¹ i, so the only term left is xi ni bi = bi by definition of the xi. So x satisfies the simultaneous congruences.
  2. Suppose x' º bi (mod mi ) for all i. Then x' º x (mod mi ) " i since both º bi. So mi | x'-x. But the mi are pairwise coprime, so Õmi | x'-x, so x' º x (mod M ).



Example 3   We solve 10x º 2 (mod 26 ), 7x º 3 (mod 20 ). (26,20) ¹ 1, but (10,2,26)=2, so we can convert the first equation to 5x º 1 (mod 13 ). To apply the Chinese Remainder Theorem, we must start off by reducing the equations to the form x º bi (mod mi ). So we solve 5b1-1=13y getting b1=8, and we solve 7b2-3=20y, getting b2=9. Now, we see that mi = n3-i (that is, there are only two factors so the cofactor in each case is the other one). So we solve 20x1 º 1 (mod 13 ), getting x1=2, and 13x2 º 1 (mod 20 ), getting x2 = 17. And, by the Chinese Remainder Theorem, we have x º n1 x1 b1 + n2 x2 b2 º 20 · 2 · 8 + 13 · 17 · 9 º 2309 º 229 (mod 260 ).

4  Arithmetic Functions

4.1  Arithmetic Functions

Definition 1   An arithmetic function is a function from N to C (often from N to N).
Examples of arithmetic functions include obvious ones like the polynomials, and also some less usual ones : d(n), the divisor function, which is |{k Î N : k|n}|. s(n) = åk|nk w(n), the number of prime factors of n f(n), the Euler function, which is |{k Î N : k<n, (k,n)=1}|.

4.2  Multiplicative functions

Definition 2   We say that an arithmetic function is multiplicative if f(mn) = f(m) f(n) whenever m,n Î N and (m,n)=1.
For example, d is multiplicative, whilst w isn't (since w(2)=1, w(3)=1, w(6) = 2 ¹ 1.
Theorem 3   f is a multiplicative function


Proof. f is the number of invertible elements in Z / nZ. Let a run over a complete set of invertible elements mod m, and b do the same mod n. So there are f(m) a's, and f(n) b's. We want to show that, if (m,n)=1, am+bn runs over a complete set of invertible elements mod mn. This would imply f(mn)=f(m)f(n). So we need to show that
  1. am+bn º a'm+b'n a=a', b=b'. Working mod m gives bn º b'n, so b=b' since (n,m)=1; repeating the argument backwards gives a=a'.
  2. (an+bm, nm)=1. (an+bm,m) = (an,m) = 1 since a and n are each coprime to m. Similarly, (an+bm,n)=(bm,n)=1. So (an+bm, nm)=1.
  3. If c is invertible mod mn, $ a,b : c º am+bn (mod mn ). But mx º c mod n is solvable since (m,n)=1; let b be a solution. If d>1 divides both b and n, d|c, so (c,n)>1, so (c,mn) ¹ 1. So (b,n)=1. Similarly to get (a,m)=1. Now am+bn º am º c (mod n ), and am+bn º bm º c (mod n ). So the numbers are congruent mod m and mod n, so mod mn.



Corollary 4  
f(n) = n
 
Õ
p|n
(1-1/p).


Proof. f(pe) is the number of integers < pe without a factor p, so is pe (1-1/p). The result follows by multiplicativity.


4.3  Making multiplicative functions

Theorem 5   If f is multiplicative, then g(n) = åd|n f(d) is multiplicative.


Proof. g(mn) = åd|mn f(d). If u and v run over the divisors of m and n respectivly, then d=uv runs over the divisors of mn, if (m,n)=1 : If uv=u'v', then u|u'v'. But u|m, v'|n (u,v')=1, so u|u'. Similarly, u'|u, so u=u', v=v', so all the uv are different. uv|mn trivially (since (m,n)=1). If a | mn, set u=(a,m) and v=a / u. Then a = uv, and a | mn a/u | mn/u. But d/u and m/u are coprime, so a/u divides n. So v|n, u|m.


This produces a number of new multiplicative functions : f(x)=1 gives the divisor-counting function d, so that's multiplicative. f(x)=x gives the sum of the divisors, so s is multiplicative. Any multiplicative function can be given a direct form in terms of the prime factorisation of the argument :
d(p1e1 ...) = (e1+1)(e2+1) ...,
s(p1e1 ...) = Õ
piei+1-1
pi-1
.

4.4  Perfect Numbers

Definition 6   n Î N is perfect iff s(n)=2n. If s(n)<2n, n is called deficient; if s(n)>2n, n is called abundant.
That is, the sum of the proper divisors of a perfect number is the number itself. Some perfect numbers are 6, 28, 496, 33550336 and 260 · (261-1). It is an open question whether there are infinitely many perfect numbers (though the answer is clearly `yes'), and whether there are any odd ones (where the answer is less clear); these are probably the oldset well-defined unanswered questions. Euclid proved that, if p=2n-1 is prime, then p · (p+1)/2 is perfect; such primes are called Mersenne primes, and it's an open question as to whether there are infinitely many of them. 36 are currently known, the largest being 22976221-1.
Theorem 7   If n=ab with a,b ³ 2 then 2n-1 is composite


Proof. 2n-1 = xb-1 for x=2a; xb-1 factors algebraically as (x-1) (xb-1+xb-2 ... +1).


Theorem 8   If q | 2p-1 with p,q prime, then q º 1 (mod 2p ).


Proof. Consider the group of order q-1 of the non-zero residues mod q. By Lagrange's theorem, 2q-1 º 1 (mod q ). Now, 2p º 1 (mod q ), since q|2p-1. Now, if p ¬ | q-1, (p,q-1)=1 so $ x,y : px+(q-1)y=1. But then 2px 2q-1y º 21 º 1x 1y = 1, which is a contradiction. So p | q-1, so q º 1 (mod p ). q º 1 (mod 2p ) since q is prime, hence odd.


Theorem 9  [Euler]   Every even perfect number is of the form 2p-1 (2p-1).


Proof. An even n is of the form 2e b with e ³ 1 and b odd. Now, s(n) = s(2e) s(b) since s is multiplicative and (2e,b)=1 since one has only factors of 2 and the other is odd. So s(n) = s(b) 2e+1-1. So, for n to be perfect, we require
2e+1b = (2e+1-1) s(b).
So 2e+1 | s(b), so s(b) = 2e+1k, which means b=(2e+1-1)k. If k>1 then, since 1, k and b are all divisors of b, s(b) ³ 1+b+k > k+b = 2e+1k = s(b). Oops. So k=1, b=2e+1-1, and s(b)=2e+1 - so b must be prime.


So any even perfect number is of Euclid's form. No-one's ever seen an odd perfect number, but you can prove results about them anyway :
Theorem 10   Any odd perfect number has at least three prime factors


Proof. Suppose n = p1e1 p2e2, where p2 might be 1. Then
s(n) = Õ æ
ç
ç
è
piei+1-1
pi-1
ö
÷
÷
ø		 < Õ
piei+1
pi+1
= Õpiei Õ
pi
pi-1
= n Õ
pi
pi-1
.
So 2 = Õi=1k pi (pi-1)-1. Write Pi for the ith odd prime number. Assume Pi are written in ascending order, so pi ³ Pi. So 2 < Õi=1k pi/pi-1. But this is impossible if k=1 or k=2, since the product is too small. Increasing k might produce good results after a bit of searching.


In fact, it's known that any odd perfect number has at least eight prime factors.

4.5  The Möbius Function

We define µ(1)=1, and
µ(p1e1 ... pkek) =
ì
í
î
(-1)k ei=1 " i
0 $ i : ei ³ 2
The function is multiplicative by definition, and equal to zero at any power or number divisible by a power.
Theorem 11   åd|n µ(d) = 0 unless n=1, whereupon it equals 1.


Proof. µ(d) is multiplicative, so f(n) = åd|n µ(d) is multiplicative. But f(pk) = µ(1) + µ(p) + µ(p2) ... = 1 - 1 + 0 + 0 .... So f is 1 iff n=1.


This function is important because of the following
Theorem 12  [The Möbius Inversion Theorem]   If G(n) = åd|n F(d), then
F(n) =
 
å
d|n
µ(d) G(
n
d
) =
 
å
d|n
G(d) µ(
n
d
).


Proof.
 
å
d|n
µ(d) G(
n
d
)
=
 
å
d|n
µ(d)
 
å
c|
n
d
f(c)
                 
=
 
å
cd|n
µ(d) f(c)
                 
=
 
å
c|n
f(c)
 
å
d|
n
c
µ(d) = f(n)
                 



Theorem 13   If f(n) = åd|n µ(d) g(n/d), then g(n) = åd|n f(d).


Proof.
 
å
d|n
f(d)
=
 
å
d|n
f(
n
d
)
                 
=
 
å
d|n
å
c|
n
d
µ(
n
cd
) g(c)
                 
=
 
å
cd|n
µ(
n
cd
) g(c)
                 
=
 
å
c|n
g(c)
 
å
d|
n
c
µ(
n
cd
) = g(n)
                 



Theorem 14   åd|n f(d) = n.
We will present three different proofs of this

Proof.[Using multiplicativity] f is multiplicative, so f(n) = åd|n f(d) is also multiplicative. And
f(pe) = f(1) + f(p) + ... + f(pe) = 1 + (p-1) + p(p-1) + ... + pe-1(p-1) = pe.
So f(n)=n " n.




Proof.[Using the inclusion-exclusion principle] Let m=p1e1 ... pkek. Then
f(m)
= m · 1-
1
p1
· 1-
1
p2
...
                 
= m - é
ê
ê
ë
 
å
i£ k
m
pi
ù
ú
ú
û		 + é
ê
ê
ë
 
å
i<j£ k
m
pipj
ù
ú
ú
û		 + ... + (-1)k
m
p1p2... pk
                 
=
 
å
d|m
m
d
µ(d)
                 
=
 
å
d|m
dµ(
m
d
)
                 
                   
So, by theorem 13, m = åd|m f(d).




Proof.[Counting by (m,n)]
n = |{ m Î N : m £ n }|.
We'll group the m's according to the value of (m,n), giving
n=
 
å
d|n
|{ m Î N : m £ n, (m,n)=d }|.
Now, if m £ n and (m,n)=d, we have m=rd and n=sd with (r,s)=1. So
n =
 
å
d|n
|{ r Î N : r £ d, (r,d)=1 }| =
 
å
d|n
f(d)



This is quite a useful result, because it tells you that f is in some sense the inverse of n.
Theorem 15  
 
å
d|n
d(
n
d
) f(d) = s(n)


Proof. Note that d(k) = åd|k 1 = åuv=k 1. So we have
 
å
d|n
d(
n
d
) f(d) =
 
å
d|n
f(d)
 
å
uv =
n
d
1
=
 
å
duv=n
f(d)
                 
=
 
å
v|n
 
å
d|
n
v
f(d) =
 
å
v|n
n
v
= s(n).
                 



5  Congruences to prime moduli

For p prime, Z / pZ is not merely a ring but a field. It has p elements, and the non-zero ones for a group of order p-1 under multiplication. Applying Lagrange's Theorem gives np-1 º 1 (mod p ) if p ¬ | n, which is called Fermat's Little Theorem or FLT. In general, if n is composite, the residues coprime to n will form a group of order f(n) under multiplication, so af(n) º 1 (mod n ) whenever (a,n)=1. This is called Euler's Theorem.

5.1  The multiplicative group of Zp is cyclic

Lemma 1   If au º 1 (mod n ), av º 1 (mod n ) and (a,n)=1 then a(u,v) º 1 (mod n )


Proof. au º 1 means that the order of a has a factor u; av º 1 means that it has a factor v, so it has a factor (u,v).


Lemma 2   If e | p-1, then there are exactly e solutions to xe-1 º 0 (mod p ).
Note that this only works for prime p; x2-1 º 0 (mod 8 ) has four roots.

Proof. A polynomial of degree d has at most d roots over any field, so we need to prove the polynomial has at least d roots.
p-1 = ef xp-1-1 = (xe-1)(xef-e + xef-2e + ... + xe + 1).
But xp-1=1 by Fermat's little theorem. But the first factor has at most e roots, and the second at most e(f-1) roots. But e+e(f-1) = p-1, so both factors must have their full complements of roots. In particular, xe-1 has e roots.


Theorem 3   If e | p-1 then there are precisely f(e) elements of order e in the multiplicative group mod p.
Again, this only works for prime p; there are no elements of order 4 in the multiplicative group modulo 8.

Proof. We work inductively. For e=1, there is 1 element of order 1. xe º 1 (mod p ) |x| | e. There are exactly e elements with order dividing e, by lemma 2; let f(d) be the number of order-d elements, so åd|e f(d) = e. Now f(d) = f(d) for all d<e, by the inductive step, so åd|e f(d) = åd|e f(d) = e. Comparing terms in the series gives f(e)=f(e).


As a corollary to this result, we have that the multiplicative group of Zp is cyclic with f(p-1) generators, which we call the primitive roots of Zp.

5.2  A very bad primality test

Theorem 4   xp-1 - 1 º (x-1)(x-2) ... (x-(p-1)) (mod p )


Proof. Both sides are polynomials of degree p-1 with the same roots, so must be equal to within a constant term, and comparing the coefficient of xp-1 gives the constant term equal to 1.


Putting x=0 in the above gives (since p is odd)
Theorem 5  [Wilson's Theorem]  
-1 º (-1)p-1 (p-1)! º (p-1)! (mod p )
This in fact gives a (totally useless) test for primality :
d|n d|(n-1)! (n-1)! ¬ º-1 (mod n ),
so (p-1)! º -1 (mod p ) iff p is prime.
Theorem 6   Let s be the sum of the primitive roots mod p. Then s º µ(p-1) (mod p ).


Proof. Let g be a primitive root. Then the f(p-1) primitive roots will be gn, where n Î [1, p-1] with (n,p-1)=1. Define f(n) to be 1 iff (n,p-1)=1. Then s = ån=1p-1 f(n)gn. But we can also write f(n) as åd | (n,p-1) µ(d), by theorem 11. So
s =
p-1
å
n=1
gn
 
å
d | (n,p-1)
µ(d) =
 
å
d | p-1
µ(d)
 
å
d|n, n Î [1,p-1]
gn.
Write s(d) =åd|n gn, so s = åd|p-1 µ(d) s(d). If d=p-1, s(d) = gp-1 º 1 (mod p ). If d < p-1, we have
s(d) º
p-1
d
å
m=1
gmd =
(gd)
p-1
d
+ 1
 
- gd
gd-1
by the formula for the sum of a geometric progression. But gp+1-d-gd = gd-gd º 0 (mod p ), and gd-1 ¬ º0. So p | s(d) since it divides the numerator and not the denominator, and s(d) is an integer. So s(d) º 0 for d<p-1, so s º µ(p-1) gp-1 = µ(p-1).


5.3  The multiplicative group of Z / pnZ is cyclic for p ³ 3

We extend the definition of `primitive root' such that a primitive root of pn is a generator of the multiplicative group mod pn.
Theorem 7   The multiplicative group (mod pn) is cyclic if p ³ 3. In fact, there is a g which is a primitive root for pr " r.


Proof. The proof proceeds in three steps :
  1. $ g, a primitive root mod p, such that gp-1 ¹ 1 (mod p2 ). Let g1 be any primitive root mod p. Unless g1p-1 º 1 (mod p2 ), we can take g=g1. If g1p-1 º 1 (mod p2 ), consider g = g1+p. This is still a primitive root mod p, and
    gp-1
    = g1p-1 +
    æ
    è
    p-1
    1
    		ö
    ø
    		g1p-2p +
    æ
    è
    p-1
    2
    		ö
    ø
    		g2p-3p2 ...
    		                 
    º 1 + (p-1) g1p-2 p (mod p2 )                  
    ¬ º1 (mod p2 )                  
    since p2 does not divide p(p-1)g1p-2.
  2. For such a g, g(p-1)pr ¬ º1 (mod pr+2 ) for r ³ 0 For this bit, we work by induction on r. r=0 is given by the previous part. g(p-1)pr = gf(pr+1) º 1 (mod pr+1 ), by Euler's theorem, so g(p-1)pr = 1 + lpr+1. By induction, we have that the left-hand side ¬ º1 (mod pr+2 ), so p ¬ | l. So
    g(p-1)pr+1 = (g(p-1)pr)p = (1+pr+1l)p                  
    = 1 + pr+1l
    æ
    è
    p
    1
    		ö
    ø
    		+ ...
    		                 
    º 1 + pr+2l (mod pr+3 )                  
    since pr+3 | (pr+1l)k
    æ
    è
    p
    k
    		ö
    ø
    for k ³ 2.
  3. Such a g is a primitive root mod pt for all t ³ 1. Let the order of g mod pt be m. Then gm º 1 (mod pt ), so in particular gm º 1 (mod p ), so g is a primitive root mod p and p-1 | m. Also, gf(pt) º 1 (mod pt ), so m | (p-1)pt-1. Write m = (p-1)k, where k | pt-1. Then either k = pt-1, in which case m = (p-1)pt-1 = f(pt) and g is a primitive root of pt, or k | pt-2, whereupon m | (p-1)pt-2, so g(p-1)pt-2 º 1 (mod pt ), which contradicts part ii.



5.4  Non-linear congruences

Theorem 8  [Chevalley, 1936]   Let f(x1, ..., xn) be an integer polynomial of total degree d. Then, if n>d, the number of solutions of f(x1, ..., xn) º 0 (mod p ) is a multiple of p.
Corollary 9   If f has zero constant term and n>d, there is a solution other than xi º 0. For example, a quadratic form in more than two variables has a non-trivial zero (mod p ).
To prove this theorem, we start with the following
Lemma 10   åx=0p-1 xn º 0 (mod p ) for 0 £ n < p-1.


Proof. If n=0 then the sum is equal to p, so º 0 (mod p ). Otherwise, the non-one xi are equivalent to gri in some order, where g is a primitive root. So
p-1
å
i=1
xn =
p-1
å
i=1
gnri =
p-1
å
i=1
gni =
gnp-gn
gn-1
.
The numerator is gn((gn)p-1-1), which is º 0 (mod p ); the denominator is not divisible by p since n < p-1, so the fraction (which is an integer) is divisible by p so º 0 (mod p ).




Proof.[Proof of 8] 1-f(x1,...,xm) p-1 º 1 if f º 0 (mod p ), and 0 otherwise. So the number of solutions to the equation is
 
å
x1, ...,xn
[1-f(x1, ..., xn)p-1] (mod p ).
Now, expand fp-1 to get terms of the form c x1e1 ... xnen, of total degree £ d(p-1), which is < n(p-1). So some exponent must have ei0 < p-1. The contribution from this term is
c
p-1
å
x1=0
p-1
å
x2=0
...
p-1
å
xn=0
x1e1 ... xnen = c
p-1
å
x1=0
x1e1 ...
p-1
å
xn=0
xnen.
By the lemma, the i0th factor is zero modulo p, so that term contributes 0 modulo p, so the whole sum is 0 modulo p.


6  Quadratic Residues

6.1  Solving Quadratic Equations

When can we solve x2 º n (mod p )? It's clearly not always possible; the only remainders given by a square modulo 7 are 0,1,2,4.
Definition 1   Let p be an odd prime. If p ¬ | n and x2 º n (mod p ) is solvable, we say that n is a quadratic residue of p. If p ¬ | n and the congruence is not solvable, we say n is a quadratic non-residue. If p|n, n is neither.
We summarise this definition with the Lagrange symbol :
æ
ç
ç
è
n
p
ö
÷
÷
ø		 =
ì
í
î
+1 residue
-1 non-residue
0 p|n
Note that, if m º n (mod p ),
æ
ç
ç
è
m
p
ö
÷
÷
ø
=
æ
ç
ç
è
n
p
ö
÷
÷
ø
.
Theorem 2   If p ³ 3 then there are p-1/2 residues and p-1/2 non-residues. So ån=1p
æ
ç
ç
è
n
p
ö
÷
÷
ø
= 0.


Proof. We will show that the mapping n ® n2 is a bijection between the numbers between 1 and p-1/2 and the quadratic residues.
  1. If n2 º m2 (mod p ), p | m2-n2 = (m-n)(m+n). m+n < p, so we have p | m-n and m º n (mod p ).
  2. If r is a quadratic residue then s2 º r (mod p ) for some s. s ¹ 0 since 0 is not relevant in this context; if s £ p-1/2 then we send s to r, if not we send p-s to r.



6.2  Ways of finding
æ
ç
ç
è
n
p
ö
÷
÷
ø

Theorem 3  [Euler's Criterion]  
æ
ç
ç
è
n
p
ö
÷
÷
ø
º n(p-1)/2 (mod p )


Proof. If p|n, then the left- and right-hand sides are equal. If n º x2 (mod p ), then p ¬ | x and n(p-1)/2 = xp-1 º 1 =
æ
ç
ç
è
n
p
ö
÷
÷
ø
. Now, x(p-1)/2 º 1 has at most p-1/2 roots; we have found exactly that many, namely the quadratic residues, so there can be no more. And, letting m = x(p-1)/2, we have m2 = xp-1 º 1 (mod p ), for which we know two roots ± 1. So m º ± 1 (mod p ) -- and we know m ¬ º+1, so m º -1 =
æ
ç
ç
è
n
p
ö
÷
÷
ø
.


Corollary 4  
æ
ç
ç
è
a
p
ö
÷
÷
ø		 æ
ç
ç
è
b
p
ö
÷
÷
ø		 = æ
ç
ç
è
ab
p
ö
÷
÷
ø		 .
So the product of two residues or two non-residues is a residue; the product of a non-residue and a residue is a residue.
Corollary 5  
æ
ç
ç
è
-1
p
ö
÷
÷
ø		 = (-1)(p-1)/2 =
ì
í
î
+1 p º 1 (mod 4 )
-1 p º -1 (mod 4 )
So x2+1 º 0 (mod p ) is solvable if p º 1 (mod 4 ), not if p º -1 (mod 4 ).
Definition 6   The least positive residue of m (mod p ) is the unique n Î N with m º n (mod p ) and m<p.
Definition 7   If x Î R, define [x] = max{n Î N : n £ x}.
Then the least positive residue of m is m-p[m/p].
Theorem 8  [Gauss' Lemma]   If p ¬ | n, then
æ
ç
ç
è
n
p
ö
÷
÷
ø
= (-1)n, where n is the number of integers in [1,p-1/2] for which the least positive residue of mn exceeds p/2.
For example, consider
æ
ç
ç
è
4
11
ö
÷
÷
ø
. We take m=1,2,3,4,5, mn=4,8,12,16,20, mn º 4,8,1,5,9, so n=2 and
æ
ç
ç
è
4
11
ö
÷
÷
ø
= 1.

Proof. Consider the numbers mn, reduced to lie between - p/2 and p/2 (by subtracting p from the numbers > p/2 in the list). This produces a list of remainders r1, ..., rµ, s1, ..., sn, where 0 £ ri,sj < p/2 and µ + n = p-1/2. If any of the ri or sj are zero, then p | mn, which is impossible since p ¬ | m, p ¬ | n. So 1 £ ri,sj £ p-1/2. We claim that the ri and sj are all different. If ri=rj or si=sj, then we have mn º m'n for some m,m', so, since p ¬ | n, m º m'. If ri = sj, then ri º mn, p-sj º m'n, so mn+m'n º ri + p - sj º 0 (mod p ), so p | (m+m')n, which is impossible since p ¬ | n and m+m' < p. So ri, sj are a rearrangement of 1 ... p-1/2. Now,
p-1
2
Õ
m=1
mn = n