Elementary Number Theory
August 17, 2011

## 1. Principal Ideal Domains and Unique Factorization Domains

In these notes a ring R will be assumed to be an integral domain and R* will denote the nonzero elements of R. That is, R is a commutative ring with identity such that if a,bR and ab=0, then a=0 or b=0. Note that, in R, you can ”divide out” an element in the sense that if a,b,cR, a0, and ab=ac, then ab-c=0, so, since a0, we have b-c=0 or b=c.

###### Definition 1.1.

R is a Euclidean domain if there is a function

 λ:R*→ℕ

such that if a,R and bR*, then there are elements q,rR with a=qb+r and either r=0 or λr<λb.

###### Example 1.2.

We will later verify that the following are Euclidean domains.

1. , with λa=a.

2. The set kx of polynomials in x, with coefficients in a field, k.

3. i=a+bi:a,b,i=-1, with λa+bi=a2+b2. Note here that λ is multiplicative.

4. ω=a+bω:a,b,ω=-1+-32, with λa+bω=a2-ab+b2.

###### Definition 1.3.
1. An ideal in R is an IR that is closed under addition and satisfies the absorption property. That is, if aR,bI, then abI.

2. The ideal generated by the elements a1,a2,,anR, denoted a1,a2,,an, is the set

 a1⁢x1+a2⁢x2+…+an⁢xn:x1,x2,…,xn∈R

.

3. R is a principal ideal domain if every ideal in R is principal, meaning “generated by a single element of R”. A principal ideal domain will often be called a PID.

###### Theorem 1.4.

Every Euclidean domain is a PID.

###### Proof.

Let I be an ideal in a Euclidean domain R. The set λb:bI* has a least positive element, λa. Since aI*, aI. If we can show Ia, then we are done. To this end, let cI and write c=aq+r as in the definition of Euclidean domain. Since a,cI, we have r=c-aqI so, by the minimality of λa, λrλa, so λr=0. Therefore c=aqa so Ia as required. ∎

###### Definition 1.5.

Let R be an integral domain and let a,b,uR. We say:

1. b divides a and write b|a, if a=bc for some cR.

2. u is a unit if u|1. Note that u is a unit if and only if u-1 is a unit. The set of all units in R is denoted R*.

3. a and b are associates if a=bv for some unit vR.

4. a nonunit pR* is irreducible if a|p implies that a is a unit or an associate of p.

5. A nonumit pR* is prime if p|ab implies p|a or p|b.

###### Exercise 1.6.

Show that if R is an integral domain, then pR is irreducible only if p is prime.

We will show that one hallmark of a PID is that the converse holds as well.

###### Definition 1.7.

Let R be an integral domain with a,bR.

1. dR is a greatest common divisor, or gcd, of a and b if

1. d|a and d|b.

2. c|a and c|b implies that c|d, for all cR.

2. a and b are relatively prime if every gcd of a and b is a unit.

###### Exercise 1.8.

Show that if d and d are are both gcd’s of a,bR, then d and d are associates.

For the remainder of this section, we will assume that R is a PID and a,b are elements of R.

###### Proposition 1.9.

a and b have a gcd d, and a,b=d.

###### Proof.

By definition of a PID, there is a dR with a,b=d. Then a,bd, so d|a and d|b. Moreover, if c|a and c|b, then c|(ax+by) for all x,yR. Since d=ax+by for some x,yR, we have c|d. Hence d is a gcd of a and b. ∎

###### Corollary 1.10.

If a and b are relatively prime, then a,b=R.

###### Proof.

For such a and b, a,b=u for some unit uR by proposition 1.9. But u=R so we are done. ∎

###### Corollary 1.11.

If pR is irreducible, then p is prime

###### Proof.

Suppose pR is irreducible and p|ab. We need to show that p|a or p|b. If p|a we are done, so assume pa. To show p|b, it suffices to show that any gcd of p and a is a unit, and thus p,a=R. If so, then 1=px+ay for some x,yR, so b=bpx+bay. Since p|bpx and p|bay, we then have p|b. Let d be a gcd of p and a. d|p so, since p is irreducible, d is a unit or an associate of p. Now d|a but pa so d cannot be an associate of p, so d is unit and we are done. ∎

We will now consider unique factorization in R. The key to the “factorization” part is the following lemma:

###### Lemma 1.12.

In a PID R, every ascending chain of ideals terminates. This means that given ideals

 I1⊂I2⊂I3⊂…

in R, there is an ideal IR and a k+ with In=I for all nk.

###### Proof.

Let I=i=1nIi. I is an ideal of a PID so I=a for some aI. By definition of I, there is a k for which aIk. Then for each nk, aIkInI=a, implying that In=I for all nk. ∎

###### Proposition 1.13.

Any element aR* can be written as a product of finitely many irreducibles in R.

###### Proof.

Let aR*. If a is irreducible, we are done. If not, write a=a1b1 with for nonunits a1 and b1. If a1 is irreducible, stop. If not, write a1=a2b2 with a2 and b2 nonunits. If a2 is irreducible, stop. Otherwise continue as above. Eventually there will be an n for whic an is irreducible or

 a⊂a1⊂a2⊂…

would be a nonterminating ascending chain in R, contradicting lemma 1.12. There must then exist an irreducible p1=an with a=p1c1. for some c1R. If c1 is a unit, the p1c1 is irreducible and we are done. If not, c1=p2c2 with p2 irreducible and so on as in the case on the ai above. Eventually there will be an k for whic ck is irreducible or

 a⊂a1⊂a2⊂…

would be a nonterminating ascending chain in R, contradicting lemma 1.12. So for some k+, a=p1p2pkck is a factorization.of a into irreducibles as required. ∎

This proves the factorization portion of unique factorization. Uniqueness is proven with two lemmas and a theorem.

###### Lemma 1.14.

Let pR be prime and aR*. There is an α with pα|a but pα+1a.

###### Proof.

Suppose the lemma were not true. Then for all m, there is a bmR with a=pmbm. Since pmbm=pm+1bm+1, we have pbm+1=bm. Since p is irreducible, we conclude that

 b1⊂b2⊂b3⊂…

is ascending and nonterminating, contradicting lemma 1.12. ∎

We can deduce the α in the previous lemma by ordpa.

###### Lemma 1.15.
 ordp⁢a⁢b=ordp⁢a+ordp⁢b

for all p,a,bR* with p irreducible.

###### Proof.

The proof is the same as in . ∎

We are now ready to prove the theorem.

###### Theorem 1.16.

Let R be a PID and S be any set of primes in R such that

1. every prime pR is an associate to some prime in S, and

2. no two primes in S are associates.

Then any aR* has a unique factorization

 a=u⁢∏p∈Spα⁢p

with u a unit and αp=ordpa for all pS.

###### Proof.

As in

We thus have that Euclidean domain PID UFD. Note that the converses are false.

###### Example 1.17.

-1+-192 is a noneuclidean PID.
Qx,y is a UFD but not a PID since the ideal x,y is not principal.

The following are examples of Euclidean domains and therefore PID’s and UFD’s.

###### Proposition 1.18.

The Gaussian integers i=a+bi:a,b with valuation λa+bi=a2+b2 are a Euclidean domain.

###### Proof.

Note that λuv=λuλv for all u,vi and in fact, for all u,v if we extend λ to . Now let α=a+bi and β=c+di, with a,b,c,d. We will show that there are ρ,δi with α=βδ+ρ and ρ=0 or λρ<λβ. To do som write α/β=r+si with r,s. The there are m,nZ with r-m12 and s-n12. Put δ=m+nii and note that

 λ⁢αβ-δ =λ⁢r-m+s-n⁢i =r-m2+s-n2 ≤14+14 =12

Now let ρ=α-βδ. Then

 λ⁢ρ =λ⁢β⁢αβ-δ =λ⁢β⁢λ⁢αβ-δ ≤12⁢λ⁢β <λ⁢β

as required. ∎

The crucial fact above is that there is always a δi within one unit of αβ. A similar thing happens for ω as defined previously, but no such δ exists in -5, which is not even a UFD. In particular, 9=33 and 9=2+-52--5 and all four factors are irreducible in -5.

## 2. On the Density of Primes in ℤ

###### Theorem 2.1 (Euclid).

contains infinitely many primes.

###### Proof.

Suppose not. List the positive primes in ascending order as p1,p2,,pn, and let N=p1p2pn+1. No pk can divide N, for if one did, then since p|p1p2pn, we would have pk|1, which is impossible.

So N must be prime; but this contradicts the fact that N>pn, and pnis the largest prime. Therefore, there must be infinitely many primes. ∎

It should be noted that is special, in the sense that there are other Euclidean domains with only finitely many primes up to associates.

###### Example 2.2.

Consider, for a given prime p, the ring p of reduced fractions. That is, the elements tu for which pu. As a subring of , p is an integral domain.

Claim: For tup with t,u=1 and pu, define λa=ordpt. Then λ is a Euclidean valuation on p.

###### Proof.

Let a be as above; also let b=v/wp* with v,w=1 and pw. We consider two cases

1. ordpt<ordpv. In this case, write a=bq+r with q=0 and r=a. Then λr=λa=ordpt<ordpv=λb, as required.

2. If ordptordpv, write a=bq+r with q=a/b and r=0. Note that qp, since

 q =ab =pordp⁢t⁢cupordp⁢v⁢dw =pordp⁢t-ordp⁢v⁢c⁢wu⁢d

Where pu and pd. So in this case, r=0 as required.

The only primes in p are the associates of p so p is an integral domain.

Going back to , we ask how many is “infinitely many”? Or, how many positive primes are there in a bounded subinterval of +? An answer is given in the prime number theorem.

###### Theorem 2.3 (PNT).

If πx is the number of positive prime integers less than x, then

 limx→∞⁡π⁢xx/log⁡x=1

In this case we say that πx is asymptotic to xlogx and write πxxlogx. We will see later that this is equivalent to saying that if pn is the nth positive prime, then pnnlogn. Note that here log is denoting the natural logarithm.

A full proof is beyond the scope of this course. We will hint at a proof here.

###### Definition 2.4.

Any function f:+ is an arithmetic function.

###### Example 2.5.
1. The function νn which gives the number of positive divisors of n.

2. σn, the sum of the positive divisors of n.

3. For some s,

 σs⁢n=∑d|nds

d|n always means positive divisors. Note that σ0=ν and σ1=σ.

4. The Möbius function

 μ⁢n=1if ⁢n=10if ⁢c2⁢n⁢ for some ⁢c⁢1⁢i⁢n⁢ℤ+.-1rif ⁢n=p1⁢p2⁢…⁢pr⁢ for distinct nonzero primes ⁢p1,p2,…,pr.
5. In=δn,1=1n=10n1

6. 1n=1 for all n.

7. Euler’s phi function, ϕn=#1kn:k,n=1, where #S denotes the cardinality of the set S.

###### Definition 2.6.

Let a,b be arithmetic functions. We define:

1. The Dirichlet product of a and b by

 a∘b⁢n=∑d|na⁢d⁢b⁢n/d
2. The Dirichlet L-series La by

 La⁢s=∑n=1∞a⁢n⁢n-s

for any s such that the series converges absolutely.

###### Proposition 2.7.

For arithmetic functions a and b, LaLb=Lab.

###### Proof.
 La⁢s⁢Lb⁢s =∑d=1∞a⁢d⁢d-s⁢∑m=1∞b⁢m⁢m-s =∑d=1∞∑m=1∞a⁢d⁢b⁢m⁢d⁢m-s =∑n=1∞∑d,m∈ℤ+,d⁢m=na⁢d⁢b⁢m⁢n-s =∑n=1∞∑d|na⁢d⁢b⁢n/d⁢n-s =∑n=1∞a∘b⁢n⁢n-s =La∘b⁢s

###### Proposition 2.8.

The set 𝒜,+, forms an integral domain with the usual addition of functions, +, and the Dirichlet product . The unity function is I.

###### Proof.

Exercise. ∎

We look at properties of certain algebraic functions. For this section, n=p1a1p2a2plal is a positive integer factored into powers of positive primes.

###### Proposition 2.9.
1. νn=k=1lak+1.

2. σn=k=1lpkak+1-1pk-1

###### Proof.

(a) d|n and d1 if and only if d=p1b1p2b2plbl with 0bkak for all k. There are ai+1 such bi’s for each i, so there are a1+1a2+1al+1 possible l-tuples b1,b2,,bl. (b)

 σ⁢n=∑b1,b2,…,blp1b1⁢p2b2⁢…⁢plbl=∑b1=0a1p1b1⁢∑b2=0a2p2b2⁢…⁢∑bl=0alplbl

and the result follows by summing the geometric sums. ∎

###### Proposition 2.10.

If n>1, then d|nμd=0.

###### Proof.

If d|n and n1, then

 μ⁢n=1if ⁢n=10if pk2|n for some 1 ≤k≤l.-1rif ⁢d=p1⁢p2⁢…⁢pr⁢ for distinct nonzero primes ⁢p1,p2,…,pr.

There are lr of the latter type of d’s, for 1rl. So

 ∑d|nμ⁢d=∑r=0llr⁢-1r=1-1l=0

Now observe that the simple identity

 μ∘1(n)=∑d|nμ(d)1(n|d)=∑d|nμ(d)=1n=10n>1=I(n)

So μ and 1 are inverses in A. This yields the very useful Möbius inversion formula.

###### Theorem 2.11 (Möbius inversion).

Let f𝒜. If Fn=d|nfd, then fn=d|nμdFn/d.

###### Proof.

Our hypothesis is that F=f1; then

 μ∘F=F∘μ=f∘1∘μ=f∘1∘μ=f∘μ∘1=f∘I=f

as required. ∎

From this we have a very cool application:

###### Lemma 2.12.
 ∑d|nϕ⁢d=n
###### Proof.

Let S=in:i=1,2,,n and take each element in S to have its denominator written in lowest terms. The denominator of each xS is a divisor of n. Moreover, for each such d, we have ϕd elements of S having this denominator: namely, the elements kd where 1kd and k,d=1. By definition of ϕ, there are exactly ϕd such k’s, so

 n=#⁢S=∑d|n#⁢kd∈S:k,d=1=∑d|nϕ⁢d

