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 infinitude 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 infinitude 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 final 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 infinitely
many prime numbers. It has been one of the cornerstones of mathematical thought.
More than a dozen different proofs of this result, with many clever simplifications 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 first
one, but perhaps equally fundamental. It makes use of the ancient concept of proportion,
the theory of which was perfected by Pythagoras, Eudoxus and finally 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 finite 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 fixed 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 define
∇(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 infinitude
of the prime numbers. This is because the vertical dimension is (trivially) infinite, 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 finite composition of such powers, and therefore only an infinite horizontal
dimension could possibly compensate for the growing deficit 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.
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 finite 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.