Number Theory: An Introduction to Mathematics

X A Character Study...........................................

1 PrimesinArithmeticProgressions

Letaandmbe integers with 1≤a<m.Ifaandmhave a common divisord>1,
then no term after the first of the arithmetic progression

a,a+m,a+ 2 m,... (∗)

is a prime. Legendre (1788) conjectured, and later (1808) attempted a proof, thatif
a and m are relatively prime, then the arithmetic progression(∗)contains infinitely
many primes.
Ifa 1 ,...,ahare the positive integers less thanmand relatively prime tom,andif
πj(x)denotes the number of primes≤xin the arithmetic progression

aj,aj+m,aj+ 2 m,...,

then Legendre’s conjecture can be stated in the form

πj(x)→∞ asx→∞ (j= 1 ,...,h).

Legendre (1830) subsequently conjectured, and again gave a faulty proof, that

πj(x)/πk(x)→1asx→∞ for allj,k.

Since the total numberπ(x)of primes≤xsatisfies

π(x)=π 1 (x)+···+πh(x)+c,

wherecis the number of different primes dividingm, Legendre’s second conjecture is
equivalent to

πj(x)/π(x)→ 1 /h asx→∞ (j= 1 ,...,h).

Hereh=φ(m)is the number of positive integers less thanmand relatively prime tom.
If one assumes the truth of the prime number theorem, then the second conjecture is

W.A. Coppel, Number Theory: An Introduction to Mathematics, Universitext,
DOI: 10.1007/978-0-387-89486-7_10, © Springer Science + Business Media, LLC 2009

399