6 Six proofs of the infinity of primes Let N be the number of positive integers nN which are divisible by at least one big prime,and Ns the number of positive integers nN which have only small prime divisors.We are going to show that for a suitable N Nb+N。<N, which will be our desired contradiction,since by definition N+N.would have to be equal to N. To estimate N note that counts the positive integers nN which are multiples of pi.Hence by (1)we obtain (2) >k+1 Let us now look at N.We write every nN which has only small prime divisors in the form n=ab,where an is the square-free part.Every an is thus a product of different small primes,and we conclude that there are precisely2 different square---free parts..Furthermore,.asbn≤√元≤√F, we find that there are at most vN different square parts,and so Ns≤2kVN Since (2)holds for any N,it remains to find a number N withN or1VN,and for this N =22k+2 will do. ☐ Appendix:Infinitely many more proofs Our collection of proofs for the infinitude of primes contains several other old and new treasures,but there is one of very recent vintage that is quite different and deserves special mention.Let us try to identify sequences S of integers such that the set of primes Ps that divide some member of S is infinite.Every such sequence would then provide its own proof for the infinity of primes.The Fermat numbers Fn studied in the second proof form such a sequence,while the powers of 2 don't.Many more examples are provided by a theorem of Issai Schur,who showed in 1912 that for every nonconstant polynomial p(x)with integer coefficients the set of all nonzero values{p(n)≠0：n∈N}is such a sequence..For the polynomial p(x)=z,Schur's result gives us Euclid's theorem.As another example, forp(x）=x2+1 we get that the“squares plus one”contain infinitely many different prime factors. The following result due to Christian Elsholtz is a real gem:It generalizes Schur's theorem,the proof is just clever counting,and it is in a certain sense Issai Schur best possible.6 Six proofs of the infinity of primes Let Nb be the number of positive integers n ≤ N which are divisible by at least one big prime, and Ns the number of positive integers n ≤ N which have only small prime divisors. We are going to show that for a suitable N Nb + Ns < N, which will be our desired contradiction, since by definition Nb + Ns would have to be equal to N. To estimate Nb note that N pi counts the positive integers n ≤ N which are multiples of pi. Hence by (1) we obtain Nb ≤  i≥k+1 N pi  < N 2 . (2) Let us now look at Ns. We write every n ≤ N which has only small prime divisors in the form n = anb2 n, where an is the square-free part. Every an is thus a product of different small primes, and we conclude that there are precisely 2k different square-free parts. Furthermore, as bn ≤ √n ≤ √ N, we find that there are at most √ N different square parts, and so Ns ≤ 2k √ N. Since (2) holds for any N, it remains to find a number N with 2k √ N ≤ N 2 or 2k+1 ≤ √ N, and for this N = 22k+2 will do. Appendix: Infinitely many more proofs Our collection of proofs for the infinitude of primes contains several other old and new treasures, but there is one of very recent vintage that is quite different and deserves special mention. Let us try to identify sequences S of integers such that the set of primes PS that divide some member of S is infinite. Every such sequence would then provide its own proof for the infinity of primes. The Fermat numbers Fn studied in the second proof form such a sequence, while the powers of 2 don’t. Many more examples Issai Schur are provided by a theorem of Issai Schur, who showed in 1912 that for every nonconstant polynomial p(x) with integer coefficients the set of all nonzero values {p(n) =0: n ∈ N} is such a sequence. For the polynomial p(x) = x, Schur’s result gives us Euclid’s theorem. As another example, for p(x) = x2 + 1 we get that the “squares plus one” contain infinitely many different prime factors. The following result due to Christian Elsholtz is a real gem: It generalizes Schur’s theorem, the proof is just clever counting, and it is in a certain sense best possible.