Dirichlet

s Theorem
Daniel Harrer (ZetaX)
24. Februar 2011
Symbols and used theorems
Z: the integers.
N: the set {1, 2, 3, ...} of positive integers.
N
0
: the set {0, 1, 2, ...} of non-negative integers.
P: the primes in N.
Z/pZ or F
p
: the (eld of) residues mod p, p prime.
A sums and products of 0 numbers are always set to 0 respectively 1.
Theorem 1. (Unique factorisation)
For all n N there are (up to reordering) uniquely determined primes q
1
, q
2
, ..., q
k
such that
n = q
1
q
2
...q
k
.
Theorem 2. (Binomial theorem)
(a + b)
n
=
n

k=0
a
k
b
nk
_
n
k
_
for all a, b C.
Preface
A lot of primes
A very fundamental result is
Theorem 3. There are innitely many primes (in N).
There are a lot of proofs for this theorem, but probably the oldest and most famous one is:
1
Proof. (Euklid) Assume that there are only nitely many primes, call them p
1
, p
2
, ..., p
n
. Consider
their product P = p
1
p
2
... p
n
. Since P + 1 > 1, there is (using theorem 1) at least one prime q
dividing P + 1. But this q is dierent from all primes p
i
because q and P are coprime, so q was
not in the initial set, a contradiction.
The proof above was known thousands of years ago. But in the 18th century Euler showed that
there is a much stronger result:
Theorem 4. The sum

pP
1
p
diverges, in other words: grows to .
Proof. Every k N can be written as k = t s
2
with t not divisible by a square > 1. This gives
the inequality
n

k=1
1
k

pP
pn
_
1 +
1
p
_
n

s=1
1
s
2
.
Since
1
s
2

1
s(s1)
=
1
s1

1
s
for s 2 we get

n
s=1
1
s
2
1 +

n
s=2
1
s1

1
s
= 2
1
n
2. Together
with the easy to verify property 1 + x e
x
for all x R this yields
n

k=1
1
k

pP
pn
_
1 +
1
p
_
n

s=1
1
s
2
2

pP
pn
_
1 +
1
p
_
2

pP
pn
e
1
p
= 2 e

1
p
where the last sum also runs over all primes p n. To show that

pP
1
p
diverges, it now suces
to show that

k=1
1
k
diverges. But the latter one is a well known property, shown by the
following since for all n 2
m
we have:
n

k=1
1
k

2
m
1

k=1
1
k
=
m1

s=0
2
s+1
1

k=2
s
1
k

m1

s=0
2
s+1
1

k=2
s
1
2
s+1
=
m1

s=0
1
2
=
m
2
,
giving the divergence because m can be chosen arbitrary large.
Dirichlets Theorem
It is a very natural question to ask if a given sequence contains innitely many primes or not.
One of the easiest cases seems to be an arithmetic sequence a, a + m, a + 2m, a + 3m, .... In other
words, it is asked for a lot of primes p a mod m.
If d > 1 is a common divisor of a and m, then all terms of this sequence are divisible by d, thus
there can be only a nite set of primes in the sequence; in fact, the only prime can be d itself.
But for gcd(a, m) = 1, Dirichlet was able to prove that there are a lot of primes by giving a much
stronger result:
2
Theorem 5. Let gcd(a, m) = 1, then there are innitely many primes a mod m. More
exactly, the sum

pP
pa mod m
1
p
diverges and the primes are equally distributed into the dierent
residues a coprime to m.
All known proofs for this(these) theorem(s) require a lot of real or complex analysis, especially
concerning the so-called L-series L(s, ) =