as required. ∎

As a result, we obtain the following useful formula for ϕn:

###### Corollary 2.13.
 ϕ⁢n=n⁢∏k=1d1-1pk
###### Proof.

The lemma says ϕ1=id, where we define idn=n for all n. But then by Möbius inversion ϕ=μid. That is,

 ϕ⁢n =∑d|nμ⁢d⁢nd =n⁢∑d|nμ⁢dd =n⁢1-1p1+1p2+…+1pl+1p1⁢p2+1p2⁢p3+…+1pl-1⁢pl+-1dp1⁢p2⁢…⁢pl =n⁢∏k=1d1-1pk

by some algebra. ∎

###### Corollary 2.14.
1. If p is prime and α+, then ϕ=pα-pα-1.

2. ϕ is multiplicative. That is, ϕmn=ϕmϕn if m,n=1.

###### Example 2.15.

Let n=617400=24325273. Then

 ν⁢n=3⋅3⋅4⋅5=180
 σ⁢n=25-12-1⋅33-13-1⋅53-15-1⋅74-17-1=4997200
 ϕ⁢n=n⁢1-12⁢1-13⁢1-15⁢1-17=141120

## 3. The growth of π⁢x

Recall the prime number theorem (PNT):

If πx is the number of positive prime integers less than or equal to x, then

 π⁢x∼xlog⁡x

We won’t prove this, but we will show that there are c1,c2>0 with

 c2xlog⁡x<π(x)

For this, we will need Chebyshev’s function,

 Θ⁢x=∑p≤xlog⁡p
###### Proposition 3.1.

For x>1, Θx<4log2x.

###### Proof.

Let n+. The binomial coefficient, 2nn, is divisible by any prime pn,2n, and therefore by the product of all such primes. In particular,

 ∏n

But, since

 22⁢n=1+12⁢n=∑j=02⁢n2⁢nj,

we also have 2nn<22n. So the product n<p2np is less than 22n. Taking the natural logarithms of the result gives

 ∑n

Now note that for m+, the interval 1,2m equals 1,22,44,82m-1,2m, so taking the previous sum over n1,2,4,,2m-1 givers

 ∑1

But 1<p2m=Θ2m, so Θ2m<4log22m-1 for some m+.

Now given x>1, there is a m+ with 2m-1<x<2m. But then, since Θ is nondecreasing,

 Θ⁢x≤Θ⁢2m<4⁢log⁡2⁢2m-1<4⁢log⁡2⁢x.

###### Corollary 3.2.

For x2, πx<8log2+2xlogx.

###### Proof.

From a first course in calculus, we know that x<2xlogx for x2 so it suffices to show that

 π⁢x<8⁢log⁡2⁢xlog⁡×+x

for x2. By proposition 3.1,

 4⁢log⁡2⁢x >Θ⁢x ≥∑x

Then some algebra shows that

 π⁢x≤4⁢log⁡2⁢x12⁢log⁡x+x=8⁢log⁡2⁢xlog⁡x+x

as required. ∎

It was easier to work directly with Θx=pxlogp than with πx=px1. To get from the former to the latter, we needed to remove the “weighting factor” of logp. General strategies, called “Tauberian theorems”, for removing such wieghts abound in analytic number theory.

To complete our study, we will find c2>0 such that πx>c2xlog× for x2.

###### Lemma 3.3.

For n+ and prime p+, ord2nnlog2nlogp

###### Proof.

It is an exercise to prove that

 ordp⁢2⁢nn=ordp⁢2⁢n!n!⁢n!=∑s=j∞2⁢nps-2⁢nps

Now one checks that, for any x, 2x-2x is 0 or 1; also 2nps=2nps if 2n<p, meaning s>log2nlogp. So we have

 ordp⁢2⁢nn≤∑s=1log⁡2⁢nlog⁡p1=log⁡2⁢nlog⁡p

This gives us the desired result:

###### Proposition 3.4.

If x2, we have πx>c2x2log×, fro some constant c2.

###### Proof.

By the lemma, the fact that

 2⁢nn=n+11+n+22+…+2⁢nn≥2n

for n+, and the fact that p|2nn implies p2n, we have

 2n≤2⁢nn≤∏p≤2⁢nplog⁡2⁢nlog⁡p

So, taking natural logarithms,

 n⁢log⁡2≤∑p≤2⁢nlog⁡2⁢nlog⁡p

Break the sum into a sum over p2n and a sum over 2n<p2n. For the former sum, note that x is always less than x; for the latter, observe that

 2⁢n

So

 n⁢log⁡2 ≤∑p≤2⁢nlog⁡2⁢nlog⁡p⁢log⁡p+∑2⁢n

That is,

 Θ⁢2⁢n>n⁢log⁡2-2⁢n⁢log⁡2⁢n

But note that limn2nlog2nn=0 so that for some N+

 n≥N⇒2⁢n⁢log⁡2⁢nn≤log⁡22

But then, nN means that Θ2nlog22n. Now suppose x2N. Then 2nx2n+2 for some n+ with nN. So since Θ is nondecreasing,

 Θ⁢x≥Θ⁢2⁢n≥log⁡22⁢n≥log⁡22⋅x⁢log⁡22=log⁡2⁢x-2≥x⁢log⁡22

assuming N>1. We may thus assume that for some N+-1, x2N so that Θxlog22x. Of course for x in the interval 2,2N, the function Θxx attains a minimum m>0. Letting c2=minlog22,m, we find x2 implies Θxc2x. Finally, since

 Θ⁢x=∑p≤xlog⁡p≤π⁢x⁢log⁡x,

we find that if x2,

 π⁢x≥Θ⁢xlog⁡x≥c2⁢xlog⁡×.

## 4. Congruence

To generalize the notion of parity of an integer, a, we fix m+ and consider the remainder of a after division by m. Then a,b are called congruent modulo m, written abm, if they have the same such remainder.

###### Definition 4.1.

Let a,b and m+. We say abm if m|(a-b).

This defines an equivalence relation on .

###### Exercise 4.2.

For a,b,c and m+,

1. aamod m;

2. abmod m implies bamod m;

3. if abmod m and bcmod m, then acmod m

So congruence modulo m partitions into equivalence classers a¯, where by definition,

 a¯=b∈ℤ:b≡a⁢mod ⁢m=a+m⁢k:k∈ℤ=a+m⁢ℤ.

a¯ is also called the residue class of a modulo m.

If m=3:
0¯=0,±3,±6,
1¯=,-5,-2,1,4,7,
2¯=,-4,-1,2,5,8,
3¯=,-3,0,3,6,9,
4¯=,-2,1,4,7,10,
5¯=,-1,2,5,8,11,

###### Proposition 4.4.

For a given m+, there are exactly m distinict equivalence classes a¯.

###### Proof.

Note 0¯,1¯,2¯,,m-1¯ are distinct modulo m otherwise we would have a+km=b+lm for some integers a,b,k,l with 0a,bm-1, so that a-b=ml-k, so that m|(a-b), which is impossible for such a,b. To show that these are the only equivalence classes, let a. Write a=mq+r with 0r<m. Then armod m, meaning a¯=r¯, so a¯ is one of the classes already listed. ∎

###### Definition 4.5.

The set of residue classes modulo m is denoted /m.

###### Proposition 4.6.

/m is a ring under

1. a¯+b¯=a+b¯

2. a¯b¯=ab¯

###### Proof.

To shoe the above operations are well defined, we must show that if acmod m and bdmod m, then a+bc+dm and abcdmod m. To do this, suppose m|(a-c) and m|(b-d). Then m|((a-c)+(b-d)) so m|((a-c)-(b-d)) and m|(d(a-c)-c(b-d)), so m|(ad-bc) as required.
The rest of the proof is an exercise. ∎

###### Definition 4.7.

If a1¯,a2¯,,am¯ is a complete set of equivalence classes mod m, then a1,a2,,am is a complete set of residues modulo m.

###### Example 4.8.

Let m=4. Write /4=0¯,1¯,2¯,3¯. By abuse of notation, we sometimes write a for a¯. We have the following addition and multiplication tables.

 +012300123112302230133012
 ⋅012300000101232020230321

Note /4 is not an integral domain: in general, if m=m1m2, then m1¯m2¯=0 in /m is an integral domain if and only if m is prime.

### 4.1. Applications of Congruence to Polynomial Equations

Note that, if x1x2mod m, then cx1kcx2kmod m for all k,c; consequently, px1px2m for all polynomials pxx. We get the following proposition.

###### Proposition 4.9.

if pxx, and there is an m+ such that pa0mod m for any integer a0,1,2,,m-1, then px has no integer roots.

###### Proof.

Suppse pxx, and there is an m+ has an integer root x0. For any m+, we have x0amod m for some a0,1,2,,m-1, so by the above note, papx0mod m. ∎

###### Example 4.10.

Let px=x5+5x4+4. We judiciously choose m=3, and note p0=41mod 3, p1=101mod 3, and p2=1162mod 3. So by the above proposition, px has no roots in .

###### Proposition 4.11.

Let d=a,m, a=ad, m=md. We have:

1. axbmod m has solutions if an only if d|b.

2. If there are any solutions, thrn there are exactly d unique incongruent solutions mod m. If x0 is any such solution, then all such may be given by

 x0,x0+m′,x0+2⁢m′,…,x0+d-1⁢m′.
###### Proof.
1. () If x0 is a solution, then ax0=b+mk for some integer k. But d|m, and d|a so d|b, as required.
() We can write d=ar+ms for some r,s. Assume d|b. Then writing b=db, we have b=ar+msb, of arbbmod m, so x0=rb solves the congruence.

2. Let x0 be a solution. Then for l, we have

 a⁢x0+k⁢m′ =a⁢x0+k⁢a⁢m′ =a⁢x0+k⁢a⁢md =a⁢x0+k⁢a′⁢m ≡a⁢x0⁢mod ⁢m ≡b⁢mod ⁢m

That is, if x0 is a solution, then so is any of the items listed. All such items are incongruent mod m, since x0+kmx0+lmmod m so that m|m(k-l) which implies that k=l=0, since mk-l<md=m for 0k,dd-1. Finally, we need to show that,if ax1bmod m, then x1 is congruent to an element in the list. To do so , let x1 be such a solution. Then

 a⁢x1≡b≡a⁢x0⁢mod ⁢m

so m|a(x1-x0), so m|a(x1-x0), so since m,a=1, we have m|(x1-x0), so x1=km+x0 for some k. Write k=qd+r with 0rd-1, we have

 x1=q⁢d⁢m′+r⁢m′=q⁢m+r⁢m′+xo≡r⁢m′+x0⁢mod ⁢m

so x1 is congruent to an element in the list and we are done.

The proof of the forward direction of part (i) shows how to construct a solution x0 to axbmod m, assuming (a,m)|b. Namely: write a,m=ar+bs with r,s and let x0=rb/a,m.

###### Example 4.12.

Completely solve

 12⁢x≡15⁢mod ⁢21
###### Solution.

Since 12,21=3 divides 15, there are solutions. By the Euclidean algorithm, we can write 3=221+-121 so

 x0=r⁢b/a,m=2⋅15/3=10

is a solution.
The complete set mod m is

 10,10+1⋅21/3=17,10+2⋅21/3=4

Now let’s apply the propostion with b=1: we find that ax1mod m - that is, a¯ is a unit in /m - if and only if (a,m)|1, meaning a,m=1. ∎

###### Corollary 4.13.

The units of /m are the classes a¯ where a,m=1. This implies that /m is a field if and only if m is prime.

We will denote by U/m the group of units in /m. By the corollary, this group has order ϕm, which implies the following corollary:

###### Corollary 4.14.
1. Euler’s Theorem: If a,m=1, then aϕm1mod m.

2. Fermat’s Little Theorem: If p is prime and pa, then ap-11mod p.

3. If p is prime and a, then apamod m.

###### Proof.

(i) is by the previous corollary and the fact that in any group G of order G, aG=1 for any aG.
(ii) follows by putting m=p prime into (i).
(iii) is true provided p|a by ii, multiplied through by a; (iii) us clearly true if pa. ∎

The previous corollary can be used to reduce powers mod primes.

###### Example 4.15.

Compute 587mod 17.

###### Solution.

Let p=17. Divide p-1=16 into 87:

 87=5⋅16+7

. Then by Fermat’s little theorem,

 58⁢7 =55⋅16+7 =5165⁢57 ≡15⋅57 ≡57 ≡25⋅25⋅25⋅5 ≡8⋅8⋅8⋅5 ≡64⋅40 ≡(-4)6≡-24≡10(mod 17)

## 5. Prelude to RSA

### 5.1. Comouting Powers by Successive Squaring.

Our goal is to efficiently compute powers ak mod m even for large values of a, m, and k.

###### Example 5.1.

Find 5605mod 921.

###### Solution.

Step 1: Rais 5 to 2k mod m for 12k605 as follows.

 51 ≡5⁢mod ⁢921 52=512 ≡25⁢mod ⁢921 54=522 ≡625⁢mod ⁢921 58=542=6252≡390625 ≡121⁢mod ⁢921 516=582≡1212≡14641 ≡826⁢mod ⁢921 532=51⁢62≡8262≡682276 ≡736⁢mod ⁢921 564=53⁢22≡7362≡541696 ≡148⁢mod ⁢921 5128=56⁢42≡1482≡21904 ≡721⁢mod ⁢921 5256=51⁢282≡7212≡519841 ≡397⁢mod ⁢921 5512=52⁢562≡3972≡157609 ≡118⁢mod ⁢921

The point is that no numbers greater than or equal to 9212 need ever be reduced.

Step 2: Find the binary expansion of 605 by successive exiscion of the highest possible powers of 2:

 605 =512+93 =512+64+29 =512+64+16+13 =512+64+16+8+5 =512+64+16+8+4+1

Step 3: Combine steps 1 and 2; then finish by whatever means necessary such as paring off factors and reducing.

 5605 =5512+64+16+8+4+1 =5512⁢564⁢516⁢58⁢54⁢51 ≡118⋅148⋅826⋅121⋅625⋅5 ≡118⋅148⁢826⋅121⁢625⋅5 ≡17464⋅99946⋅3125 ≡423508⋅362 ≡769⋅362 ≡278378≡236(mod 921)

