Number Theory: An Introduction to Mathematics

400 X A Character Study

also equivalent to

πj(x)∼x/φ(m)logx (j= 1 ,...,φ(m)).

The validity of the second conjecture in this form is known as theprime number theo-
rem for arithmetic progressions.
Legendre’s first conjecture was proved by Dirichlet (1837) in an outstanding pa-
per which combined number theory, algebra and analysis. His algebraic innovation
was the use ofcharactersto isolate the primes belonging to a particular residue class
modm. Legendre’s second conjecture, which implies the first, was proved by de la
Va l l ́ee Poussin (1896), again using characters, at the same time that he proved the
ordinary prime number theorem.
Selberg (1949), (1950) has given proofs of both conjectures which avoid the use of
complex analysis, but they are not very illuminating. The prime number theorem for
arithmetic progressions will be proved here by an extension of the method used in the
previous chapter to prove the ordinary prime number theorem.
For any integera, with 1≤a<mand(a,m)=1, let

π(x;m,a)=

∑

p≤x,p≡amodm

1.

Also, generalizing the definition of Chebyshev’s functions in the previous chapter, put

θ(x;m,a)=

∑

p≤x,p≡amodm

logp,ψ(x;m,a)=

∑

n≤x,n≡amodm

Λ(n).

Exactly as in the last chapter, we can showthat the prime number theorem for arith-
metic progressions,

π(x;m,a)∼x/φ(m)logx asx→∞,

is equivalent to

ψ(x;m,a)∼x/φ(m) asx→∞.

It is in this form that the theorem will be proved.

2 Characters of Finite Abelian Groups

LetGbe an abelian group with identity elemente.AcharacterofGis a function
χ:G→Csuch that

(i)χ(ab)=χ(a)χ(b)for alla,b∈G,
(ii)χ(c)=0forsomec∈G.

Sinceχ(c)=χ(ca−^1 )χ(a), by (i), it follows from (ii) thatχ(a)=0forevery
a∈G. (Thusχis ahomomorphismofGinto the multiplicative groupC×of nonzero
complex numbers.) Moreover, sinceχ(a)=χ(a)χ(e),wemusthaveχ(e)=1. Since
χ(a)χ(a−^1 )=χ(e), it follows thatχ(a−^1 )=χ(a)−^1.