n=1
(n)
n
s
with : N C some function (for those
who know the term: is a character from (Z/nZ)

to C here).
Its an interesting question whether there exist more elementary proofs for special cases, possibly
based on the ideas of Euklids proof of theorem 3 (note that Dirichlets idea is more related to
Eulers one).
Our goal is now to prove it for the cases a = 1 and a = 1 and arbitrary m.
Special cases
Lets try some very special m, namely m = 4 and m = 3.
Theorem 6. There are many primes p with:
a) p 1 mod 4.
b) p 1 mod 3.
c) p 1 mod m for any xed m N in general.
Proof. Its clear that c) implies a) and b) since there are only the residue classes 1 and 1
mod 3, 4, so we just need to prove this one.
Assume like before that there are only nitely many primes p
1
, p
2
, ..., p
n
1 mod m. Then let P
be their product and consider the number mP 1: All its prime divisors q
1
, q
2
, ..., q
k
are 1
mod m because they are coprime to P, thus dierent from the initial primes p
i
. But
1 = 1 1 ... 1 q
1
q
2
... q
k
= mP 1 1 mod m, being impossible for m 3. So we got
our contradiction again.
Another idea has to be used to attack 1 mod m, which we will do rst for m = 4:
Theorem 7. There are many primes 1 mod 4.
Before we can tackle this one, we need the following
Lemma 1. Let p be a prime dividing x
2
+ 1 for some x Z. Then p = 2 or p 1 mod 4.
3
Proof. Assuming that p 1 mod 4, so that
p1
2
is odd, we want to bring p|x
2
+1 to something
absurd. We know that x
2
1 mod p, so we get using Fermats little theorem:
1 x
p1

_
x
2
_
p1
2
(1)
p1
2
1 mod p,
our so much desired contradiction.
Now back to theorem 7:
Proof. Yes, it gets boring, but for the sake of proving the theorem assume that there are only
nitly many primes p
1
, p
2
, ..., p
n
1 mod 4 and let P be their product. Then consider any prime
divisor q of (2P)
2
+ 1: q is clearly odd, coprime to P, and 1 mod 4 by the Lemma, done.
Requirements
Before we can give a general proof like that of theorem 7, we need some more stu.
Denition 1. Let p be prime and p a Z. Then the smallest k N with a
k
1 mod p is
called the order of a mod p and is denoted by ord
p
(a) (note that the order always exists since
a
p1
1 mod m by Fermats little theorem).
This denition can still be made if p is any integer coprime to a, but we will need only the case p
prime.
A very powerful principle with striking simplicity is the next
Lemma 2. (Order lemma mod p)
Take a, p as in the above denition and let k be given such that a
k
1 mod p. Then ord
p
(a)|k.
This holds also for any p, but will, as said before, not be required.
Proof. Take division with remainder to write k = q ord
p
(a) + r, 0 r < ord
p
(a). By the
denitions we get a
r
a
k
a
qordp(a)
1 1
q
1 mod p. We cant have r = 0 since then
0 < r < ord
p
(a) and a
r
1 mod p, contradicting that ord
p
(a) is the minimal positive integer
with a
ordp(a)
1 mod p. So r = 0 and k = q ord
p
(a), proving the lemma.
A very useful type of polynomial, closely related to orders, is now given by
Denition 2. Set
n
= e
2i
n
. Then the n-th cyclotomic polynomial
n
(x) is dened by

n
(x) =
n

k=1
gcd(k,n)=1
(x
k
n
).
Theorem 8. The cyclotomic polynomials
n
(x) fulll the fundamental property
x
n
1 =

d|n

d
(x).
4
Proof. Since both sides are monic polynomials (their leading coecient is 1), it suces to show
that they have the same complex roots. The roots of x
n
1 are e
2k
n
for k = 0, 1, 2, ..., n 1,
thus let = e
2k
n
be a root of that polynomial.
Let d = gcd(k, n) and n = d n

, k = d k

. By that we have = e
2k
n
= e
2dk

dn

= e
2k

and
gcd(k

, n

) = 1, thus being a root of

n
(x) by denition. This shows that any root of the left
hand side (LHS from now) is one of the right hand side (RHS from now).
Now let be a root of the RHS, lets say
n
() = 0 for n

|n. By this n = d n

for some integer d

and because of that
n
=
_

_
d
= 1
d
= 1, so it is a root of the LHS.
Theorem 9. The coecients of the
n
(x) are integers.
Proof. We will use induction on n to show that
n
(x) is a polynomial with integers as coecients.
Clearly
1
(x) = x 1, so it is as nice as we want it to be. Thus assume the theorem to be proven
for all m < n, so especially for the divisors d = n of n. By that

d|n,d=n

d
(x) is a monic
polynomial with integer coecients.
By theorem 8 we have
n
(x) =
x
n
1

d|n,d=n