So 5605236mod 921. ∎

We can use the above method to check whether an integer m>1 is prime.

1. Pick an integer a with 1a<m. Compute a,m. If it is greater than 1, then m is composite.

2. If a,m=1, compute am-1 modulo m. If you do not get 1, then by Fermat’s little theorem, m is composite.

3. If the result of (b) is 1, then m may or may not be prime. There exist numbers, m for which am-11mod m for all 1a<m. Such numbers are called Carmichael numbers. m=561 is such a number. Try again with with a different a. If many different a’s satisfy am-11mod m, then m is probably prime (this probability can actually be quantified).

### 5.2. kth Roots mod m.

We now turn our attention to solving equations of the form

 xk≡b⁢mod ⁢m

for x, given k,b,m.

We assume k,ϕm=1 and b,m=1.

Suppose u,v satisy ku-ϕmv=1 and are greater than 0. This is possible because, if not, we replace u by u+nϕm and v by v+nk fro n+ large enough. Note that if we define x=bu, then

 xk=buk=bk⁢u=b1+ϕ⁢m⁢v=b⁢bϕ⁢mv=b⋅1v≡b⁢mod ⁢m

so we have solved bk modulo m.

To summarize, have the follwoing algorithm for finding the kth root of b modulo m as long as b,m=1

1. Compute ϕm and proceed if and only if k,ϕm=1.

2. Use the Euclidean algorith to find u,v+ with ku-ϕmv=1.

3. Compute bu modulo m. Then x=bu is a solution.

A fact that we will not prove but is quite nice is that the above x is unique modulo m.

###### Example 5.2.

Solve x31529mod 7531.

###### Solution.

First, we note that 29,7531=1 so we may use the method outlined above.

 ϕ⁢m=ϕ⁢17⋅443=16⋅442=7072

Using the Eucldiean algorithm, we can check that 7072,315=1 and obtain u=2739,v=122 so that ku-ϕmv=1. So we can compute bu=292739=1575mod 7531 by successive squaring so that x=1575 is the solution. ∎

## 6. The RSA (Rivest, Shamir, Adelman) Public Key Cryptosystem

A decoder, J. Lo, sends an encoding algorithm to an encodner, Jay Z, who encodes a message and sends it to J. Lo, who decodes it. All of this must be done in such a way that a spy, P. Diddy, can overhear all communications and still not decode the message.

The method is as follows: J. Lo picks large primes p and q, and forms m=pq. She also picks k+ with k,ϕm=1 and sends m and k, but not p or q, to Jay Z. Also sent is a way to convert letters to numbers, such as

 A↔11,B↔12,…,Z↔37

Next, Jay Z converts his message to a large number a. If am, he breaks a into submessages a1,a2,,ar, with each a<m. Then he computes aikmod m, by successive squaring, for each i and call the result bi. The bi for the encoded message. They are sent to J. Lo. Now P. Diddy, not knowing p or q or, consequently, ϕm cannot decode the message. But J. Lo can by solving aikbimod m for ai for each i.

###### Example 6.1.

Let m=77,k=11. Note that k,ϕm=11,60=1. Suppose the message is ”YO”. This becomes 3525. Since 352577, we form two submessages: a1=35,a2=25.

Now,

 35 ≡35⁢mod ⁢77 352=1225 ≡70⁢mod ⁢77 354=702 ≡49⁢mod ⁢77 358=492 ≡14⁢mod ⁢77
 a1k=3511=358⋅352⋅35≡14⋅70⋅35≡34300≡35⁢mod ⁢77

so b1=35

 25 ≡25⁢mod ⁢77 252= ≡625⁢mod ⁢77 254= ≡92⁢mod ⁢77 258= ≡42⁢mod ⁢77
 a2k=2511=258⋅252⋅25≡16⋅9⋅25≡144⋅25≡-10⋅25≡58⁢mod ⁢77

so b2=58

Using the Euclidean algorith, we see that u=11 and v=2 satisfy 11u-60v=1 so we can solve for a1 and a2 by our method of finding kth roots modulo m:

a111b135mod 77 so a1b1u351135mod 77 and a211b258mod 77 so a2b2u5811mod 77

Now

 58 ≡58⁢mod ⁢77 582=3364 ≡53⁢mod ⁢77 584≡532=2809 ≡37⁢mod ⁢77 588≡372=1369 ≡60⁢mod ⁢77

so

 a2 ≡5811 ≡588⋅582⋅58 ≡60⋅53⋅58 ≡25⁢mod ⁢77

It should be noted that the method of solving xkbmod m assumed b,m=1. But this failed above as 35,77=7. Our method still works provided m is a product of distinct primes.

## 7. The Chinese Remainer Theorem.

Let m+ have prime factorization

 m=p1a1⁢p2a2⁢…⁢plal

with ai>0 for all j. We wish to deduce an isomorphism between /m and

 ⨁j=1lℤ/pjaj⁢ℤ,

and thereby understand the structure of U/m.

It all starts with:

###### Theorem 7.1 (The Chinese Remainder Theorem (CRT)).

Suppose mi,mj=1 for 1i<jl and let m=m1m2ml. Let b1,b2,,bl. Then there is an x that solves the equations

 x ≡b1⁢mod ⁢m1 x ≡b2⁢mod ⁢m2 ⋮ x ≡bl⁢mod ⁢ml

simultaneously, and any two such x differ by a multiple of m.

###### Proof.

For 1jl, let nj=mmj. Then nj,mj=1, since nj=m1m2mj-1mj+1ml is a product of factors relatively prime to mj. So we can write njrj+mjsj=1 for rj,sj. Define ej=njrj. Then ej1mod mj; moreover, for kj, ej0mod mk.

But then

 x0=∑i=1lbi⁢ei

solves the congruences stated in the theorem.

Finally, suppose x1 solves the congruences as well. Then x0x1mod mj for all j. That is, mj|(x1-x0) for all j. The mj being relatively prime implies m=m1ml divides x1-x0 so x1x0mod m and we are done. ∎

Note that the proof above is constructive, so we may use it to find a solution for a given example.

###### Example 7.2.

Solve

 x≡1⁢mod ⁢4 x≡3⁢mod ⁢5 x≡0⁢mod ⁢3
###### Solution.

Put b1=1,b2=3,b3=0,m-1=4,m2=4,m3=3 so m=453=60,n1=15,n2=12,n3=20. By the Euclidean algorithm, we find

 -1⁢n1+4⁢m1=1 -2⁢n2+5⁢m2=1 -1⁢n3+7⁢m3=1

So a solution is

 x0 =∑i=13bi⁢ei =1⁢-1⋅15+3⁢-2⋅12+0⁢-1⋅20 =-87

We will now apply the CRT to /m and U/m.

Suppose m=m1m2ml with mj,mk=1 for 1j,kl and jk. For each j with 1jl, let ψj:/mj be the natural map aa+mj. Define

 ψ:ℤ→⨁j=1lℤ/mj⁢ℤ

by ψa=ψ1a,ψ2a,,ψla. One checks that ψ is a ring homomorphism. To check that ψ is surjective, let b=b1,b2,,blj=1l/mj. We need to show that b=ψa for some a. To this end, note that since eachψj is surjective, there are a1,a2,,al such that b=ψ1a1,ψ2a2,,ψlal. Now consider the system

 a ≡a1⁢mod ⁢m1 a ≡a2⁢mod ⁢m2 ⋮ a ≡al⁢mod ⁢ml

By the chinese remainder theorem, there is a simultaneos solution a. Now since aa+jmod mj for each j, we have ψjaψjajmod mj by definition of ψj. So

 b=ψ1⁢a1,ψ2⁢a2,…,ψl⁢al=ψ1⁢a,ψ2⁢a,…,ψl⁢a=ψ⁢a

so ψ is surjective. FInally,

 ker⁡ψ =a∈ℤ:ψ⁢a=0 =a∈ℤ:ψj⁢a=0⁢∀j =a∈ℤ:a≡0⁢mod ⁢mj⁢∀j ={a∈ℤ:m|a}

So we have a surjective homomorphism ψ:j=1l/mj with kernal m so by the fundamental homomorphism theorem for rings,

###### Theorem 7.3.

if m1,m2,,ml+ are relatively prime and m=m1m2ml, then

 ℤ/m⁢ℤ≅⨁j=1lℤ/mj⁢ℤ

In other words, knowing the nature and the algebra of remainders mod mj for various coprimes tells you the nature and the algebra of remainders modulo the product of these mj’s.

###### Corollary 7.4.

For m and the mj’s as above,

 U(ℤ/mℤ)≅ × U(ℤ/mjℤ)
###### Proof.

Let j=j1,j2,,jl be the isomorphism implicit in [7.3] and let j* be the restriction of j to U/m. Also, in general, write 1n for the multiplicative identity in . Then:

1. j*xy=jxy=jxjy=j*xj*y. for x,yU/m.

2. j* is injective because j is.

3. If xU/m, then there exists a yU/m for which xy=1m so that j*xy=jxy=j1x,j2x,jlxj1y,j2y,,jly=j1xj1y,j2xj2y,,jlxjly=1m1,1m2,1ml since j, being an isomorphism, takes the unity in /m to the unity in j=1l/mj.

So j* is an isomorphism between the stated groups of units and we are done. ∎

Now let n+ have prime factorization

 n=p1a1⁢plal⁢…⁢plal

By the above corollary,

 U⁢ℤ/m⁢ℤ≅U⁢ℤ/p1a1⁢ℤ × … × U⁢ℤ/plal⁢ℤ

so we ask what U/pa looks like for p+ prime and a+.

###### Lemma 7.5.

If k is a field and fxkx has degree n+, then f has at most n distinct roots in k.

###### Proof.

If n=1, then fx=ax+bkx has a single root x=-ba. Suppose the lemma is false and let n0 be the minimal such element n+ for which there is a polynomial fxkx of degree n with more than n distinct roots. n0>0 and we can find fxkx with degree n0 and at least n0+1 distinct roots. Let α be sucha root and write fx=qxx-α+rx with rx=0 or degrx<degx-α=1: that ism rx is a constant R. But then 0=qαα-α+R sp R=0 and fx=qxx-α.

Now, let β1,β2,,βn0 be distinct roots of f with no βj equal to α. Then for each j,

 0=f⁢βj=q⁢βj⁢βj-α

So q, which has degree n0-1 has at least no distinct roots, contradicting the minimality of n0 so the lemma is true. ∎

###### Proposition 7.6.

For p+ prime and x,

 xp-1-1≡x-1⁢x-2⁢…⁢x-p-1⁢mod ⁢p.
###### Proof.

We wish to show that if

 f⁢x=xp-1-1¯-x-1¯⁢x-2¯⁢…⁢x-p-1¯∈ℤ/p⁢ℤ⁢x

then fx=0 for all x/p.

1. Since the leading terms cancel, we have degfx<p-1;

2. fa¯=0¯ for 1ap-1, by Fermat’s Little Theorem so f is identically zero.

If we put x=0 in this proposition we obtain Wilson’s theorem:

###### Corollary 7.7 (Wilson’s Theorem).

p-1!-1mod p for p+ prime.

This tells us that the congruence xp-11mod p has exactly p-1 solutions mod p. More generally:

###### Proposition 7.8.

Let p+ be prime. If d|(p-1), then

 xd≡1⁢mod ⁢p

has exactly d distinct solutions mod p.

###### Proof.

By [7.5], xd-1/px has at most d distinct roots. Now suppose p-1=dc for c. Then

 xp-1-1xd-1=xdc-1xd-1=1+xd+x2⁢d+…+xc-1⁢d

So xp-1-1¯=xd-1¯gx for some gx/px of degree c-1d. Now by [7.5], gx has at most c-1d roots in /p so xd-1 must have less d roots, otherwise xp-1-1¯ would have less than c-1d+d=cd=p-1, contradicting the lemma. Thus we are done. ∎

U/p is cyclic.

###### Proof.

For c+, let ψc be the cardinality of the set xU/p:x=c where x denotes the order of x. If we show ψp-11, we will be done.

Let xU/p have order c; let d*; write d=cq+r with 0r<c. Then xd=xcqxr1qxrxrmod p, so xd1mod p if and only if xr1mod p if and only if r=0 (by the minimality of c) if and only if c divides d. So

 ∑c|dψ⁢c=x∈U⁢ℤ/p⁢ℤ:xd≡1⁢mod ⁢p=d

assuming d|(p-1). Now for any n+, let Fn=c|nψc so that Fn=n if n|(p-1). Choose n=p-1. By Möbius inversion,

 ψ⁢p-1 =∑c|(p-1)μ⁢c⁢F⁢p-1c =∑c|(p-1)μ⁢c⁢p-1c =∑c|(p-1)μ⁢c⁢i⁢d⁢p-1c

We saw in the proof of [2.13] that the sum on the right is ϕp-11, also ψp-11 and we are done. ∎

###### Definition 7.10.

An element g is a primitive root mod m+ if g¯/m generates U/m.

We have just seen that primitive roots exist if m is prime - in fact, there are ϕp-1 such roots.

###### Lemma 7.11.

If p is a prime and 1kp-1, then p|pk.

###### Proof.

We have pk=p!k!p-k!, or p!|(pkk!(p-k)!). Now p|p! but for 1kp-1, pk! and pp-k!, so p|pk. ∎

###### Lemma 7.12.

If l+, p is prime, and abmod pl, then apbpmod pl+1.

###### Proof.

If j is such that a=b+jpl, then

 ap =b+j⁢plp =bp+jp⁢pl⁢p+∑k=1p-1pk⁢bk⁢j⁢plp-k =bp+jp⁢pl⁢p-1-1⁢pl+1+pl⁢∑k=1p-1pk⁢bk⁢jp-k⁢plp-1-k

By [7.11], p divides each pk in the suml so apbpmod pl+1 as required. ∎

###### Corollary 7.13.

If l2 and p is an odd prime, then 1+appl-21+apl-1mod pl for all a.

