The lowest powers of $2$ are $1, 2, 4, 8$, and there are four of ...
Prof. Saidak's 2006 paper has been [previously annotated on Fermat’...
According to the fundamental theorem of arithmetic, every positive ...
Note that: $$\frac{m+1}{p^m}>\frac{m+2}{p^{m+1}} \equiv \frac{... Acta Universitatis Matthiae Belii, series Mathematics Issue 2016, 25–26, ISSN 1338-7111 Online Edition, http://actamath.savbb.sk A note on Euclid’s Theorem concerning the inﬁnitude of the primes Filip Saidak Department of Mathematics and Statistics, University of North Carolina, Greensboro, NC 27402, U.S.A. saidak@protonmail.ch Abstract We present another elementary proof of Euclid’s Theorem concerning the inﬁnitude of the prime numbers. This proof is “geometric” in nature and it employs very little beyond the concept of “proportion. Received 21 July 2016 Revised 25 October 2016 Accepted in ﬁnal form 27 October 2016 Published online 20 November 2016 Communicated with Miroslav Haviar. Keywords Euclid, prime numbers. MSC(2010) 11A41. Euclid’s Theorem ([2], Book IX, Proposition 20) establishes the existence of inﬁnitely many prime numbers. It has been one of the cornerstones of mathematical thought. More than a dozen diﬀerent proofs of this result, with many clever simpliﬁcations and variants, have been published over the past two millennia (for lists of proofs and good discussions of their historical relevance, see [1], [3], [4] and [6]). A decade ago, in [5], we gave a short direct proof of Euclid’s Theorem that has received a surprising amount of attention. Here we would like to present another idea, not quite as simple as the ﬁrst one, but perhaps equally fundamental. It makes use of the ancient concept of proportion, the theory of which was perfected by Pythagoras, Eudoxus and ﬁnally Euclid himself (a fact demonstrated by the results summarized in Book V of his Elements [2]). We rephrase the problem slightly. The question we ask is: Why cannot products of powers of a ﬁnite number of primes cover the entire set N? We investigate the factorization geometrically and consider the canonical representa- tion as an operation (on exponents) in two dimensions, with single prime powers repre- senting what we will call the “vertical” and their products the “horizontal” dimensions. Vertical Dimension. For a ﬁxed prime number p, and 0 i m, there are m + 1 positive integers that can be written in the form p i , the largest of which is p m . Since, clearly, m + 1 (1 + 1) m = 2 m p m , many integers are not of this form; so for the proportion (p m ) of these powers (up to p m ) we not only have (p m ) < 1, for all m > 1 (as well as (p m ) 0, as m ), but also (p m ) > (p m+1 ), because m + 1 p m > m + 2 p m+1 1 1 m + 2 > 1 p . (1) Thus, considered vertically, the proportions are monotonically decreasing. Copyright c 2016 Matej Bel University 26 Filip Saidak Horizontal Dimension. Recall that a function f : N C is called multiplicative, if f(1) = 1 and f (ab) = f (a)f (b), for all a, b N with gcd(a, b) = 1. A critically important property of the proportions is their multiplicativity. For all k 2, let us deﬁne (p m 1 1 · · · p m k k ) := #{n = p a 1 1 · · · p a k k : 0 a j m j , for 1 j k} p m 1 1 · · · p m k k , then, for all permutations of exponents m i , we have (p m 1 1 · · · p m k k ) = (p m 1 1 ) · · · (p m k k ) < 1. (2) In other words, the multiplicativity of implies the horizontal monotonicity. Combining these two monotonic orthogonal trends is enough to prove the inﬁnitude of the prime numbers. This is because the vertical dimension is (trivially) inﬁnite, and (1) implies an ever-increasing sparseness of integers represented by a given prime power; while from the monotonicity property of (2) it follows that the same will remain true upon any ﬁnite composition of such powers, and therefore only an inﬁnite horizontal dimension could possibly compensate for the growing deﬁcit and create a complete cover of N, guaranteed by the unique factorization theorem. Acknowledgements I would like to thank Prof. Peter Zvengrowski (University of Calgary), the referee and the Editor-in-chief for several useful comments. References [1] Dickson, L. E., “History of the theory of numbers. Vol 1, Chapter XVIII, 2nd ed., Chelsea Publishing, New York, 1992. [2] Euclid, “Elements. Alexandria, c. 300 BC (for a modern edition, see Heath, T. L., “Thirteen Books of Euclid’s Elements. Dover, New York, 1956). [3] Narkiewicz, W., “The development of prime number theory. From Euclid to Hardy and Littlewood. Springer Monographs in Mathematics. Springer-Verlag, Berlin, 2000. [4] Ribenboim, P., “The little book of bigger primes. Springer-Verlag, New York, 2004. [5] Saidak, F., A new proof of Euclid’s theorem, Amer. Math. Monthly 113 (2006), no. 10, 937–938. [6] Sierpiński, W., “Elementary theory of numbers”, 2nd Edition, Polish Sci. Pub., Warsaw, 1988. Prof. Saidak's 2006 paper has been [previously annotated on Fermat’s Library](http://fermatslibrary.com/s/a-new-proof-of-euclids-theorem). Unlike Euclid’s proof which was by way of contradiction, Saidak's proof avoids the "reductio ad absurdum" method and is constructive. The lowest powers of 2 are 1, 2, 4, 8, and there are four of them \leq 8 (their proportion is 1/2). The lowest powers of 3 are 1, 3, 9, and we have three of them \leq 9 (the proportion is 1/3). How many integers can be constructed as products of two terms, one from each of these two set? Twelve; and the largest of these numbers is 72 = 8 \times 9 (which means that their proportion is 1/6 = 1/2 \times 1/3). So the proportions are multiplicative! (The equation (2) of the paper.) This idea woke me up at 3 AM one night last Spring, and I wrote it down on the back of a box of Kinder chocolate on the nightstand, before falling back asleep. The rest of the proof comes out easily (and leads one to consider the factorization of integers geometrically) -- a 30 minute exercise after breakfast. Note that:$$ \frac{m+1}{p^m}>\frac{m+2}{p^{m+1}} \equiv \frac{m+1}{m+2}>\frac{1}{p} \\ \frac{m+1+1-1}{m+2}>\frac{1}{p} \equiv \frac{m+2}{m+2} - \frac{1}{m+2}>\frac{1}{p}  To prove that $1- \frac{1}{m+2}>\frac{1}{p}$ we just have to note that the smallest value of the left side is when $m=1$, $1- \frac{1}{m+2}=\frac{2}{3}$ whie the biggest value of the right side is when $p=2$, $\frac{1}{p} = \frac{1}{2}$, and so the left side will always be greater than the right side. As we can see in the following graph, the proportion $\nabla (2^n)$ decreases very rapidly as $n$ increases. ![](http://i.imgur.com/6tasHfo.jpg) According to the fundamental theorem of arithmetic, every positive integer n > 1 can be represented in exactly one way as a product of prime powers. Euclid’s theorem is about proving that there are infinitely prime numbers. In this paper Saidak combines the two and raises the question: if there is a ﬁnite number of primes can they cover the entire set $\mathbb N$ without violating the fundamental theorem of arithmetic? If a finite number of primes violates the fundamental theorem of arithmetic then there must be infinitely many prime numbers!