d
(x)
, and by making standard division of polynomials,
we see that
n
(x) has indeed integers as coecients.
Primes 1 mod n
Now the time has come to prove the innity of primes 1 mod m for any m.
We will use cyclotomic polynomials for this, so lets start collecting their properties mod p:
Lemma 3. Let n > 0 and a be integers, p prime, and g(x) a polynomial with integer coecients.
If x
n
1 (x a)
2
g(x) mod p, then p|n (polynomials mod p are archieved and handled by
reducing all coecients mod p).
Proof. Set y = x a, then we have (y + a)
n
1 y
2
g(y + a) mod p. Expand the LHS by the
binomial theorem to be y
n
+... +n a
n1
y +(a
n
1). From the factor y
2
on the RHS we get that
the constant and linear coecient are 0 mod p, thus a
n
1 mod p and n a
n1
0 mod p. So
we get n 1 n a
n
(n a
n1
) a 0 a 0 mod p.
This means nothing else than p|n.
Continuing with a way to construct primes we want:
Theorem 10. (Main theorem for cyclotomic polynomials mod p)
If p is a prime divisor of
n
(a) with n N and a Z, then p|n or p 1 mod n.
Proof. Let o = ord
p
(a) (it exists because p|
m
(a) p|a
m
1 p a
m
p a). Assume also
that o = n. By the order lemma we have o|n. Using that
x
n
1 =
n
(x) (x
o
1)

d|n, do
d=n

d
(x)
5
(theorem 8) together with
n
(x) (x a) g(x) mod p and x
o
1 (x a) h(x) mod p (the
last two because x a mod p is a root mod p of the LHSes), we are led to
x
n
1 (x a)
2
j(x) mod p (with j(x) = g(x) h(x)

d|n, do
d=n

d
(x)). But this gives p|n by
lemma 3, proving this theorem.
Theorem 11. There are innitly many primes 1 mod n.
Proof. For the fourth time now, we assume that there are only nitly many primes
p
1
, p
2
, ..., p
n
1 mod n. Then we take their product P = p
1
p
2
... p
n
and choose q to be any
prime divisor of
n
(k n P), where k is an integer just chosen big enough such that

n
(k n P) = 1 so that at least one prime divisor exists.
We have q|(knP)
n
1 q (knP)
n
q n and q = p
i
(for all i). Because of q n but
q|
n
(k n P) when applying theorem 10, only the second case can happen there, giving that
q 1 mod n. Since q is dierent from all the p
i
, this gives a contradiction.
Fields, Orders and Polynomials
The approach of constructing a polynomial having, up to nitly many exceptions, only divisors
1 mod n fails for n 3. Indeed it was proved that for given polynomial f(x) the set of
residues a mod n for which there are many primes p a mod n with p|f(k) for some k build
a group; especially, there will always be a lot of them 1 mod n.
Our idea is now to construct a polynomial only (again up to some exceptions) archieving prime
divisors 1 mod n.
This chapter is probably the most theoretic one: most stu will not be needed again, and it is
possible to show the important theorems only for the needed cases. But these proofs are neither
shorter nor more intuitive, so we will handle the general case.
Lemma 4. Let f(x) = a
k
x
k
+ ... + a
0
+ ... + a
k
x
k
with a
k
, a
k1
, ..., a
k+1
, a
k
Z be
symmetric, meaning that a
k
= a
k
, ..., a
i
= a
i
, ..., a
0
= a
0
or equivalently f(x) = f
_
1
x
_
. Then
there exists a polynomial g(x) (with integer coecients) fullling g
_
x +
1
x
_
= f(x).
Proof. This falls by induction:
Its clearly true for k = 0: we just take g(x) = f(x) = a
0
.
Now let it be proved for alle m < k. We note that g(y) = a
k
y
k
fullls
g
_
x +
1
x
_
= a
k
_
x +
1
x
_
k
= a
k
k

i=0
_
k
i
_
x
ki
x
i
= a
k
x
k
+ a
k
x
k
+ a
k
k1

i=1
_
k
i
_
x
k2i
.
Simple checking gives that the sum/dierence (and the product, which we will not need) of
symmetric terms is again symmetric. This leads to the symmetry (which also can be checked
6
directly) of
f(x) g
_
x +
1
x
_
=
k1