###### Proof.

We will use induction on l. When l=2, 1+app2-2=1+ap2-1. So assume the result holds for some integer l2. Then

 1+a⁢ppl+1-2=1+a⁢ppl-1=1+a⁢ppl-2p≡1+a⁢pl-1p⁢mod ⁢pl+1

by 7.12 and the induction hypothesis. But, by the binomial theorem,

 1+a⁢pl-1p=1+p⋅a⁢pl-1+p2⁢a2⁢p2⁢l-2+∑k=3ppk⁢ak⁢pk⁢l-1

Now for k3 and l2, we have kl-13l-1=l+1+2l-2l+1 so pl+1 divides the above sum on k. Moreover, for p2, we have p|p2 by lemma , so that pl+1|p2p, and therefore pl+1 divides

 p2⁢pl⋅a2⁢pl-2=p2⁢a2⁢p2⁢l-2

So for p2, we have

 1+a⁢ppl+1-2≡1+a⁢pl≡1+a⁢pl+1-1⁢mod ⁢p

which is our indtuction step and we are done. ∎

###### Corollary 7.14.

If p is odd and pa, then 1+ap¯ has order pl-1 in U/pl.

###### Proof.

It is enough to show the following claims:

1. 1+appl-11mod pl

2. 1+appl-21mod pl

###### Proof of (i).

Raising both sides of 7.13 to pth powers gives

 1+a⁢ppl-1≡1+a⁢ppl-1p⁢mod ⁢pl

the right side of which is congruent to 1 mod pl because

 1+a⁢pl-1p=1+a⁢pl+∑k=2ppk⁢ak⁢pl-1⁢k

and, for k,l2, we have l-1k=+l-1k-1-1l, so that pl|pl-1k. ∎

###### Proof of (ii).

This is just the previous corollary and the fact that, if pa, then apl-10mod pl

Thus we are done. ∎

###### Lemma 7.15.

Let p be odd. There is a primitive root, g, of unity mod p such that gp-11mod p2.

###### Proof.

Let h be a primitive root of unity mod p. If hp-11mod p2, then let g=h. If hp-11mod p2, let g=h+p: then

 gp-1 =hp-1+p-11⁢p⁢hp-2+∑k=2p-1p-1k⁢pk⁢hp-1-k ≡hp-1+p-1⁢p⁢hp-2⁢mod ⁢p2 ≡hp-1-p⁢hp-2⁢mod ⁢p2 ≢1⁢mod ⁢p2

Since ph. ∎

###### Theorem 7.16.

U/pl is cyclic for p an odd prime and l1.

###### Proof.

Let g be as in the previous lemma; we claim that g¯=U/pl. To se this, let n be the order of g¯ in U/pl. Note that U/pl=ϕpl=pl-1p-1, so n|pl-1(p-1). If we can show that pl-1|n and (p-1)|n then, since pl-1,p-1=1, we will have pl-1(p-1)|n, so that n=pl-1p-1, as required.

Since gp-11mod p and gp-11mod p2, we have gp-1=1+ap where pa. So by 7.14, gp-1 has order pl-1 in U/pl. But

 gp-1n=gnp-1≡1p-1≡1⁢mod ⁢pl

so pl-1|n.

Since we can write n=pl-1m with m+. we have pl|(gn-1) so p|(gn-1) and

 1≡gn≡gpl-1m≡gm⁢mod ⁢p

So, by induction, gpkgmod p for all K. But (p-1)|m by the above congruences; so (p-1)|n and we are done. ∎

###### Theorem 7.17.

U/2l is cyclic for l=1 or 2. For l3, it is not cyclic. It is the direct product of a cyclic group of order 2l-2 with a cyclic group of order 2.

###### Example 7.18.

Let m=10800=243352. Then

 U⁢ℤ/m⁢ℤ ≅U⁢ℤ/24⁢ℤ × U⁢ℤ/33⁢ℤ × U⁢ℤ/52⁢ℤ ≅ℤ/2⁢ℤ × ℤ/4⁢ℤ × ℤ/ϕ⁢33⁢ℤ × ℤ/ϕ⁢52⁢ℤ =ℤ/2⁢ℤ × ℤ/4⁢ℤ × ℤ/18⁢ℤ × ℤ/20⁢ℤ
###### Theorem 7.19.

m+ possesses primitive roots if and only if m=2,4,pl, or 2pl for some odd prime p and l+.

###### $⇐.$

The backwards direction follows from the previous theorems. ∎

###### $⇒.$

Suppose m is not any of the specified forms. If m=2l for l3 then we are done. So we need only consider the remaining possibilities - namely, where m=pfm0 where f2, m0 is divisible by an odd prime, and p,m0=1. Here

 U⁢ℤ/m⁢ℤ≅U⁢ℤ/pf⁢ℤ × U⁢ℤ/m0⁢ℤ

Since ϕpf and ϕm0 are even, the groups on the right contain elements x and y, resepectively, of order 2, so that U/m has two such elements and is therefore not cyclic. ∎

### 7.1. nth Power Residues

###### Definition 7.20.

a is an nth power residue mod m+ if a,m=1 and the congruence xnamod m is solvable.

We have already seen that, if n,ϕm=1, then any a with a,m=1 is an nth power residue mod m. More generally,

###### Proposition 7.21.

Suppose M has primitive roots, and a,m=1. Then a is an nth power residue mod m if and only if aϕm/d1mod m, where d=n,ϕm. Further, when a is such a residue, there are exactly d distinct roods of a mod m.

###### Proof.

Let m possess primitive roots; suppose a,m=1. Put d=n,ϕm. For the forward direction, suppose x0namod m. Then by Euler’s theorem,

 aϕ⁢m/d≡x0nϕ⁢m/d≡x0nn/d≡1n/d≡1⁢mod ⁢m

To prove the reverse direction, suppose aϕm/d1mod m. Let g be a primitive root mod m, so that gbamod m for some b+. Note that, since gbϕm/d=aϕm/d1mod m, we have ϕ(m)|(bϕ(m)/d), or d|b. So the congruence nybmod ϕm has d solutions: let y0 be one such solution. Then ny0=b+kmod ϕm for some k: so

 gy0n≡gb⁢gϕ⁢mk≡gb≡a⁢mod ⁢m

so a is an nth power residue. ∎

###### Proposition 7.22.

The congruence xnamod 2l, for a odd and l3, has exactly one solution if n is odd and 2d solutions if a1mod 4 or a2l-2/d1mod 2l and 0 solutions otherwise, where d=n,2l-2.

Now for the other values of m. Suppose m=m1m2mr with mi,mj=1 for ij, and each congruence xnamod m has a solution xi. By the chinese remainder theorem, there is a simultaneous solution x0 to the equations xximod mi. Then for each i,

 x0n≡xin≡a⁢mod ⁢mi

So mi|(x0n-a) for all i, so m|(x0n-a) and so x0namod m. The consequence of this is that to solve xnamod m, it suffices to consider m=pl.

###### Definition 8.1.

Let a,m=1. We say a is a residue, or quadratic residue mod m if x2amod m is solvable. If not, a is said to be (quadratic) nonresidue mod m.

###### Lemma 8.2.
1. If p is an odd prime, then a is a residue mod p if and only if a is a residue mod pl for all l+.

2. a is a residue mod 23 if and only if a is a residue mod 2l for all l3.

###### Proof.

We first note that p,a=1 if and only if pl,a=1 for all l+. The backwards direction if clear for (A) and (B). For the forward direction of (A), assume that a is a residue mod m. Then we have the following string of implications:

 aϕ⁢p/2,ϕ⁢p≡1⁢mod ⁢p ⇒ap-1/2 ≡1⁢mod ⁢p ⇒ap-1/2pl-1 ≡1pl-1⁢mod ⁢pl ⇒apl-1⁢p-1/2 ≡1⁢mod ⁢pl ⇒aϕ⁢pl/2 ≡1⁢mod ⁢pl ⇒aϕ⁢al/z,ϕ⁢pl ≡1⁢mod ⁢pl

which implies that a is a residue mod pl for any l+. The first and the last implications are from 7.22; The third is by 7.12.

For the forward direction of (B), as in part (A), we have

 a⁢ is a residue mod ⁢23 ⇒a2/2,2 ≡1⁢mod ⁢23 ⇒a ≡1⁢mod ⁢23 ⇒a2l-3 ≡1⁢mod ⁢2l ⇒a2l-1/2,2l-2 ≡1⁢mod ⁢2l ⇒a⁢ is a residue mod ⁢2l

###### Corollary 8.3.

a is a residue mod 2l for all l3 if and only if a1mod 8.

So we have

###### Theorem 8.4.

Let m=2l0p1l1ptlt be the prime decomposition of m+. Suppose a,m=1. Then a is a residue mod m if and only if

1. a1mod 4 whenever l0=2;

2. a1mod 8 whenever l03;

3. api-1/21mod pi for 1it.

###### Proof.

The case where m is a power of the two follows from the above corollary (and inspection if m=2 or 4). The case where m is an odd prime power follows because, if p is odd, then xamod pl is, by part (A) of the previous lemma, solvable if and only if x2amod p is, which happens if and only if ap-1/21mod p. ∎

###### Example 8.5.

57 is a residue mod 2574293, since 571mod 8, 577-1/2573131mod 7, and 5729-1/25714-1141mod 29. But 57 is a nonresidue mod 25742935, since

 5729-1/2≡572≡22≡4≢1⁢mod ⁢5
###### Theorem 8.6 (The Law of Quadratic Reciprocity).

Define the Legendre symbol ap, for p an odd prime and a, by

 ap=1if ⁢a⁢ is a residue mod ⁢p.-1if ⁢a⁢ is a nonresidue mod⁢p.0if p|a

Then

1. -1p=-1p-1/2.

2. 2p=-1p2-1/8.

3. pqqp=-1p-12q-12 for q an odd prime not equal to p.

Towards the proof, we need

###### Proposition 8.7.

For p an odd prime and a,b,

1. ap-1/2apmod p;

2. abp=apbp;

3. if abmod p, then ap=bp.

###### Proof.

For (a), it is clear if p|a so suppose not. Then ap-11mod p so p|(ap-1-1); that is, p|(ap-1/2-1)(ap-1/2+1). So ap-1/21mod p or ap-1/2-11mod p. In the first case a is a residue mod p, so ap=1 so ap-1/21apmod p. In the second case a is a nonresidue mod p, so ap=-1, so ap-1/2-1apmod p.

For (b), we use part (a) to get

 a⁢bp ≡a⁢bp-1/2 ≡ap-1/2⁢bp-1/2 ≡ap⁢bp⁢mod ⁢p

each side of the congruence is equal to ±1 or 0, so the congruence implies equality.

(c)

 a≡b⁢mod ⁢p ⇒ap-1/2≡bp-1/2(mod p) ⇒(ap)≡(bp)(mod p) ⇒(ap)=(bp)

Note that (b) and (c) imply that ap defines a character on U/p, meaning a homomorphism from this group into *.

###### Corollary 8.8.

There are as many residues mod an odd prime as nonresidues.

###### Proof.

Since the polynomial xp-1-1¯=xp-1/2-1¯xp-1/2+1¯/px has, by Fermat’s little theorem, p-1 distinct roots, each of the factors xp-1/2-1¯ and xp-1/2+1¯ must have p-12 such. roots of the former are residues and roots of the latter are nonresidues. ∎

and we can prove part (a) of quadratic reciprocity.

-1p=-1p-1/2

###### Proof.

Put a=-1 into part (a) of 8.7 and note that, in this case, congruence implies equality. ∎

###### Definition 8.10.

For an odd prime p, define the set Lp of least residues mod p by

 Lp=-p-12,…,-1,1,…,p-12

Note that Lp is a complete set of representatives for U/p.

###### Definition 8.11.

For a with pa, denote by μa,p the number of elements of a,2a,4a,,p-12a that are congruent mod p to a negative element of Lp.

###### Lemma 8.12 (Gauss’ Lemma).

ap=-1μa,p, for p an odd prime and pa.

###### Proof.

Fix p and a. For 1lp-12, define μl as the element of Lp to which la is congruent modulo p Then μa,p=#1lp-12:la=-μlp. Note that μlμk for lk because otherwise we would have la±kamod p for some kl, implying that p|a(l±k) or, since p,a=1, p|(l±k), which is impossible for l,kp-12 and lk. So the sets

 m1,m2,…,mp-1/2⁢ and ⁢1,2,…,p-12

are eqyual, so

 p-12! =m1⁢m-1⁢…⁢mp-1/2 ≡±a⁢±2⁢a⁢…⁢±p-12⁢a⁢mod ⁢p ≡-1μ⁢a,p⁢p-12!⁢ap-1/2⁢mod ⁢p

by definition of μa,p.

Since pp-12!-1,we obtain -1μa,pap-1/2mod p . The right side is equivalent to ap and since equivalence mod an odd prime implies equality when both sides are ±1, we have that -1μa,p=ap and we are done. ∎

We can now prove part (b) of quadratic reciprocity:

###### Proposition 8.13.

For p an odd prime,

 2p=-1p2-1/8
###### Proof.

Note that μ2,p is the number of elements of A=12,22,,p-122 that are greater than p-12.

Let m2 be the largest element of A that is not greater than p-12; that is, 2mp-12<2m+1. Note also that

 μ⁢2,p=#⁢m+1⋅2,…,p-1=p-12-m

We consider four cases:

1. p=8k+1 for some k. Then m=2k satisfies 2mp-12<2m+1, so μ2,p=2k; then by Gauss’ lemma

 2p=-12⁢k=1
2. p=8k+3 for some k. Then m=2k satisfies 2mp-12<2m+1, so μ2,p=2k+1; then by Gauss’ lemma

 2p=-12⁢k+1=-1
3. p=8k+5 for some k. Then m=2k+1 satisfies 2mp-12<2m+1, so μ2,p=2k+1; then by Gauss’ lemma

 2p=-12⁢k+1=-1
4. p=8k+7 for some k. Then m=2k+1 satisfies 2mp-12<2m+1, so μ2,p=2k+2; then by Gauss’ lemma

 2p=-12⁢k+2=1

