Elementary Number Theory
Eric Stade
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

    a1x1+a2x2++anxn:x1,x2,,xnR

    .

  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

I1I2I3

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

aa1a2

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

aa1a2

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

b1b2b3

is ascending and nonterminating, contradicting lemma 1.12. ∎

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

Lemma 1.15.
ordpab=ordpa+ordpb

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=upSpα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-ni
=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
    =pordptcupordpvdw
    =pordpt-ordpvcwud

    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/logx=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,

    σsn=d|nds

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

  4. The Möbius function

    μn=1if n=10if c2n for some c1in+.-1rif n=p1p2pr 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

    abn=d|nadbn/d
  2. The Dirichlet L-series La by

    Las=n=1ann-s

    for any s such that the series converges absolutely.

Proposition 2.7.

For arithmetic functions a and b, LaLb=Lab.

Proof.
LasLbs=d=1add-sm=1bmm-s
=d=1m=1adbmdm-s
=n=1d,m+,dm=nadbmn-s
=n=1d|nadbn/dn-s
=n=1abnn-s
=Labs

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,,blp1b1p2b2plbl=b1=0a1p1b1b2=0a2p2b2bl=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 kl.-1rif d=p1p2pr 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μ=f1μ=f1μ=fμ1=fI=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#kdS:k,d=1=d|nϕd

as required. ∎

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

Corollary 2.13.
ϕn=nk=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μdnd
=nd|nμdd
=n1-1p1+1p2++1pl+1p1p2+1p2p3++1pl-1pl+-1dp1p2pl
=nk=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=3345=180
σn=25-12-133-13-153-15-174-17-1=4997200
ϕn=n1-121-131-151-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

πxxlogx

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

c2xlogx<π(x)<c1xlogx(x2).

For this, we will need Chebyshev’s function,

Θx=pxlogp
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<p2np<2nn

But, since

22n=1+12n=j=02n2nj,

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

n<p2nlogp<2nlog2.

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<p2mlogp<j=0m-122jlog2 (3.1)
=2log2j=0m-12j (3.2)
=2log22m-1 (3.3)
<2m+1log2 (3.4)
=4log22m-1 (3.5)

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<4log22m-1<4log2x.

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<8log2xlog×+x

for x2. By proposition 3.1,

4log2x>Θx
x<pxlogp
x<px1
=logxπx-πx
logxπx-x
=12logxπx-x.

Then some algebra shows that

πx4log2x12logx+x=8log2xlogx+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

ordp2nn=ordp2n!n!n!=s=j2nps-2nps

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

ordp2nns=1log2nlogp1=log2nlogp

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

2nn=n+11+n+22++2nn2n

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

2n2nnp2nplog2nlogp

So, taking natural logarithms,

nlog2p2nlog2nlogp

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

2n<p2n1log2nlogp<2log2nlogp=1

So

nlog2p2nlog2nlogplogp+2n<p2nlogp
p2nlog2n+p2nlogp
2nlog2n+Θ2n

That is,

Θ2n>nlog2-2nlog2n

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

nN2nlog2nnlog22

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

ΘxΘ2nlog22nlog22xlog22=log2x-2xlog22

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=pxlogpπxlogx,

we find that if x2,

πxΘxlogxc2xlog×.

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:bamod m=a+mk:k=a+m.

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

Example 4.3.

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+2m,,x0+d-1m.
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

    ax0+km=ax0+kam
    =ax0+kamd
    =ax0+kam
    ax0mod m
    bmod 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

    ax1bax0mod 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=qdm+rm=qm+rm+xorm+x0mod 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

12x15mod 21
Solution.

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

x0=rb/a,m=215/3=10

is a solution.
The complete set mod m is

10,10+121/3=17,10+221/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=516+7

. Then by Fermat’s little theorem,