i=(k1)
a
i
x
i
a
k
k1

i=1
_
k
i
_
x
k2i
=
k1

i=(k1)
b
i
x
i
.
By induction hypothesis we have that f(x) g
_
x +
1
x
_
= g
_
x +
1
x
_
with a polynomial g(y). Thus
we can take g(y) = g(y) + g(y) as our polynomial. When we look back, we never left the integers
by our operations since we never divided, just added, subtracted and multiplicated.
The polynomial of our choice is more or less the following one:
Corollary 1. For n N, n 3 there exists a polynomial
n
(x) with integers as coecients such
that x
(n)
2

n
_
x +
1
x
_
=
n
(x). Here (n) just denotes the degree of
n
(x).
Proof. We remember that the roots of
n
(x) are
k
n
with gcd(k, n) = 1, so we can pair up
k
n
and

k
n
: If
k
n
=
k
n
, then
2k
n
= 1, thus n|2k; since n and k are coprime, we get n|2, contradicting
n 3. So we get that (n) is indeed even. And we also get that

n
(x) =

1k
n
2
gcd(k,n)=1
(x
k
n
)(x
k
n
) =

1k
n
2
gcd(k,n)=1
(x
2
(
k
n
+
k
n
)x + 1),
yielding
r(x) :=

n
(x)
x
(n)
2
=

1k
n
2
gcd(k,n)=1
(x (
k
n
+
k
n
) + x
1
),
giving r(x) = r
_
1
x
_
, so it is symmetric. Using the lemma, the result follows (we again never left
the integers).
As promised, we will prove the next theorems in a more general way. Thus we need elds and
some related stu.
Denition 3. A eld is a set K together with addition + and multiplication such that:
- there are 0
K
and 1
K
with 0
K
+ a = a = 1
K
a for all a K.
- the known laws of associativity, commutativity and distrubitivity hold.
- for all a K there is an (a) K with a + (a) = 0.
- for all a K\{0
K
} there is an a
1
K with a a
1
= 1
K
.
To shorten things, for n N
0
one often writes a
n
for a a ... a
. .
n times
and also often simplies a b to
ab as one was always used to.
7
Thus elds are just things we can calculate in as we always did.
Examples are:
- the rationals Q, the reals R or the complex numbers C.
- the residues mod p for p prime; this eld, from now denoted by F
p
, is more or less the
only eld we will need.
Some properties we will leave to the reader:
Properties 1. For all a K:
- (a) = (1
K
) a.
- 0
K
a = 0
K
.
- (1
K
)
2
= 1
K
.
- (a)
2
= a
2
.
- ab = 0 = a = 0 or b = 0.
Denition 4. Let n Z. Then for any eld K, n can be seen as some element n
K
of K by
n
K
:= 1
K
+ 1
K
+ ... + 1
K
. .
n times
if n 0 and by n
K
:= (1
K
+ 1
K
+ ... + 1
K
. .
(n) times
) otherwise. An easy check
gives (n)
K
= (n
K
), (m + n)
K
= m
k
+ n
K
and (m n)
K
= m
k
n
K
for all m, n Z (one says
that n
K
is a ring homomorphism Z K).
From now on K will always be a eld and we will often just write n instead of n
K
for all integers
when it is clear that we work in K.
Since integers can be seen as elements of K, especially the binomial coecients can be seen so.
Theorem 12. (Binomial theorem)
(a + b)
n
=

n
k=0
a
k
b
nk
_
n
k
_
for all a, b K.
Proof. This is proved exactly in the same way it is done for complex numbers inductively using
_
n+1
k
_
=
_
n
k
_
+
_
n
k1
_
.
Corollary 2. If p is a prime with p
K
= 0
K
, then (a + b)
p
= a
p
+ b
p
for all a, b K.
Proof. For k = 1, 2, ..., p 1 we have p|
p!
k!(p k)!
=
_
p
k
_
since the numerator is divisible by p,
whereas the denominator is not. As a result
_
p
k
_
K
= 0
K
for those k. Now the binomial theorem
nishes the proof by (a + b)
p
=
p

