4 1. Elementary Prime Number Theory, I
Second, it may be used to prove that certain arithmetic progressions contain
infinitely many primes. To see this, suppose that p  ni and note that by
(1.1), we have
22i−1
≡ −1 (mod p), so that
22i
≡
(22i−1
)2
≡ 1 (mod p).
Hence the order of 2 modulo p is precisely
2i.
Thus
2i

(Z/pZ)×
= p − 1, so
that p ≡ 1 (mod
2i).
As a consequence, for any fixed k, there are infinitely
many primes p ≡ 1 (mod
2k):
choose a prime pi dividing ni for each i ≥ k.
In §9.1 we will prove the more general result that for each m ≥ 1, there are
infinitely many primes p ≡ 1 (mod m).
A related method of proving the infinitude of the primes is as follows:
Let a1 a2 a3 · · · be a sequence of positive integers with the property
that
gcd(i, j) = 1 =⇒ gcd(ai,aj) = 1.
Moreover, suppose that for some prime p, the integer ap has at least two
distinct prime divisors. Then if p1,...,pk were a list of all the primes, the
integer
ap1 ap2 · · · apk
would possess at least k + 1 prime factors: indeed, each factor exceeds 1,
the factors are pairwise relatively prime, and one of the factors is divisible
by two distinct primes. So there are k + 1 k primes, a contradiction.
It remains to construct such a sequence. We leave to the reader the easy
exercise of showing that an =
2n
− 1 has the desired properties (note that
a11 = 23 · 89). The original version of this argument, where an is instead
chosen as the nth Fibonacci number, is due to Wunderlich [Wun65]. The
generalization presented here is that of Hemminger [Hem66].
Saidak [Sai06] has recently given a very simple argument making use of
coprimality. Start with a natural number n 1. Because n and n + 1 are
coprime, the number N2 := n(n + 1) must have at least two distinct prime
factors. By the same reasoning,
N3 := N2(N2 + 1) = n(n + 1)(n(n + 1) + 1)
must have at least three distinct prime factors. In general, having con
structed Nj with at least j different prime factors, the number Nj+1 :=
Nj(Nj + 1) must have at least j + 1.
4. The EulerRiemann zeta function
For complex numbers s with real part greater than 1, define the zeta function
by putting
ζ(s) :=
∞
n=1
1
ns
.