So 2p=1 if and only if p=±1mod 8. The latter is seen to hold if and only if p2-18 is even, so

 2p=1if ⁢p2-18⁢ is even-1if not

which is equal to -1p2-18, and we’re done. ∎

###### Definition 8.14.

For n+, an nth root of unity is a complex number z=e2πik/n where k and, by definition, eiθ=cosθ+isinθ for θ.

Note that if z is an nth root of unity, then zn=e2πik/nn=e2πik=cos2πk+isin2πk=1+i0=1.

a root of unity as defined above is called primitive if k,n=1. Note that this is the case if and only if z is not an mth root of unity for any positive m<n.

Now for n+ fixed, write ζ for e2πi/n. Then a complete set of distinct primitive roots of unity is given by

 ζk:1≤k≤n,k,n=1

so there are ϕn such primitive roots. Now for the remainder of the section, assume n+ is odd.

###### Lemma 8.15.
 xn-yn=∏k-0n-1x⁢ζk-y⁢ζ-k
###### Proof.

Since zn-1 has n distinct roots: 1,ζ,ζ2,,ζn-1 in , zn-1=k=0n-1z-ζk. Put z=xy and multiply through by yn to get

 xn-yn=∏k-0n-1x-y⁢ζk

But the set 1,ζ,ζ2,,ζn-1 is the same as 1,ζ-2,ζ-4,,ζ-2n-1. So

 xn-yn =∏k-0n-1x-y⁢ζ-2⁢k =∏k-0n-1ζ-k⁢x⁢ζk-y⁢ζ-k =∏k-0n-1ζ-k⁢∏k-0n-1x⁢ζk-y⁢ζ-k =ζ-1+2+…+n-1⁢∏k-0n-1x⁢ζk-y⁢ζ-k =ζ-n⁢n+12⁢∏k-0n-1x⁢ζk-y⁢ζ-k =∏k-0n-1x⁢ζk-y⁢ζ-k

Now define fz=e2πiz-e-2πiz=2isin2πz for z.

###### Proposition 8.16.
 f⁢n⁢zf⁢z=∏k=1n-12f⁢z+kn⁢f⁢z-kn
###### Proof.

By 8.15 with x=e2πiz and y=e-2πiz,

 f⁢n⁢z =xn-yn =∏k=0n-1x⁢ζk-y⁢ζ-k =∏k=0n-1e2⁢π⁢i⁢z+kn-e-2⁢π⁢i⁢z+kn =∏k=0n-1f⁢z+kn

So if we set m=n-k,

 f(nzf⁢z =∏k=1n-1f⁢z+kn =∏k=1n-12f⁢z+kn⁢∏k=n+12n-1f⁢z+kn =∏k=1n-12f⁢z+kn⁢∏k=n+12n-1f⁢z+kn-1 =∏k=1n-12f⁢z+kn⁢∏m=1n-12f⁢z+mn =∏k=1n-12f⁢z+kn⁢f⁢z-kn

###### Proposition 8.17.

For p,a,f as above,

 ∏l=1p-12f⁢l⁢ap=ap⁢∏l=1p-12f⁢lp
###### Proof.

Since la±μlmod p for some integer μl1,p-12, and since f is odd with period 1,

 f⁢l⁢a/p=f⁢±μl+k⁢pp=f⁢±μlp+k=f⁢±μlp=±f⁢±μlp

for some k. The minus sign occurs μa,p times; also,

 {1,2,3,…,p-12}={μ1.μ2,…,μp-12}

so

 ∏k=1p-12f⁢l⁢ap =∏k=1p-12-f⁢μp =-1μ⁢a,p⁢∏k=1p-12f⁢lp =ap⁢∏k=1p-12f⁢lp

where the last step is by Gauss’ lemma. ∎

###### Theorem 8.18 (Quadratic Reciprocity part (c)).

For p,g distinct odd primes,

 pq=-1p-12⋅q-12⁢qp
###### Proof.

By 8.17,

 qp=∏l=1p-12f⁢l⁢qp/f⁢lp

So by 8.16 with z=lp and n=q,

 qp=∏l=1p-12∏k=1q-12f⁢lp+kq⁢f⁢lp-kq

Now f is odd, so flp-kq=-fkq-lp for each l,k with 1lp-12 and 1kq-12, and of course flp+kq=fkq+lp, so

 qp =-1p-12⁢q-12⁢∏l=1p-12∏k=1q-12f⁢kq+lp⁢f⁢kq-lp =-1p-12⁢q-12⁢∏k=1q-12∏l=1p-12f⁢kq+lp⁢f⁢kq-lp =pq

## 9. Residues and Arithmetic Progression

We wish to address the following question: Given a are there infinitely many primes p modulo which a is a residue? For this section p and q will be distinct odd primes.

###### Proposition 9.1.
1. Suppose q1mod 4. Then q is a residue mod p if and only if p is a residue mod q.

2. Suppose q3mod 4. Then q is a residue mod p if and only if p±b2mod 4q.

###### Proof of (a).

If q1mod 4, then by part (c) or quadratic reciprocity, qp=pq, so qp=1 if and only if pq=1. ∎

###### Proof of (b).

Assume q3mod 4, so that q-12 is odd.

###### $⇐.$

If pb2mod 4q, then pb2mod q, so p is a residue mod q, so pq=1; also pb2mod 4 so, because b is odd and therefore b21mod 4, we have b1mod 4, so

 qp=pq⁢-1p-12⁢q-12=1⋅1=1

so q is a residue mod p.

If p-b2mod 4q, then much as above, -p is a residue mod q, and p-1mod 4.

 qp =pq⁢-1p-12⁢q-12 =-1q⁢-pq⁢-1p-12⁢q-12 =(-pq)(-1)p-12⁢q-12=-1⋅-1=1

so again q is a residue mod p.

###### $⇒.$

Assume q is a residue mod p. Since q-12 is odd, pq=qp-1p-12q-12=-1p-12. We consider two cases:

1. If p1mod 4, then p-12 is even so pq=1 implies that p is a residue mod q. Hence pb2mod q for some b, which we can take to be odd. If not, replace b by b+q. But then b21pmod 4 and since 4,q=1 we have pb2mod 4q.

2. If p3mod 4, then p-12 is odd so -pq=-1qpq=(-1)fracq-12(pq)=-1-1=1 which implies that -p is a residue mod q so that -pb2mod q for some odd b; this and the fact that -p1mod 4 implies that p-b2mod 4q as required.

###### Example 9.2.
1. Mod which odd primes is 11 a residue?

###### Solution.

113mod 4 so we need to find all odd b with b,11=1 and 1b44. The set of such b’s is

 1,3,5,7,9,13,15,17,19,21,23,25,27,29,31,35,37,39,41,43

Squaring these mod 44 gives 1,5,9,25,37 so 11 is a residue mod any prime p that is congruent to ±1,±5,±9,±25,±37 mod 44 and these are the only such primes. ∎

2. Mod which odd primes is 13 a residue?

###### Proof.

131mod 4. The residues mod 13 are 1,3,4,9,10, and 12 so 13 is a residue mod any odd prime which is congruent to one of these numbers mod 13. ∎

###### Corollary 9.3.

Let q be prime. There are infinitely many primes p such that q is a residue mod p.

###### Proof.

By Dirichlet’s theorem on primes in progression, any arithmetic progression

 h+k⁢q:k∈ℤ

contains infinitely many primes, provided h,q=1. So by 9.1, q is a residue mod infinitely many primes p, if q is odd.

The case q=2 follows because 2 is a residue mod an odd prime p 2p=1 -1p2-18=1 p2-18 is even p±1mod 8 p8k+1:k8k-1:k. ∎

###### Definition 9.4.

Let b=p1p2pm for not necessarily distinct odd primes p1,p2,,pm. The Jacobi symbol ab is defined by

 ab=ap1⁢ap2⁢…⁢apm

Note that ab=1 doesn not, in general, imply that a is a residue mod b

###### Example 9.5.
 215=23⁢25=-132-18⁢-152-18=-1⁢-1=1

although 2 is not a residue mod 15.

However, ab=-1 does imply that a is a nonresidue mod b.

###### Proposition 9.6.

Let a,a1,a2,b,b1,b2, with b,b1,b2 odd and greater than 1. Then

1. a1a2mod ba1b=a2b.

2. a1a2b=a1ba2b.

3. ab1b2=ab1ab2.

###### Proof.

The proof follows from the definition of the Jacobi symbol and the properties of the Legendre symbol. ∎

###### Lemma 9.7.

For r1,r2,,rl+ odd,

1. k=1mrk-12r1r2rm-12;

2. k=1mrk2-18r12r22rm2-18.

###### Proof.

the proof is a simple argument using induction on m. ∎

###### Proposition 9.8.

For b odd and greater than 1,

1. -1b=-1b-12

2. 2b=-1b2-18

3. For a odd and greater than 1 and a,b=1, abba=-1a-12b-12.

###### Proof.

Write b=k=1mpm as above. Then:

1.  -1b =∏k=1m-1pk =∏k=1m-1pk-12 =-1∑k=1mpm-12 =-1p1⁢p2⁢…⁢pm-12 =-1b-12
2.  2b =∏k=1m2pk =∏k=1m-1pk2-18 =-1∑k=1mpm2-18 =-1p12⁢p22⁢…⁢pm-18 =-1b2-18
3. Write a=q1q2qn for not necessarily distinct odd primes q1,q2,,qn and qjpk for all j and k. Then

 ab⁢ba =∏k=1m∏j=1nqjpk⁢∏k=1m∏j=1npkqj =∏k=1m∏j=1npkqj⁢qjpk =∏k=1m∏j=1n-1pk-12⁢qj-12 =-1∑k=1m∑j=1npk-12⁢qj-12 =-1∑k=1mpk-12⁢∑j=1nqj-12 =-1p1⁢p2⁢…⁢pm-12⁢q1⁢q2⁢…⁢qn2 =-1a-12⁢b-12

###### Corollary 9.9.

Let a; suppose a is not a perfect square. Then a is a nonresidue mod infinitely many primes p.

###### Proof.

We may assume that a is square-free since if a=b2c with c square-free, then ap=bp2cp=cp unless p|b, but there are only finitely many primes p dividing any divisor of a.

We will argue by contradiction, considering two cases.

1. a=2. Note that 23=-132-18=-1, so 2 is a nonnresidue mod 3. Suppose the set S2 of primes mod which 2 is a nonresidue is finite, say S2={l1,l2,,l)k}. Let b=8l1l2lk+3. Note that no element of S2 divides b and 3b. Since b=38, we have 2b=-1b2-18=-1, so necessarily, 2p=-1 for some prime p dividing b. But again, no prime in S2 divides b, so pS2 and p3 which is a contradiction so S2 is infinite.

2. a=2eq1q2qn with the qj’s distinct odd primes and n1, and e=0 or 1.

Suppose the set Sa of odd primes mod which a is a nonresidue is finite, say S2=l1,l2,,lk. Let s be any nonresidue mod qn, and let b solve the congruences

 b ≡1⁢mod ⁢lj b ≡1⁢mod ⁢8 b ≡1⁢mod ⁢qj b ≡s⁢mod ⁢qn

simultaneously. Since b1mod 8, b is odd; we find that 2b=1 and qjb=bqj for each j. So

 ab =2be⁢q1b⁢…⁢qnb =1e⁢bq1⁢…⁢bqn =1e⁢1q1⁢…⁢1qn-1⁢sqn =1⋅1⋯1(-1)=-1

So ap=-1 for some prime p dividing b. The fact that a is a nonresidue mod p means PSa; the fact that p|b and lj|(b-1) for eachj means psa. This is a contradiction so Sa is infinite.

###### Definition 9.10.

An element α is called an algebraic number if α is a root of some nonzero polynomial fxx. α is called an algebraic integer if it is a root of some monic, nonzero polynomial fxx

###### Example 9.11.

2 is an algebraic integer since it solves x2-2=0 so are i2 and 5. 52 is an algebraic number but not an algebraic integer. 52 is an algebraic number but not an algebraic integer.

Neither e nor π is an algebraic number.

The roots of unity, ζ=e2πi/n for n+ are algebraic integers as they solve xn-1=0.

###### Proposition 9.12.

α is a n algebraic integer if and only if α.

###### $⇐.$

The backwards direction is clear since x-α is a monic nonzeros polynomial if α. ∎

###### $⇒.$

Suppose α is a root of fx=xn+b1xn-1++bnx. Write α=pq with p,q and p,q=1: then fα=0 implies that pn+qb1pn-1+q2b2pn-2++qnbn=0; since q divides each summand after pn, we have q|pn. Since q,p=1, we have q=±1, so α=pq. ∎

### 9.1. The Algebraic Structures of Algebraic Numbers and Algebraic Integers

###### Definition 9.13.