k=0
a
k
b
pk
_
p
k
_
K
= a
p
+ b
p
.
Lemma 5. If x
2
= a has a solution b K, then all solutions are given by x = b.
8
Proof. Let b be a solution, then b
2
= a, thus (b)
2
= b
2
= a, so b is also a solution.
Now let c be any solution, thus c
2
a = 0 c
2
b
2
= 0 (c b)(c + b) = 0. If c = b, then
c b = 0, thus (c b)
1
exists, leading to
b + c = (c b)
1
(c b)(c + b) = (c b)
1
0 = 0 c = b, proving the lemma.
We will now treat the lemmata we used and proved before in a more general way.
Denition 5. Let a K, we call the smallest k N with a
k
= 1 the order of a in K and write
ord
K
(a) for it. For those a for which there is no such k, we just write ord
K
(a) = .
Lemma 6. (order lemma)
If a K and n N such that a
n
= 1
K
, then ord
K
(a)|n.
Proof. The same as we did before when proving it mod p:
Let o = ord
k
(a) and take division with remainder to get n = o q + r with 0 r < o. We get
a
r
= a
noq
= a
n
(a
o
)
q
= 1
K
1
q
K
= 1
K
, contradicting the minimality of o again if r > 0. Thus
r = 0 and o|n = qo.
Denition 6. A polynomial over K, or sometimes also called a polynomial with coecients in
K, is a term of the type a
k
x
k
+ ... + a
1
x + a
0
with a
i
K for all i. Polynomials can in general be
added and multiplied exactly in the same way as we are used to in the complex numbers.
Lemma 7. Let n N, a K, and g(x) a polynomial with coecients in K. If
x
n
1 = (x a)
2
g(x) as polynomials (so if x
n
1 has a double root), then n
K
= 0
K
.
Proof. We will just mimic the proof of lemma 3:
Set y = x a, then (y + a)
n
1 = y
2
g(y + a). By expanding the LHS we get
y
n
+ ... + n
K
a
n1
y + (a
n
1), and the RHS gives ... + 0
K
y + 0
K
, thus n
K
a
n1
= 0
K
and
a
n
= 1, giving n
K
= n
K
1
K
= n
K
a
n
= (n
K
a
n1
) a = 0
K
a = 0
K
.
Since they have integer coecients, we can treat the cyclotomic polynomials as polynomials over
any eld K. The same holds for all the other polynomials that will come and be viewed in some
eld.
Theorem 13. (main theorem on cyclotomic polynomials)
Let n N again. If there is an a K with
n
(a) = 0, then n
K
= 0
K
or ord
K
(a) = n.
Proof. Another one we can the proof copy for:
Assume that o := ord
K
(a) = n (the order exists since a
n
= 1
K
). Then o|n by the order lemma, so
we get that
x
n
1 =
n
(x) (x
o
1)

d|n, do
d=n

d
(x)
by theorem 8. Now by denition
n
(a) = 0
K
and a
o
1 = 0
K
, thus
n
(x) = (x a) g(x) and
x
o
1 = (x a) h(x) with g(x), h(x) polynomials over K. But by this x
n
1 = (x a)
2
j(x)
with j(x) = g(x) h(x)

d|n, do
d=n

d
(x).
Now using lemma 7 we get n
K
= 0
K
.
9
If we have a eld K, we can get another one containing K, e.g. by the following process:
Theorem 14. If K is a eld and s K is such that x
2
= s has no solution x K, then the set
L = K[

s] of numbers of type a + b

s (with a + b

s = c + d

s i a = c, b = d) with the
canonical and intuitive addition (a + b

s) + (c + d

s) = (a + c) + (b + d)

s and multiplication
(a +b

s) (c +d

s)[= ac +ad

s +b

sc +b

s d

s] = (ac +sbd) +(ad +bc)

s is again a eld
(with

s
2
= s). Additionally, K is a subset, 0
K
= 0
L
, 1
K
= 1
L
such that the new addition and
multiplication are the old ones, too. One says K is a subeld of K[

s] then. This especially

implies that n
K
= 0 i n
L
= 0, thus the property for an integer to be zero doesnt change.
Proof. The easy checking of the properties of a eld will be left to the reader:
- associativity, commutativity, distributivity are easy to check directly
- 0
L
= 0 + 0

s, 1
L
= 1 + 0

s
- (a + b

s) = (a) + (b)

