# A note on Euclid’s Theorem concerning the infinitude of the primes

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/a-note-on-euclids-theorem-concerning-the-infinitude-of-the-primes

- **Authors:** Filip Saidak
- **Published:** 2016
- **Topic:** Mathematics
- **Original:** https://s3-us-west-1.amazonaws.com/fermatslibrary/uploads%2F1484866734551-zkymmtse7me250kd-3d78da7d3858615bb114cd974171e801%2FAUMB-2016-2.pdf
- **Pages:** 2
- **Annotations:** 4 comments in 4 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-note-on-euclids-theorem-concerning-the-infinitude-of-the-primes

## Annotations

### Annotation 1 (page 1)

Beside the passage: “the inﬁnitude of the primes”

**Annotation** by F. Saidak (2017-01-23):

> 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.

### Annotation 2 (page 1)

Beside the passage: “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 …”

**Annotation** by Mike Chu (2017-02-13):

> 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.

### Annotation 3 (page 1)

Beside the passage: “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?”

**Annotation** by Mike Chu (2017-02-13):

> 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!

### Annotation 4 (page 1)

Beside the passage: “p m > m + 2 p m+1 ⇐⇒ 1 − 1 m + 2 > 1 p . (1)”

**Annotation** by Mike Chu (2017-02-13):

> 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)

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

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 [Annotation 1]

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 [Annotation 2] 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 [Annotation 3] powers of a ﬁnite number of primes cover the entire set N?

We investigate the factorization geometrically and consider the canonical representation as an operation (on exponents) in two dimensions, with single prime powers representing 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 > [Annotation 4] 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

#### Page 2

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.

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-note-on-euclids-theorem-concerning-the-infinitude-of-the-primes. More annotated papers: https://fermatslibrary.com/llms.txt