W is a -module (respectively, -module if

1. γ1,γ2Wγ1+γ2W;

2. γW,r (respectively, r) rγW;

3. There is a finite subset γ1,γ2,,γl of W such that, given γW, there exist r1,r2,,rl (respectively, in ) with

 γ=∑k=1lrk⁢γk

in this case, we say the set γ1,γ2,,γl spans W.

Note that a -module is the same thing as a finite-dimensional vector space over .

###### Example 9.14.

i is a -module spanned by 1,i. Similarly for ω where ω=-121--3.

Both i and ω are rings, the latter because ω2=-ω-1.

M=a+b23:a,b is a -module but not a ring because (()23)2M.

[23={a+b23+c43:a,b,c} is a ring.

###### Proposition 9.15.

Let W be a nonzero -module. (respectively, a -module); suppose α satisfies αγW for all γW. Theh α is an algebraic number (respectively, integer).

###### Proof.

Suppose γ1,γ2,,γl spans W: since, by assumption, αγiW for each i, there exist, for each i, constants ai1,ai2,,ail (respectively, ) with

 α⁢γi=∑j=1lai⁢j⁢γj

We will rewrite this as

 0=∑j=1l(αδi⁢j-ai⁢j)γj(1≤i≤l)

where by definition, δij=1if i=j0if ij. But this means that the l × l matrix whose ijth entry is αδij-aij has determinant zero; one checks that the determinant is a monic, nonzero polynomial in α, with coefficients in (respectively ) and we are done. ∎

###### Corollary 9.16.

52 is not an algebraic integer.

###### Proof.

if 52 were an algebraic integer then, since the set of all algebraic integers forms a ring, we would have 522=52 would be an algebraic integer, which it is not by LABEL:[algint]. ∎

###### Notation 9.17.

We will denote the set of algebraic integers by Ω and the set of algebraic numbers by ¯.

###### Proposition 9.18.

Under the usual operations of addition (+) and multiplication (), Ω is a ring and ¯ is a field.

###### Proof.

We will prove the statement for ¯; the proof for Ω is similar.

Let α1.α2¯ and let f and g be nonzero elements of x with fα1=0=gα2, degf=n, and degg=m. We will also denote by W the set of all linear combinations

 W=∑i=0n-1∑j=0m-1ai⁢j⁢α1i⁢α2j:ai⁢j∈ℚ

Note W is a -module. Moreover, note α1WW and α2WW since α1n is a -linear combination α10,α11,,α1n-1 and α2m is a -linear combination α20,α21,,α2m-1.

But then, for γW, α1+α2γ=α1γ+α2γW and α1α2γ=α1α2γW so α1+α2¯ and α1α2¯. Thus

 αn+a1⁢αn-1+…+an-1⁢α+an=0

for certain ai’s in ; then. assuming α0,

 an⁢α-1n+an-1⁢α-1n-1+…+a1⁢α-1+1=0

so α-1¯ and ¯ is a field. ∎

###### Definition 9.19.

α1 and α2 in Ω are said to be congruent modulo gammaΩ (written α1α2mod γ) if γ|(α1-α2) in Ω. This means that there is a βΩ for which γβ=α1-α2.

###### Remark 9.20.

If α1α2mod γ in Ω for α1,α2,γ, then the β given in the definition is in both Ω and , and hence in . This means that congruence on Ω, when restricted to , is the same as congruence on .

###### Proposition 9.21.

If w1,w2Ω and p is prime in , then w1+w2pw1p+w2pmod p.

###### Proof.
 w1+w2p=w1p+w2p+∑k=1p-1pk⁢w1k⁢w2p-k

and p|pk whenever 1kp-1. ∎

Now given α¯, pick any monic polynomial, of minimal degree, from the set

 f⁢x∈ℚ⁢x*:f⁢α=0.

Call this polynomial mαx.

###### Proposition 9.22.

mαx is irreducible in x. It is also unique: that is, if gxx* is monic, gα=0, and deggx=degmαx, then gx=mαx.

Moreover, given any gxx with root α, mαx divides gx.

###### Proof.

mαx is irreducible because, if not, some polynomial in x of lesser degree would have α as a root.

Now suppose gxx has α as a root and write

 g⁢x=mα⁢x⁢q⁢x+r⁢x

with rx=0 or degrx<degmαx. Plugging in x=α gives

 0=g⁢α=mα⁢α⁢q⁢α+r⁢α=r⁢α

since mαα=0. Since mαx has minimal degree among nonzero polynomials with α as a root, we must have rx=0 so gx=mαxqx thus mα(x)|g(x).

Finally, it is easily shown that if mα(x)|g(x), degmαx=deggx, and mα and g are monic, then mαx=gx. ∎

###### Definition 9.23.

The polynomial defined above is called the minimal polynomial of α. degmαx is the degree of α. If mαx=mβx, we say α and β are conjugate in .

###### Example 9.24.

m37x=x-37; mix=x2+1=m-ix

x2+1 is irreducible because if it were reducible, it would factor into linear terms in x. but x2+1=x+ix-i, so by unique factorization in x, such a factorization is impossible. Note this means i and -i are conjugate in . So are 2 and -2 since m2x=x2-2=m-2x.

Finally, if δ=e2πi/p where p is prime, then mδx=xp-1+xp-2++x+1.

###### Definition 9.25.

Let α. The set

 g⁢αh⁢α:g⁢x,h⁢x∈ℚ⁢x,h⁢x≠0

is a field called the field of rational functions in α and is denoted α. Also recall that α denotes the ring of polynomials in α with rational coefficients.

If α¯, then α=α.

###### Proof.

let β=gαhαα. Then hα0 so mαxhx. So since mαx is irreducible, mαx,hx=x. Write mαxt1x+hxt2x=1 for t1x,t2xx; then since mαα=0, hαt2α=1 so h-1α=t2αx. So βx. ∎

It should be noted that this proposition fails if α¯. For example, ππ.

###### Corollary 9.27.

If α has degree n, then the dimension α: of α over is n.

###### Proof.

Note that

 ℚ⁢α =ℚ⁢α (9.1) =∑j=0kaj⁢αj:k∈ℕ,aj∈ℂ (9.2) =∑j=0kaj⁢αj:0≤k≤n-1,aj∈ℂ (9.3)

since αn is a linear combination of α0,α1,,αn-1. So S=αj:0jn-1 spans α over . Moreover, the elements of S are linearly independent over , since fα0 for any fxx* with 0degfx<n. So S is a basis for α over and therefore, [(α):]=#S=n. ∎

Congruence in Ω allows us to write a more satisfying proof of part (b) of quadratic reciprocity.

###### Theorem 9.28.

For p an odd prime, 2p=-1p2-18.

###### Proof.

Let ζ=e2π18 be a primitive 8th root of unity. Let

 τ=ζ+ζ-1=e2⁢π⁢18+e-2⁢π⁢18=2⁢cos⁡π4=2

Now let p be an odd prime. We will prove the result by computing τp modulo p in two ways.

First we have τ2=2, so

 τp-1=τ2p-1/2=2p-1/2≡2p⁢mod ⁢p

Multiplying both sides by τ gives

 τp≡2p⁢τ⁢mod ⁢p

Next we have

 τp=ζ+ζ-1p≡ζp+ζ-p⁢mod ⁢p

Since ζ8=ζ-8=1, we have

 ζp+ζ-p=ζ+ζ-1if ⁢p≡±1⁢mod ⁢8ζ3+ζ-3if ⁢p≡±3⁢mod ⁢8

But

 ζ3+ζ-3 =ζ+ζ-1⁢ζ2-1+ζ-2 =ζ+ζ-1⁢ζ+ζ-12-3 =τ⁢τ2-3 =τ⁢2-3 =-τ

so mod p,

 τp≡τif ⁢p≡±1⁢mod ⁢8-τif ⁢p≡±3⁢mod ⁢8

note that this may be written

 τp≡-1p2-18⁢τ⁢mod ⁢p

Combining the two computations of τp yields 2pτ-1p2-18τmod p and multiplying by τ=2 gives

 2⁢2p≡2⁢-1p2-18⁢mod ⁢p.

Since O,2=1, we may divide by 2 to get

 2p≡-1p2-18⁢mod ⁢p

which, by the usual argument, gives

 2p=-1p2-18

Throughout this section, p will be an odd prime, ζ=e2πi/p, and a.

###### Lemma 10.1.
 ∑t=0p-1ζa⁢t=pif ⁢a≡0⁢mod ⁢p0if not.
###### Proof.

If p|a then the sum is t=0p-11=p. If not then, since ζa1. the sum equals

 ∑t=0p-1ζat=ζap-1ζa-1=ζpa-1ζa-1=1a-1ζa-1=0

. ∎

Putting a=x-y for x,y and dividing by p gives the following corollary:

###### Corollary 10.2.
 1p⁢∑t=0p-1ζx-y⁢t=δx,y⁢p

where, by definition,

 δx,y⁢p=1if ⁢x≡y⁢mod ⁢p,0if not.
###### Lemma 10.3.
 ∑t=0p-1tp=0
###### Definition 10.4.

The (quadratic) Gauss sum ga is defined by

 ga=∑t=0p-1tp⁢ζa⁢t.

We also write g for g1.

This is an analogue of the number τ previously defined.

###### Lemma 10.5.
 ga=ap⁢g
###### Proof.

If p|a, then by the previous lemma,

 ga=∑t=0p-1tp⋅1=0=ap⁢g.

If not,

 ap-1⁢ga =ap⁢ga =∑t=0p-1ap⁢tp⁢ζa⁢t =∑t=0p-1a⁢tp⁢ζa⁢t =∑s=0p-1(sp)ζs=g(s=at)

since, as t runs through a complete residue system mod p, so does s=at when p,a=1. ∎

###### Proposition 10.6.
 g2=-1p-12⁢p.
###### Proof.

The idea is to consider the sum a=0p-1gag-a in two different ways. Way 1: By 10.5,

 ∑a=0p-1ga⁢g-a =∑a=0p-1ap⁢g⁢-ap⁢g =g2⁢∑a=0p-1-a2p =g2⋅-02p+g2⁢∑a=1p-1-a2p =g2⁢∑a=1p-1-1p⁢ap2 =g2⁢-1p⁢∑a=1p-1±12 =g2⁢-1p-12⁢p-1.

Way 2: By the definition of ga, and by the corollary,

 ∑a=0p-1ga⁢g-a =∑a=0p-1∑x=0p-1xp⁢ζa⁢x⁢∑y=0p-1yp⁢ζa⁢y =∑x=0p-1∑y=0p-1xp⁢yp⁢∑a=0p-1ζa⁢x-y =∑x=0p-1∑y=0p-1x⁢yp⁢pif ⁢x≡y⁢mod ⁢p0if not =p⁢∑x,y=0;x=yp-1x⁢yp =p⁢∑x=0p-1x2p =p⋅0+p⁢∑x=1p-1xp2 =p⁢p-1

Now equzte the right sides of these two ways and dividne by -1p-12p-1 to finish. ∎

###### Theorem 10.7 (Quadratic Reciprocity part (c)).

For p,q distinct odd primes,

 qp=-1p-12⁢q-12⁢pq.
###### Proof.

Let p*=-1p-12p. Then by the previous proposition, g2=p*, so

 gq-1=g2q-12=p*q-12≡p*q⁢mod ⁢q

so gqp*qgmod q and

 gq =∑t=0p-1tp⁢ζtq ≡∑t=op-1tpq⁢ζq⁢t ≡∑t=op-1(tp)ζq⁢tsince (tp)∈{-1,0,1} and q is odd. ≡gq ≡qp⁢g⁢mod ⁢q

Combining these two congruences, gives

 p*q⁢g≡qp⁢g⁢mod ⁢q;

multiply by g and use the fact that, here, congruence implies equality to get

 qp =p*q =-1p-12⁢pq =-1qp-12⁢pq =-1p-12⋅q-12⁢pq

as required. ∎

## 11. Finite Fields

Note that (for p prime?) /p is a field with p elements. We will investigate the the question of for which q+ there is a field Fq with q elements. For now we will assume q is such that there is such an Fq.

Throughout this section, all polynomials are in Fqx and the unity in Fq will be denoted by 1.

###### Proposition 11.1.
 xq-x=∏α∈Fqx-α.
###### Proof.

Since Fq is a multiplicative group with q-1 elements, we have αq-1=1 for each αFq*. So

 ∏α∈Fq*(x-α)|(xq-1-1).

Note that his follows because if αβ, then x-α and x-β are relatively prime. Comparing degrees and leading coefficients shows that this is actually equality so multiplying both sides by x=x-0 finishes the proof. ∎

###### Corollary 11.2.

Let αK where K is some field with FqK. Then αq=α if and only if αFq.

###### Proof.

αq=α if and only if α is a root of xq-x if and only if αFq. ∎

###### Corollary 11.3.

If f(x)|(xq-x) and degfx=d, then fx has d distinct roots.

###### Proof.

Since Fqx is a unique factorization domain, if f(x|(xq-x) then fx=j=1dx-αj where α1,α2,,αd are distinct elements of Fq. These αi are precisely the roots of fx. ∎

###### Theorem 11.4.

Fq* is a cyclic group.

###### Proof.

It suffices to show that Fq* has an element of order q-1. We will show that it has ϕq-1 such elements.

To this end, suppose d|(q-1). Say q-1=db. Then

 xq-1-1xd-1=xdb-1xd-1=1+xd+x2⁢d+…+xb-1⁢d,

so (xd-1)|(xq-1-1), whence (xd-1)|(xq-x) so xd-1 has d distinct roots.

These roots are precisely those αFq* of order d. So writing ψc=#αFq*:α=c, we have

 d=∑c|dψ⁢c,

For any n+ we define

 G⁢n=∑c|nψ⁢c

so that Gd=d provided d|q-1.Then, by Möbius inversion,

 ψ⁢q-1 =∑c|(q-1)μ⁢c⁢G⁢q-1c =∑c|(q-1)μ⁢c⋅q-1c =ϕ⁢q-1,

So Fq* has ϕq-1 elements of order q-1 and we are done. ∎

###### Proposition 11.5.

Let αFq*. Then xn=α has solutions in Fq* if and only if αq-1d=1, where d=n,q-1. If there is such a solution, then there are d such solutions

###### Proposition 11.6.

The set n1:n where by definition

 n⋅1=∑k=1n1if ⁢n>00if ⁢n=0-∑k=1-n2if ⁢n<0

forms a subfield of Fq*, isomorphic to /p for some prime p.

###### Proof.

Define j:Fq by jn=n1. One checks that this is a ring homomorphism, so kerj is an ideal in ; say kerj=m. Necessarily m is in fact a prime p, since m=m1m2 for m1,m2 implies that 0=jm=jm1jm2 so, since Fq is an integral domain, either jm1=0 or jm2=0, so either m1 or m2 is in m and is therefore ±m.

So, by the Fundamental Homomorphism Theorem for rings, j/p and we are done.

In the context of the previous proposition, let us identify j with /p. One then checks that Fq is a vector space over /p. say Fq;/p=n, and W=w1,w2,,wn is a basis for Fq over /p: then

 Fq=∑k=1nak⁢wk:a∈ℤ/p⁢ℤ.

The set on the right has pn elements, so

###### Proposition 11.7.

If Fq is a field with q+ elements, then q=pn with p prime and n+.

###### Definition 11.8.

If F is a finite field with pn elements for some prime p, then p is called the characteristic of F. Note that, since n1:n/p, we have p=minn+:n1=0.

###### Lemma 11.9.

If F has characteristic p, then

 α+βpd=αpd+βpd

for all α,βF and d+.

###### Proof.

The proof will be by induction on d. The implication holds for d=1 since

 α+βp=αp+βp+∑k=1p-1pk⁢αk⁢βp-k

and the sum on the right is zero, since p|pk for 1kp-1.

Now if the implication holds for d+, then

 α+βpd+1 =α+βpdp =αpd+βpdp =αpd+1+βpd+1

so it holds for d+1, and we are done. ∎

###### Lemma 11.10.

Let F be any field; let l,m+.

1. l|m if and only if (xl-1)|(xm-1) in +x.

2. Let α+. Then l|m if and only if (αl-1)|(αm-1).

We will prove (a) only; (b) is nearly identical.

###### $⇒.$

If m=lk for k+, then

 xm-1xl-1=1+xl+x2⁢l+…+xk-1⁢l.

###### $Leftarrow.$

Assume (xl-1)|(xm-1); write m=lq+r with 0r<l. Then

 xm-1=xr⁢xq⁢l-1+xr-1.

Now xl-1 divides the left side by assumption and also divides xql-1 as in the proof of the forward direction above, with k=q. So (xl-1)|(xr-1). Comparing degrees gives xr-1=0, so r=0 and l|m. ∎

###### Proposition 11.11.

Fpn has exactly one subfield, with pd elements, for each divisor d of n, and no other subfields.

###### Proof.

Let K be a subfield of Fpn. SInce the unity in K is the unity in Fpn, the characteristic of K is equal to the characteristic of Fpn; that is, p.

Now if α1,α2,,αd is a basis for K over /p and β1,β2,,βf is a basis for Fpn over K, then

 αj⁢βk:1≤j≤d,1≤k≤f

is a basis for Fpn over /p. So n=[Fpn:/p]=df, meaning d|n.

We then have that every subfield K of Fpn has pd elements for some divisor d of n. So we need only show that if d|n, then there is a subfield of Fpn with pd elements.

To do so: given d+ with d|n, define

 K=α∈Fpn:αpd=α.

Then K is a field, because if α,βK, then

1. α+βpd=αpd+βpd=α+β;

2. αβpd=αpdβpd=αβ;

3. α-1pd=αpd-1=α-1 for α0.

Now note that K=αFpn:αpd-α=0. Since d|n, (pd-1)|(pn-1) by the previous lemma, so (xpd-x)|(xpn-x). So xpd-x has pd distinct roots in Fpn, by 11.3. So K=pd.

Finally, for uniqueness of K: if K is a subfield of Fpn with pd elements, then

 K′=α∈Fpn:αpd=α=K

and we are done. ∎

###### Example 11.12.

Assuming there is a field F330, since 30=325, we have: F_3^30 @-[dl] @-[d] @-[dr] xymatrixAlignararar
F_3^2⋅5 @-[d] @-[drr] F_3^3⋅5 @-[dl] @-[d] F_3^2⋅3 @-[dl] @-[d] ararAlignararAlignarar
F_3^5@-[dr] F_3^3 @-[d] F_3^2 @-[dl]arAlignarAlignar
Align F_3^1≅Z/3Z

### 11.1. Existence of finite fields

###### Theorem 11.13.

Given n+ and a positive prime p, there is a field F with F=pn.

###### Proof.

The proof follows from two propositions:

###### Proposition 11.14.

Let k be a field. If fxkx is irreducible, then there is a filed K containing both a subfield isomorphic to k and a root α of fx; moreover, K=pdegfx.

###### Proposition 11.15.

Given n+, there is an irreducible fx/p with degfx=n.

###### Proof of 11.14.

Let I=fx be an ideal in kx; consider the ring L=kx/I=hx+I:hxkx. We will denote the coset hx+I by hx¯ Let hx¯K*. To show hx¯ is invertible we note that, since hx¯0, we have hxI, so fxhx. Since fx is irreducible, this means fx and hx are relatively prime: so there are t1x,t2xkx with hxt1x+fxt2x=1 But then

 h⁢x¯⁢t1⁢x¯=1¯-f⁢x¯⁢t2⁢x¯=1¯

so t1x¯=hx¯-1 and hx is invertible. Hence K is a field.

To see that K contains a subfield isomorphic t k, we simply note that j:kK given by ja=a¯ is an injective homomorphism so kjkK

Now let α=x¯K. We show fα=0 as follows. If

 f⁢x=∑m=0nam⁢xm

for amk for all m, then

 f⁢α=f⁢x¯=∑m=0nam⁢x¯m=∑m=0nam⁢xm¯=f⁢x¯=0¯.

To finish, we need to show K=pn, where n=degfx. To do this, it suffices to show that B=1,α,α2,,αn-1 is a basis for K over k.

To show that B spans K over k, we let gx¯K. The there are qx,rxkx with

 g⁢x¯=f⁢x¯⁢q⁢x¯+r⁢x¯

and rx=0 or degrx<degfx=n. Then, since fx=0¯¯,

 g⁢x¯=f⁢x¯⁢q⁢x¯+r⁢x¯=r⁢x¯=r⁢x¯=r⁢α,

so gx¯ is a linear combination of elements in B.

Finally, we show the elements of B are linearly independent. Suppose not. Then α would be a root of some polynomial in kx* of degree less than n. Among all such polynomials, let Gx have minimal degree. Then 1degGxn-1. Write

 f⁢x=G⁢x⁢Q⁢x+R⁢x

and Qx,Rxkx and degRx<degGx or Rx=0: then

 0=f⁢α=G⁢α⁢Q⁢α+R⁢α=R⁢α.

By the minimality of the degree of Gx, we conclude that Rx=0 so that fx=GxQx, contradicting the irreducibility of fx. Hence B is a basis for K over k and we are done. ∎

###### Definition 11.16.

The field K constructed above is denoted kα.

###### Definition 11.17.

For p prime and d+, we denote by Fdx the product of all monic, irreducible polynomials of degree d in /px.

###### Lemma 11.18.

For n+,

 xpn-x=∏d|nFd⁢x.
###### Proof.

Certainly xpn-x may be factored into monic irreducibles. So it suffices to show:

1. for any monic, irreducible fx of degree d, f(x)|(xpn-x) if and only if d|n.

2. Any nonconstant polynomial fx divides xpn-x to at most the first power.

###### Proof of (a).

Note that d|n if and only if (pd-1|pn-1) if and only if (xpd-1-1)|(xpn-1-1) if and only if (xpd-x)|(xpn-x). So the equivalence claimed in (a) amounts to saying f(x)|(xpn-x) if and only if (xpd-x)|(xpn-x) for f as stipulated. To prove this equivalence we note that there is a field K containing both /p and a root α of fx with K=p. We also note that the elements of K are precisely the roots of xpd-x. () Assume f(x)|(xpn-x). To show (xpd-x)|(xpn-x), it suffices to show that each root of xpn-x -that is, each element of K- is a root of xpn-x.

Note that fα=0 and f(x)|(xpn-x) imply αpn=α. Now let βK. We can write

 β=∑+m=0d-1⁢am⁢αm

where am/p since 1,α,α2,,αd-1 is a basis for K over /p. But then

 βpn =∑+m=0d-1ampn(αm)pn =∑+m=0d-1am(αpn)m =β=∑+m=0d-1amαm =β

so β is a root of xpn-x as required.

() Suppose (xpd-x)|(xpn-x). If we can show that f(x)|(xpd-x), we will have f(x)|(xpn-x), and we will be done.

To do so, write

 xpd-x=f⁢x⁢q⁢x+r⁢x

with qx,rx/px and rx=0 or degrx<degfx. Since αK,

 0=αpd-α=f⁢α⁢q⁢α+r⁢α=r⁢α.

But fx is irreducible and therefore of minimal degree among nonzero polynomials with α as a root, so necessarily, rx=0. So xpd-x=fxqx and f(x)|(xpd-x) and we are done with (a). ∎

###### Proof of (b).

Suppose xpn-x=fx2gx. Then by formal differentiation,

 pn⁢xpn-1-1=2⁢f⁢x⁢g⁢x+f⁢x2⁢g′⁢x

so that f(x)|-1 in /px. Hence fx is constant and we are done. ∎

###### Notation 11.19.

Denote by Nd the number of monic, irreducible polynomials of degree d in /p.

Comparing degrees in the previous lemma gives

 pn=∑d|nd⁢Nd

By Möbius inversion we have:

###### Corollary 11.20.
 n⁢Nn=∑d|nμ⁢nd⁢pd

Our goal is to show the left side is nonzero. We can do this more easily by showing that the right side is.

Let d0=min{d+:d|n,μ(nd)0}. d0 exists since μnn0. Then

 ∑d|nμ⁢nd⁢pd=pd0⁢±1+m⁢p

where m. ±1+mp±1mod p and so is nonzero.

### 11.2. Examples of Finite Fields

###### Example 11.21.
1. Let p be prime and p4mod 4. One then shows that in i, the ideal

 (p)=pℤ[i]={c+di:p|c,p|d}

is a prime ideal, and therefore that

 ℤ⁢i/p⁢ℤ⁢i=distinct cosets ⁢c+d⁢i+p⁢ℤ⁢i:c,d∈ℤ

is a field with p2 elements.

This fails if p1mod 4. e.g 1+2i1-2i=12+22=5 so

 1+2⁢i¯⁢1-2⁢i¯=5=0¯¯

in i/5i.

2. A field K with 36 elements:

Once checks directly that fx=x6+x+2/3x is irreducible over /3. Indeed, recall that

 x36-x=∏d∈1,2,3,6Fd⁢x

Where Fdx is the product of all monic, irreducible polynomials in /3x; more specifically,

 F1⁢x =x⁢x+1⁢x+2; F1⁢x =x2+1⁢x2+x+2⁢x2+2⁢x+2; F1⁢x =(x3+2x+1)(x3+2x+2)(x3+x2+2)) ⋅(x3+x2+x+2(x3+x2+2x+1)(x3+2x2+1) ⋅(x3+2x2+x+1)(x3+2x2+2x+2)

Note that degrees match up: x36-x has degree 36, while d1,2,3,6Fdx has degree

 1⋅3+2⋅3+3⋅8+6⁢cot⁡116=729=36

Now let K=/3x/fx; then K has dimension 6=degfx over /3, so K has 36 elements. K also contains a root α of fx, and we have

 K=∑j=05aj⁢αj:aj∈ℤ/3⁢ℤ

as a vector space. Abstractly, K is the space of 6-tuples

 a0,a1,…,a5:aj∈ℤ/3⁢ℤ

To define multiplication, we will use the fact that fα=0. For example:

 2,0,0,0,0,1⁢1,0,0,0,1,0 =2+α5⁢1+α4 =2+2⁢α4+α5+α9 =2+2⁢α4+α5+α3⁢-α-1 =2+2⁢α4+α5-α4-2⁢α3 =2-2⁢α3+α4+α5 =2,0,0,-2,1,1 =2,0,0,1,1,1

We have the following subfields for K:

xymatrixAlign

K @-[dr] @-[dl] arar
F_3^2 @-[dr] F_3^3 @-[dl] arAlignAlignar
AlignZ/3Z

We will consider F32. We know

 F32=β∈K:β32=β

We would like to have a more explicit description of this field. Fof βK, write

 β=∑j=05aj⁢αj

for aj/3. Then

 β32 =∑j=05aj⁢αj32 =∑j=05aj⁢α32⁢j =∑j=05aj⁢α3⁢-α-2j ⋮⁢reducing as necessarily =a0+a2+2⁢a3+2⁢a4+a5 +2⁢a3+2⁢a4+a5⁢α +2⁢a3+a5⁢α2 +a1+2⁢a2+a3+a4+2⁢a5⁢α3 +2⁢a1+2⁢a3⁢α4+a5⁢α5

So β32=β if and only if

 a0+a2+2⁢a3+2⁢a4+a5=a02⁢a3+2⁢a4+a5=a12⁢a3+a5=a2a1+2⁢a2+a3+a4+2⁢a5=a32⁢a1+2⁢a3=a4

Solveing gives

 a0 a1 =-2⁢a3 a2 =2⁢a3 a3 a4 =-2⁢a3 a5 =0

So finally,

 F32=a0-2⁢a3⁢α+2⁢a3⁢α2+a3⁢α3-2⁢a3⁢α4:a0,a3∈ℤ/3⁢ℤ

F33 is described similarly.

## 12. Gauss and Jacobi Sums

###### Definition 12.1.

a multiplicative character on the finite field Fp=/p is a homomorphism χ:Fp*

###### Example 12.2.

The Legendre symbol ap is a character on Fp. So is the trivial character ϵ, defined by

 ϵ⁢a=1⁢20px⁢∀a∈Fp*

The domain of a character χ on Fp can be extended to all of Fp by defining χ0 to be 0 if χ is trivial and 1 if not.

###### Proposition 12.3.

Let χ be a character on Fp and aFp*. Then

1. χ1=1.

2. χa is a p-1st root of unity.

3. χa-1=χa-1=χa¯.

###### Proof.
1. χ1=χ11=χaχ1 so since χ1* is nonzero, χ1=1.

2. χap-1=χap-1=χ1=1.

3. χa-1=χa-1 because chi is a homomorphism; since χa=1 by part (b), we have χaχa¯=1 so χa¯=χa-1.

###### Proposition 12.4 (The orthogonality property of characters).

let χ be a character on Fp. Then

 ∑t∈Fpχ⁢t=pif ⁢χ=ϵ0if not.
###### Proof.

This is clear if χ=ϵ. If not, then there is an aFp* with χa1; note that

 χ⁢a⁢∑t∈Fpχ⁢t =∑t∈Fpχ⁢a⁢χ⁢t =∑t∈Fpχ⁢a⁢t =∑u∈Fpχ⁢u

Since χa1, the final sum must be 0. ∎

Next, note that the set Fp of characters on Fp becomes a group if we define

1. χψa=χaψa for χ,ψFp and aFp;

2. χ-1a=0if a=0    and   χϵ;1if a=0    and   χ=ϵ;χa-1otherwise.

Note that ϵ is the identity in Fp.

###### Proposition 12.5.

Fp is a cyclic group of order p-1. also, if aFp-1, then there exists a character χFp with χa1.

###### Proof.

Recall that Fp* is cyclic of order p-1: say Fp*=g. Define ψ:Fp* by ψgk=ζk, where ζ=e2πi/p-1 for 0kp-1 and ψ0=0. Then ψ is a character on Fp since, if a=gl and b=gm are in Fp*, then

 ψ⁢a⁢b=ψ⁢gl⁢gm=ψ⁢gl+m=ζl+m=ζl⁢ζm=ψ⁢gl⁢ψ⁢gm=ψ⁢a⁢ψ⁢b.

Moreover, if a=gl1 in Fp, then p-1l so ψa=ζl1. Also, ψ01. So we will be done if we can show that Fp=ψ and that ψ has order p-1 in Fp.

For the latter, we note that ψj=ϵ if and only if 1=ψjg if and only if 1=ψgj=ζj if and only if (p-1)|j. So ψ=p-1 as required.

For the former, note that χFp implies that χg is a p-1st root of unity, so χg+ζk for some integer k0,1,2,,p-1. But then given n+, we have χgn=ζkn=ζnk=ψgnk so that χ=ψkψ, and we are done. ∎

###### Remark 12.6.

Both Fp* and Fp are cyclic of order p-1, so Fp*Fp. an explicit isomorphism is given by

 i⁢gn=ψn

with g and ψ as above.

###### Corollary 12.7.

If aFp*-1, then χFpχa=0.

###### Proof.

Let ψ be as above: then χψ ranges over Fp as χ does. So

 ∑χ∈Fp⌃χ⁢a=∑χ∈Fp⌃χ⁢a⁢ψ⁢a=ψ⁢a⁢∑χ∈Fp⌃χ⁢a

and since ψa1, the sum is 0. ∎

###### Lemma 12.8.

Let aFp*; suppose n|(p-1). If xn=a is not solvable in Fp*, then there exists a ϕFp with ϕn=ϵ and ϕa1.

###### Proof.

Let Fp*=g and, as before, Fp=ψ. Set ϕ=ψp-1/n. Then

 ϕn=ψp-1/nn=ψp-1=ϵ

proving the first claim.

Now, write a=gl; since xn=a is not solvable, we have nl (otherwise, gl/nn=gl=a). So

 ϕ⁢a=ψp-1/n⁢a=ψp-1/n⁢gl=ζp-1⁢l/n=e2⁢π⁢i⁢l/n≠1.

###### Notation 12.9.

When writing sums involving characters over Fp, we will omit ”χFp” when there is no danger of confusion.

###### Proposition 12.10.

Let aFp; let N(xn=a) be the number of elements xFp with xn=a. If n|(p-1), then

 N(xn=a)=∑χn=ϵχ(a).
###### Proof.

If a=0 then the left side is equal to 1; so does the right side since ϵ0=1 and χ0=0 for χϵ.

We will thus assume aFp* and consider two cases:

Case 1: N(xn=a)=0. In this case, let ϕ be as in the lemma. Note that χn=ϵ if and only if χϕn=χnϕn=ϵ.

 ∑χn=ϵχ⁢a=∑χn=ϵχ⁢ϕ⁢a=ϕ⁢a⁢∑χn=ϵχ⁢a;

as usual, since ϕa1, the sum is zero, and thus equals N(xn=a) as required.

Case 2: N(xn=a)>0. In this case, N(xn=a)=(n,p-1)=n. But since n|(p-1), Fp has exactly n distinct elements χ with χn=ϵ: namely χ=1,ψp-1/n,ψ2p-1/n,,ψn-1p-1/n. If we write a=bn where bFp* solves xn=a, then for such χ,

 χ⁢a=χ⁢bn=χn⁢b=ϵ⁢b=1

so

 ∑χn=ϵχ(a)=∑χn=ϵ1=n=N(xn=a)

as required. ∎

###### Remark 12.11.

There is a generalization of the previous proposition to the case where n need not divide p-1 but we will not prove it here.

###### Definition 12.12.

For χFp and aFp, we define the Gauss sum gaχ by

 ga⁢χ=∑t∈Fpχ⁢t⁢ζa⁢t

where ζ=e2πi/p. We also write gχ for g1χ.

###### Proposition 12.13.
 ga⁢χ=χ⁢a-1⁢g⁢χif ⁢a≠0⁢ and ⁢χ≠ϵ;pif ⁢a=0⁢ and ⁢χ=ϵ;0otherwise.
###### Proof.

We have shown that

 g0⁢χ=∑t∈Fpχ⁢t=0if ⁢χ≠ϵ,pif ⁢χ=ϵ.

Now suppose a0. Then

 ga⁢ϵ=∑t∈Fpζa⁢t=0

by the geometric sum formula, while for χϵ,

 ga⁢χ=∑t∈Fpχ⁢a-1⁢t⁢ζa⁢a-1⁢t=χ⁢a-1⁢∑t∈Fpχ⁢t⁢ζt=χ⁢a-1⁢g⁢χ,

since a-1t runs over Fp as t does.e ∎

###### Proposition 12.14.

If χ is not trivial, then

 g⁢χ=p
###### Proof.

For χϵ, we have on the one hand

 ∑a∈Fpga⁢χ⁢ga⁢χ¯ =∑a∈Fp*χ⁢a-1⁢χ⁢a⁢g⁢χ⁢g⁢χ¯ =∑a∈Fp*g⁢χ2 =p-1⁢g⁢χ2.

On the other hand,

 ∑a∈Fpga⁢χ⁢ga⁢χ¯ =∑a∈Fp∑x,y∈Fpχ⁢x⁢χ⁢y¯⁢ζa⁢x-y =∑x,y∈Fp*χ⁢x⁢y-1⁢∑a∈Fpζx-ya =∑x,y∈Fp*χ⁢x⁢y-1⁢pif ⁢x=y0if not =∑x∈Fp*p⁢χ⁢x⁢x-1 =p⁢∑x∈Fp*1 =p⁢p-1

Equating these two results gives p-1gχ2=pp-1 from which the result follows. ∎

We want to study solutions x,yFp × Fp to the equation xn+yn=1 for positive integers, n. Let N(xn+yn=1 be the number of solutions. Note that

 N(xn+yn=1)=∑a+b=1N(xn=a)N(yn=b)
###### Definition 12.15.

The Jacobi sum of two characters χ and λ is

 J⁢χ,λ=∑a+b=1χ⁢a⁢λ⁢b=∑a∈Fpχ⁢a⁢λ⁢1-a

Now suppose n|(p-1). We get

 N(xn+yn=1)=∑a+b=1[∑χn=ϵχ(a)][∑λn=ϵλ(b)]=∑χn=ϵ∑λn=ϵJ(χ,λ)
###### Proposition 12.16.

Jχ,λ=pif χ=λ=ϵ;-χ-1if χ=λ-1ϵ;gχgλgχλif χλϵ.

In particular, Jχ,λ=0 if χ=ϵ or λ=ϵ, but χλϵ.

###### Proof.

First,

 J⁢ϵ,ϵ=∑a∈Fpϵ⁢a⁢ϵ⁢1-a=∑a∈Fp1=p.

Next note that as a ranges over Fp-1, c=a1-a ranges over Fp--1, since c=a1-a if and only if a=c1+c. So for χϵ,

 J⁢χ,χ-1 =∑a∈Fpχ⁢a⁢χ-1⁢1-a =∑a∈Fp-1χ⁢a⁢χ-1⁢1-a =∑a∈Fp-1χ⁢a1-a =∑c∈Fp--1χ⁢c =∑c∈Fpχ⁢c-χ⁢-1 =0-χ⁢-1 =-χ⁢-1.

For the last case, note

 g⁢χ⁢g⁢λ=∑t,s∈Fpχ⁢t⁢λ⁢s⁢ζt+s=∑c∈Fp∑t+s=cχ⁢t⁢λ⁢s⁢ζc

Now suppose χλ0: then

 ∑t+s=0χ⁢t⁢λ⁢s =∑t∈Fpχ⁢t⁢λ⁢-t =λ⁢-1⁢∑t∈Fpχ⁢λ⁢t =λ⁢-1⋅0 =0

So

 g⁢χ⁢g⁢λ =∑c∈Fp*∑t+s=cχ⁢t⁢λ⁢s⁢ζc =∑c∈Fp*∑a+b=1χ⁢c⁢a⁢λ⁢c⁢b⁢ζc =∑c∈Fp*χ⁢c⁢λ⁢c⁢∑a+b=1χ⁢a⁢λ⁢b⁢ζc =∑c∈Fp*χ⁢λ⁢c⁢J⁢χ,λ⁢ζc =J⁢χ,λ⁢∑c∈Fp*χ⁢λ⁢c =J⁢χ,λ⁢g⁢χ⁢λ,

as required. ∎

###### Corollary 12.17.

If χ, λ, and χλ are not trivial, then Jχ,λ=p.

###### Corollary 12.18.
1. If p1mod 4, then there are α,β with p=α2+β2.

2. If p1mod 3, then there are α,β with p=α2-αβ+β2.

###### Proof of (a).

Assume p1mod 4. Then there is a character χFp of oreder 4; namely χ=ψp-1/4 with Fp=ψ.

Since 1=χ1=χa4=χa4 for all aFp*, we have χa±1,±i for such a. So

 J⁢χ,χ=∑a+b=1χ⁢a⁢χ⁢b∈ℤ⁢i,

meaning Jχ,χ=α+βi for some integers α and β. So by the previous corollary,

 p=p2=J⁢χ,χ2=α+β⁢i⁢α-β⁢i=α2+β2

###### Proof of (b).

Similarly to part (a), if p1mod 3, then there is a character χFp of order 3 so that Jχ,χ=α+βω for certain α,β, where ω=12-1+i3 is a primitive cube root of unity. Then

 p =(p)2=|J(χ,χ)|2 =α+β⁢ω⁢α+β⁢ω¯ =α2+α⁢β⁢ω+ω¯+β2⁢ω2 =α2-α⁢β+β2

Using the fact that i is a unique factorization domain, one shows that, in case (a) of the previous corollary, the stipulations that α,β>0 and α is odd imply that α and β are unique. This is not so in case (b). For example,

 7=32-3⋅1+12=32-3⋅2+22.

But note that, for p,α,β as in case (b), one has

 4⁢p =4⁢α2-α⁢β+β2 =2⁢α-β2+3⁢β2 =2⁢β-α2+3⁢α2 =α+β2+3⁢α-β2.

Checking α and β modulo 3, and noting that p1mod 3, one shows that 3|α, 3|β, or 3|(α-β) which leads to the next result:

###### Corollary 12.19.

If p1mod 3, then there exists A,B with 4p=A2+27B2. Furthermore, if A and B are positive, then they are unique.

## 13. Equations Over Finite Fields

###### Example 13.1 (x2+y2=1).

Write ρa for the Legendre symbol ap. Since ρ2=ϵ, we have ρ=ρ-1. so

 N(x2+y2=1) =∑ψ2=ϵ∑λ2=ϵJ⁢ψ,λ =J⁢ϵ,ϵ+J⁢ρ,ϵ+J⁢ϵ,ρ+J⁢ρ,ρ =p+0+0-ρ⁢-1 =p--1p =p--1p-12.
###### Example 13.2 (x3+y3=1).

First, we note that, for any ψ,λFp,

 J⁢ψ,λ=∑a+b=1ψ⁢a⁢λ⁢b=∑a+b=1ψ⁢b⁢λ⁢a=J⁢λ,ψ.

Now assume p1mod 3. Let χFp have order 3, so that λ3=ϵ if and only if λ{χ,χ2,χ3=ϵ}. Note that, since χ3=ϵ implies χ2=χ-1, we have χ2a=χ-1a=χa¯ for all aFp. Consequently, Jχ2,χ2=Jχ,χ¯. So

 N(x3+y3=1) =∑ψ3=ϵ∑λ2=ϵJ⁢ψ,ϵ =∑k,l=02J⁢χk,χl =J⁢ϵ,ϵ+J⁢χ,χ+J⁢χ2,χ2+2⁢J⁢χ,ϵ+2⁢J⁢χ2,ϵ+2⁢J⁢χ,χ2 =p+J⁢χ,χ+J⁢χ,χ¯+2⋅0+2⋅0+2⁢J⁢χ,χ-1 =p+2⁢R⁢e⁢J⁢χ,χ,

since χ-1=χ-13=χ3-1=ϵ-1=1.

To understand ReJχ,χ, recall that Jχ,χ=α+βω where α,β and ω=12-1+i3. Then working modulo 3 in the ring Ω, we have

 α+β⁢ω =J⁢χ,χ ≡p⁢J⁢χ,χ ≡∑t∈Fp*χ⁢t⁢ζt3 ≡∑t∈Fp*χ3⁢t⁢ζ3⁢t ≡∑t∈Fp*ζ3⁢t ≡∑t=0p-1ζ3⁢t-1 ≡-1

where the third congruence is because

 p⁢J⁢χ,χ =p⁢g⁢χ⁢g⁢χg⁢χ2 =p⁢g⁢χ⁢g⁢χg⁢χ-1 =p⁢g⁢χ2g⁢χ¯ =g⁢χ¯⁢g⁢χ⁢g⁢χ2g⁢χ2¯ =g⁢χ3

Now α+βω-1mod 3 gives α+βω¯-1mod 3; subtracting gives βω-ω¯0mod 3. Since ω-ω¯=i3 we have 3|i3β, so 9|-3β2, so 3|-β2, so 3|β. But this and the fact that α+βω-1mod 3 give α-1mod 3.

###### Theorem 13.3 (Gauss’ theorem).

If p1mod 3, then N(x3+y3=1)=p-2+A where 4pA2+27B2 for some B and A1mod 3. Furthermore, this A is unique.

###### Proof.

With α and β as above,

 N(x3+y3=1) =p-2+Re⁢J⁢χ,χ =p-2+Re⁢α+β⁢-12+i⁢32