s, (a + b

s)
1
= (a(a bs
2
)
1
) + (b(a bs
2
)
1
)

s (here it
has rst to be shown that a
2
b
2
s = 0 a = 0
K
= b).
K is a subeld by the numbers of type a +0

s (again just checking or simply intuition); the rest

follows from this.
Corollary 3. If 2
K
= 0
K
(in fact, this restriction is not necessary), a quadratic equation
y
2
py + q = 0 has always exactly two solutions y
1
, y
2
(counting roots with multiplicity, thus
double roots are counted twice) in some eld L containing K. Then also y
1
+ y
2
= a and
y
1
y
2
= b (Vietas theorem).
Proof. Exactly the same way one solves quadratic equations normally works (we need 2
K
= 0
K
to be able to divide by 2
K
):
y
2
ay + b = 0
_
y
a
2
K
_
2
+ b
a
2
4
K
= 0
_
y
a
2
K
_
2
=
a
2
4
K
b.
Now if x
2
=
a
2
4
b has a solution
_
a
2
4
b K, we could proceed (here we use Lemma 5) with
y
a
2
K
=
_
a
2
4
K
b y =
a
2
K

_
a
2
4
K
b and get our two solutions.
But also otherwise, we just consider L = K
__
a
2
4
K
b
_
and proceed then.
The other properties follow directly from expanding (y y
1
)(y y
2
) = y
2
(y
1
+ y
2
)y + (y
1
y
2
),
where y
1
, y
2
are the solutions found before.
Primes 1 mod n
We are now able to construct the primes we want:
10
Theorem 15. If
n
(x) = 0 has a root a in F
p
(p prime), then p|2n or p 1 mod n.
Proof. We exclude p = 2 (we already have p|2n then).
We are looking for an b = 0 with b +
1
b
= a which happens i b
2
ab + 1 = 0. Let y
1
and y
2
be
the solutions of y
2
ay + 1 = 0 (either in F
p
or in the eld constructed in corollary 3); clearly
y = 0 is not a solution, so we can always set b = y
1
to get b +
1
b
= a.
Now y
p
1
is also a solution of the equation because using corollary 2 twice we get
0 = 0
p
= (y
2
1
ay
1
+ 1)
p
=
_
y
2
1
_
p
+ (ay
1
+ 1)
p
= (y
p
1
)
2
a
p
y
p
1
+ 1
p
= (y
p
1
)
2
ay
p
1
+ 1
(here we used that a
p
= a, which is just Fermats little theorem a
p
a mod p since a is a
standard residue mod p). But y
2
ay + 1 = 0 has just two solutions (corollary 3 again), thus
y
p
1
= y
1
or y
p
1
= y
2
. Before we start considering those two cases, we see (by denition of
n
(x))
that

n
(y
1
) = y
(n)
2
1

n
_
y
1
+
1
y
1
_
= y
(n)
2
1
0 = 0.
Now using the main theorem on cyclotomic polynomials yields p|n or ord(b) = n. Assume that
ord(b) = n from now on since otherwise (p|n) we are already done.
Case 1: y
p
1
= y
1
, thus y
p1
1
= 1, giving n = ord(y
1
)|p 1 by the order lemma; but the latter means
nothing else than p 1 mod n.
Case 2: y
p
1
= y
2
. By Vietas theorem (see corollary 3 once time) we have y
1
y
2
= 1 y
2
=
1
y
1
. Using
this gives y
p
1
=
1
y
1
, implying y
p+1
1
= 1. Again by the order lemma this gives n|p + 1, thus
p 1 mod n.
Now nothing more is to be shown.
Corollary 4. Let p be an odd (thus p = 2) prime divisor of
n
(k) for some integer k. Then p|n
or p 1 mod n. (We will never use this corollary, but the theorem itself.)
Our last problem is to seperate the divisors 1 mod n from those 1 mod n. The
polynomials
n
(x) are not the best to do this, so we will construct a similar one.
Lemma 8. There is a rational number t with
n
(t) < 0.
Proof. By denition (
n
+
1
n
) =
(n)
2
n

