Six proofs of the infinity of primes Third Proof.Suppose P is finite and pis the largest prime.We consider Lagrange's theorem the so-called Mersenne number 2P-1 and show that any prime factor q If G is a finite(multiplicative)group of 2P-1 is bigger than p,which will yield the desired conclusion.Let g be and U is a subgroup.then U a prime dividing 2P-1,so we have 2P=1(mod g).Since p is prime,this divides G. means that the element 2 has order p in the multiplicative group Zo}of Proof.Consider the binary rela- the field Za.This group has q-1 elements.By Lagrange's theorem (see tion the box)we know that the order of every element divides the size of the a~b:←→ba-1∈U. group,that is,we have pq-1,and hence p<q. 0 It follows from the group axioms Now let us look at a proof that uses elementary calculus. that is an equivalence relation. ■Fourth Proof.Letπ(x=#{p≤x:p∈P}be the number of primes The equivalence class containing an that are less than or equal to the real number x.We number the primes element a is precisely the coset P [pi,p2,p3,...}in increasing order.Consider the natural logarithm Ua={xa:x∈U} logz,defined as log x=dt. Since clearly Ual U.we find Now we compare the area below the graph of f(t)=with an upper step function.(See also the appendix on page 12 for this method.)Thus for that G decomposes into equivalence n≤x<n+1 we have classes,all of size U,and hence that U divides G. 口 11 logx ≤1++号+…+n+分 In the special case when U is a cyclic subgroup fa,a2,...,am}we find ≤ -where the sum extends over all m EN which have that m (the smallest positive inte- only prime divisors p <x. ger such that a"=1,called the order of a)divides the size G of Since every such m can be written in a unique way as a product of the form the group.In particular,we have II pr,we see that the last sum is equal to alGl 1. P<I pEP p<I The inner sum is a geometric series with ratiohence π(x) logx≤ 0 PEP P<I p<x 1 2 nn+l Now clearly pk>k+1,and thus Steps above the functionf(t)= Pk ≤1+= 1 Pk-1 =1+ and therefore x( logx≤ k+1 =T(x)+1. k=1 Everybody knows that logz is not bounded,so we conclude that m()is unbounded as well,and so there are infinitely many primes.4 Six proofs of the infinity of primes Third Proof. Suppose P is finite and p is the largest prime. We consider the so-called Mersenne number 2p − 1 and show that any prime factor q of 2p − 1 is bigger than p, which will yield the desired conclusion. Let q be a prime dividing 2p − 1, so we have 2p ≡ 1 (mod q). Since p is prime, this Lagrange’s theorem If G is a finite (multiplicative) group and U is a subgroup, then |U| divides |G|. Proof. Consider the binary rela￾tion a ∼ b : ⇐⇒ ba−1 ∈ U. It follows from the group axioms that ∼ is an equivalence relation. The equivalence class containing an element a is precisely the coset Ua = {xa : x ∈ U}. Since clearly |Ua| = |U|, we find that G decomposes into equivalence classes, all of size |U|, and hence that |U| divides |G|. In the special case when U is a cyclic subgroup {a, a2,...,am} we find that m (the smallest positive inte￾ger such that am = 1, called the order of a) divides the size |G| of the group. In particular, we have a|G| = 1. means that the element 2 has order p in the multiplicative group Zq\{0} of the field Zq. This group has q − 1 elements. By Lagrange’s theorem (see the box) we know that the order of every element divides the size of the group, that is, we have p | q − 1, and hence p<q. Now let us look at a proof that uses elementary calculus. Fourth Proof. Let π(x) := #{p ≤ x : p ∈ P} be the number of primes that are less than or equal to the real number x. We number the primes P = {p1, p2, p3,...} in increasing order. Consider the natural logarithm log x, defined as log x =  x 1 1 t dt. 21 1 n n+1 Steps above the function f(t) = 1 t Now we compare the area below the graph of f(t) = 1 t with an upper step function. (See also the appendix on page 12 for this method.) Thus for n ≤ x<n + 1 we have log x ≤ 1 + 1 2 + 1 3 + ··· + 1 n − 1 + 1 n ≤  1 m, where the sum extends over all m ∈ N which have only prime divisors p ≤ x. Since every such  m can be written in a unique way as a product of the form p≤x pkp , we see that the last sum is equal to p∈P p≤x  k≥0 1 pk  . The inner sum is a geometric series with ratio 1 p , hence log x ≤ p∈P p≤x 1 1 − 1 p = p∈P p≤x p p − 1 = π (x) k=1 pk pk − 1 . Now clearly pk ≥ k + 1, and thus pk pk − 1 = 1+ 1 pk − 1 ≤ 1 + 1 k = k + 1 k , and therefore log x ≤ π (x) k=1 k + 1 k = π(x)+1. Everybody knows that log x is not bounded, so we conclude that π(x) is unbounded as well, and so there are infinitely many primes.