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