n
(
n
) = 0, and
n
+
1
n
=
n
+
n
= 2Re(
n
) R.
There are also no double roots of
n
(x) in C because that would give double roots of
n
(x).
Since
n
(x) is a polynomial without double roots, it exactly changes its sign at its roots. Since
there is a real root (e.g. 2Re(
n
)), there is a change of sign and thus also a real number r with
(r) < 0. If we choose a rational t close enough to r (here we use that polynomials give
continuous functions), we still have
n
(t) < 0.
11
Denition 7. We take xed integers a
n
, b
n
such that
n
_
an
bn
_
< 0 (such a
n
, b
n
exist be the
previous lemma) and take k to be the degree of
n
(x).
Then we dene
n
(x) := b
k
n

n
_
x +
an
bn
_
.
At last, we set c
n
=
n
(0) < 0 and then
n
(x) :=
(c
n
x)
c
n
.
Lemma 9. The polynomials
n
(x) and
n
(x) have integers as coecients (especially c
n
is an
integer) and a positive leading coecient.
Proof. At rst we prove that
n
(x) has integers as coecients:
Let
n
(x) = r
k
x
k
+ ... + r
1
x + r
0
(all r
i
are integers then) such that we have

n
(x) = b
k
n
r
k
_
x +
an
bn
_
k
+ ... + b
k
n
r
1
_
x +
an
bn
_
+ b
k
n
r
0
, so it suces to show that the polynomials
b
k
n
r
i
_
x +
an
bn
_
i
are integral for i = 0, 1, ..., k. But this follows directly from the binomial theorem:
b
k
n
r
i
_
x +
a
n
b
n
_
i
= b
k
n
i

m=0
r
k
x
im
a
m
n
b
m
n
_
i
m
_
=
i

m=0
b
km
n
r
k
x
im
a
m
n
_
i
m
_
,
where only integers occure (b
km
n
is always an integer if m k).
Let
n
(x) = s
k
x
k
+ ... + s
1
x + s
0
with integers s
i
now (s
0
=
n
(0) = c
n
). Thus

n
(x) =

n
(c
n
x)
c
n
=
s
k
c
k
n
x
k
c
n
+ ... +
s
1
c
n
x
c
n
+
s
0
c
n
,
has only integers as coecients. Indeed
s
0
cn
= 1 Z and
s
i
c
i
n
cn
= s
i
c
i1
n
Z for i 1. The sign
of the leading coecient of
n
(x),
n
(x),
n
(x) and
n
(x) never changes (since c
n
> 0), thus it
suces to show that the one of
n
(x) is positive. But this is clear from the denition when we
look back how they are dened.
We just have to show that we didnt lose too much of the properties of
n
(x).
Theorem 16. Let p be a prime divisor of
n
(k) not dividing 2b
n
c
n
n (k some given integer).
Then p 1 mod n.
Proof. Lets work in the eld F
p
again. There we have 0 =
n
(k) =
n(cnk)
cn
, thus
n
(c
n
k) = 0, thus
b
k
n

n
_
k +
an
bn
_
= 0. But b
n
= 0 in this eld, so after multiplying with (b
1
n
)
k
this gives

n
_
k +
an
bn
_
= 0. By theorem 15 we are nished.
Now the goal is near. But we will need all the developed techniques.
Theorem 17. There are innitely many primes p 1 mod n.
12
Proof. We can assume n to be greater than 2 since otherwise its trivial.
As expected, we assume that there are only nitely many such primes p
1
, ..., p
k
1 mod n and
call their product P. Lets take an integer k such that
n
(k 2b
n
c
n
nP) > 1 (exists since the
leading coecient of
n
(x) is positive)and factor
n
(k 2b
n
c
n
nP) = q
1
q
2
...q
m
into not neccessary
dierent primes q
i
. We have
n
(k 2b
n
c
n
nP)
n
(0) =
(0)
(0)
= 1 mod 2b
n
c
n
nP and especially

n
(k 2b
n
c
n
nP) 1 mod n. Thus
n
(k 2b
n
c
n
nP) is coprime to 2b
n
c
n
n, thus by theorem 16
the q
i
are 1 mod n. The same way we get that the q
i
are dierent from the p
j
, thus by
assumption q
i
1 mod n for all i, giving that
1
n
(k 2b
n
c
n
nP) = q
1
q
2
...q
m
1 1 ... 1 = 1 mod n, contradicting n > 2.
13