587=5516+7
=516557
1557
57
2525255
8885
6440
(-4)6-2410(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.

515mod 921
52=51225mod 921
54=522625mod 921
58=542=6252390625121mod 921
516=582121214641826mod 921
532=51628262682276736mod 921
564=53227362541696148mod 921
5128=5642148221904721mod 921
5256=512827212519841397mod 921
5512=525623972157609118mod 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
=5512564516585451
1181488261216255
1181488261216255
17464999463125
423508362
769362
278378236(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

xkbmod 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=bku=b1+ϕmv=bbϕmv=b1vbmod 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=ϕ17443=16442=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

A11,B12,,Z37

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,

3535mod 77
352=122570mod 77
354=70249mod 77
358=49214mod 77
a1k=3511=358352351470353430035mod 77

so b1=35

2525mod 77
252=625mod 77
254=92mod 77
258=42mod 77
a2k=2511=258252251692514425-102558mod 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

5858mod 77
582=336453mod 77
584532=280937mod 77
588372=136960mod 77

so

a25811
58858258
605358
25mod 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=p1a1p2a2plal

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

xb1mod m1
xb2mod m2
xblmod 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=1lbiei

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

x1mod 4
x3mod 5
x0mod 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

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

So a solution is

x0=i=13biei
=1-115+3-212+0-120
=-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

aa1mod m1
aa2mod m2
aalmod 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=ψ1a1,ψ2a2,,ψlal=ψ1a,ψ2a,,ψla=ψa

so ψ is surjective. FInally,

kerψ=a:ψa=0
=a:ψja=0j
=a:a0mod mjj
={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

/mj=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=p1a1plalplal

By the above corollary,

U/mU/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-1x-1x-2x-p-1mod p.
Proof.

We wish to show that if

fx=xp-1-1¯-x-1¯x-2¯x-p-1¯/px

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

xd1mod 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+x2d++xc-1d

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. ∎

Theorem 7.9.

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=xU/p:xd1mod 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)μcFp-1c
=c|(p-1)μcp-1c
=c|(p-1)μcidp-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+jplp
=bp+jpplp+k=1p-1pkbkjplp-k
=bp+jpplp-1-1pl+1+plk=1p-1pkbkjp-kplp-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+appl+1-2=1+appl-1=1+appl-2p1+apl-1pmod pl+1

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

1+apl-1p=1+papl-1+p2a2p2l-2+k=3ppkakpkl-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

p2pla2pl-2=p2a2p2l-2

So for p2, we have

1+appl+1-21+apl1+apl+1-1mod 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+appl-11+appl-1pmod pl

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

1+apl-1p=1+apl+k=2ppkakpl-1k

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-11php-2+k=2p-1p-1kpkhp-1-k
hp-1+p-1php-2mod p2
hp-1-php-2mod p2
1mod 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-11p-11mod pl

so pl-1|n.

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

1gngpl-1mgmmod 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/mU/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/mU/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/dx0nϕm/dx0nn/d1n/d1mod 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

gy0ngbgϕmkgbamod 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,

x0nxinamod 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.

8. Quadratic Reciprocity

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,ϕp1mod pap-1/21mod p
ap-1/2pl-11pl-1mod pl
apl-1p-1/21mod pl
aϕpl/21mod pl
aϕal/z,ϕpl1mod 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 23a2/2,21mod 23
a1mod 23
a2l-31mod 2l
a2l-1/2,2l-21mod 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/25722241mod 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 modp.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

abpabp-1/2
ap-1/2bp-1/2
apbpmod p

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

(c)

abmod pap-1/2bp-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.

Corollary 8.9.

-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!=m1m-1mp-1/2
±a±2a±p-12amod p
-1μa,pp-12!ap-1/2mod 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+12,,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=-12k=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=-12k+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=-12k+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=-12k+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:1kn,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ζ-2k
=k-0n-1ζ-kxζk-yζ-k
=k-0n-1ζ-kk-0n-1xζk-yζ-k
=ζ-1+2++n-1k-0n-1xζk-yζ-k
=ζ-nn+12k-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.
fnzfz=k=1n-12fz+knfz-kn
Proof.

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

fnz=xn-yn
=k=0n-1xζk-yζ-k
=k=0n-1e2πiz+kn-e-2πiz+kn
=k=0n-1fz+kn

So if we set m=n-k,

f(nzfz=k=1n-1fz+kn
=k=1n-12fz+knk=n+12n-1fz+kn
=k=1n-12fz+knk=n+12n-1fz+kn-1
=k=1n-12fz+knm=1n-12fz+mn
=k=1n-12fz+knfz-kn

Proposition 8.17.

For p,a,f as above,

l=1p-12flap=apl=1p-12flp
Proof.

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

fla/p=f±μl+kpp=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-12flap=k=1p-12-fμp
=-1μa,pk=1p-12flp
=apk=1p-12flp

where the last step is by Gauss’ lemma. ∎

Theorem 8.18 (Quadratic Reciprocity part (c)).

For p,g distinct odd primes,

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

By 8.17,

qp=l=1p-12flqp/flp

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

qp=l=1p-12k=1q-12flp+kqflp-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-12q-12l=1p-12k=1q-12fkq+lpfkq-lp
=-1p-12q-12k=1q-12l=1p-12fkq+lpfkq-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-12q-12=11=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-12q-12
=-1q-pq-1p-12q-12
=(-pq)(-1)p-12q-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+kq: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=ap1ap2apm

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

Example 9.5.
215=2325=-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
    =-1k=1mpm-12
    =-1p1p2pm-12
    =-1b-12
  2. 2b=k=1m2pk
    =k=1m-1pk2-18
    =-1k=1mpm2-18
    =-1p12p22pm-18
    =-1b2-18
  3. Write a=q1q2qn for not necessarily distinct odd primes q1,q2,,qn and qjpk for all j and k. Then

    abba=k=1mj=1nqjpkk=1mj=1npkqj
    =k=1mj=1npkqjqjpk
    =k=1mj=1n-1pk-12qj-12
    =-1k=1mj=1npk-12qj-12
    =-1k=1mpk-12j=1nqj-12
    =-1p1p2pm-12q1q2qn2
    =-1a-12b-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

    b1mod lj
    b1mod 8
    b1mod qj
    bsmod qn

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

    ab=2beq1bqnb
    =1ebq1bqn
    =1e1q11qn-1sqn
    =111(-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=1laijγj

We will rewrite this as

0=j=1l(αδij-aij)γj(1il)

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-1j=0m-1aijα1iα2j:aij

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-1pkw1kw2p-k

and p|pk whenever 1kp-1. ∎

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

fxx*: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

gx=mαxqx+rx

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α:gx,hxx,hx0

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.

Proposition 9.26.

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:0kn-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=2cosπ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/22pmod p

Multiplying both sides by τ gives

τp2pτmod p

Next we have

τp=ζ+ζ-1pζp+ζ-pmod p

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

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

But

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

so mod p,

τpτif p±1mod 8-τif p±3mod 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

22p2-1p2-18mod p.

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

2p-1p2-18mod p

which, by the usual argument, gives

2p=-1p2-18

10. Quadratic Gauss Sums

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

Lemma 10.1.
t=0p-1ζat=pif a0mod 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.
1pt=0p-1ζx-yt=δx,yp

where, by definition,

δx,yp=1if xymod 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ζat.

We also write g for g1.

This is an analogue of the number τ previously defined.

Lemma 10.5.
ga=apg
Proof.

If p|a, then by the previous lemma,

ga=t=0p-1tp1=0=apg.

If not,

ap-1ga=apga
=t=0p-1aptpζat
=t=0p-1atpζat
=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-12p.
Proof.

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

a=0p-1gag-a=a=0p-1apg-apg
=g2a=0p-1-a2p
=g2-02p+g2a=1p-1-a2p
=g2a=1p-1-1pap2
=g2-1pa=1p-1±12
=g2-1p-12p-1.

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

a=0p-1gag-a=a=0p-1x=0p-1xpζaxy=0p-1ypζay
=x=0p-1y=0p-1xpypa=0p-1ζax-y
=x=0p-1y=0p-1xyppif xymod p0if not
=px,y=0;x=yp-1xyp
=px=0p-1x2p
=p0+px=1p-1xp2
=pp-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-12q-12pq.
Proof.

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

gq-1=g2q-12=p*q-12p*qmod q

so gqp*qgmod q and

gq=t=0p-1tpζtq
t=op-1tpqζqt
t=op-1(tp)ζqtsince (tp){-1,0,1} and q is odd.
gq
qpgmod q

Combining these two congruences, gives

p*qgqpgmod q;

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

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

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+x2d++xb-1d,

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

Gn=c|nψc

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

ψq-1=c|(q-1)μcGq-1c
=c|(q-1)μcq-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

n1=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=1nakwk: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+x2l++xk-1l.

$Leftarrow.$

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

xm-1=xrxql-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:1jd,1kf

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

hx¯t1x¯=1¯-fx¯t2x¯=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

fx=m=0namxm

for amk for all m, then

fα=fx¯=m=0namx¯m=m=0namxm¯=fx¯=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

gx¯=fx¯qx¯+rx¯

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

gx¯=fx¯qx¯+rx¯=rx¯=rx¯=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

fx=GxQx+Rx

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|nFdx.
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-1amα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=fxqx+rx

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,

pnxpn-1-1=2fxgx+fx2gx

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|ndNd

By Möbius inversion we have:

Corollary 11.20.
nNn=d|nμndpd

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μndpd=pd0±1+mp

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/pi=distinct cosets c+di+pi:c,d

    is a field with p2 elements.

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

    1+2i¯1-2i¯=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=d1,2,3,6Fdx

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

    F1x=xx+1x+2;
    F1x=x2+1x2+x+2x2+2x+2;
    F1x=(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

    13+23+38+6cot116=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

    with addition defined componentwise.

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

    2,0,0,0,0,11,0,0,0,1,0=2+α51+α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α32j
    =j=05ajα3-α-2j
    reducing as necessarily
    =a0+a2+2a3+2a4+a5
    +2a3+2a4+a5α
    +2a3+a5α2
    +a1+2a2+a3+a4+2a5α3
    +2a1+2a3α4+a5α5

    So β32=β if and only if

    a0+a2+2a3+2a4+a5=a02a3+2a4+a5=a12a3+a5=a2a1+2a2+a3+a4+2a5=a32a1+2a3=a4

    Solveing gives

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

    So finally,

    F32=a0-2a3α+2a3α2+a3α3-2a3α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=120pxaFp*

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

tFpχt=pif χ=ϵ0if not.
Proof.

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

χatFpχt=tFpχaχt
=tFpχat
=uFpχ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

ψab=ψglgm=ψ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

ign=ψ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/na=ψp-1/ngl=ζp-1l/n=e2πil/n1.

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=χnb=ϵ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χ=tFpχtζat

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

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

We have shown that

g0χ=tFpχt=0if χϵ,pif χ=ϵ.

Now suppose a0. Then

gaϵ=tFpζat=0

by the geometric sum formula, while for χϵ,

gaχ=tFpχa-1tζaa-1t=χa-1tFpχtζt=χa-1gχ,

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

aFpgaχgaχ¯=aFp*χa-1χagχgχ¯
=aFp*gχ2
=p-1gχ2.

On the other hand,

aFpgaχgaχ¯=aFpx,yFpχxχy¯ζax-y
=x,yFp*χxy-1aFpζx-ya
=x,yFp*χxy-1pif x=y0if not
=xFp*pχxx-1
=pxFp*1
=pp-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=aFpχ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ϵ,ϵ=aFpϵaϵ1-a=aFp1=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=aFpχaχ-11-a
=aFp-1χaχ-11-a
=aFp-1χa1-a
=cFp--1χc
=cFpχc-χ-1
=0-χ-1
=-χ-1.

For the last case, note

gχgλ=t,sFpχtλsζt+s=cFpt+s=cχtλsζc

Now suppose χλ0: then

t+s=0χtλs=tFpχtλ-t
=λ-1tFpχλt
=λ-10
=0

So

gχgλ=cFp*t+s=cχtλsζc
=cFp*a+b=1χcaλcbζc
=cFp*χcλca+b=1χaλbζc
=cFp*χλcJχ,λζc
=Jχ,λcFp*χλ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χbi,

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-31+12=32-32+22.

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

4p=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+2Jχ,ϵ+2Jχ2,ϵ+2Jχ,χ2
=p+Jχ,χ+Jχ,χ¯+20+20+2Jχ,χ-1
=p+2ReJχ,χ,

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χ,χ
pJχ,χ
tFp*χtζt3
tFp*χ3tζ3t
tFp*ζ3t
t=0p-1ζ3t-1
-1

where the third congruence is because

pJχ,χ=pgχgχgχ2
=pgχgχgχ-1
=pgχ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+ReJχ,χ
=p-2+Reα+β