Instructions: To add a question/comment to a specific line, equation, table or graph simply click on it.
Click on the annotations on the left side of the paper to read and reply to the questions and comments.
Euclid's Theorem is one of the fundamental results in number theory...
In this paper Filip Saidak, Professor at The University of North Ca...
$Q = p_1.p_2...p_k + 1= P+1$ is either prime or not. 1. If Q i...
Why are you not specific here. Just pick one, say 2.
Two numbers are coprime if their highest common factor (or greatest...
Besides being a concise constructive proof, Saidak's relies solely ...
This is another incomplete argument. Be precise: "which process" an...
IMO you are not giving a complete argument here. If you spell out t...
American Math. Monthly, Vol 113, No. 10, December 2006.
A NEW PROOF OF EUCLID’S THEOREM
FILIP SAIDAK
A prime number is an integer greater than 1 that is divisible only
by 1 and itself. Mathematicians have been studying primes and their
properties for over twenty-three centuries. One of the very ﬁrst results
concerning these numbers was presumably proved by Euclid of Alexan-
dria, sometime before 300 B.C. In Book IX of his legendary Elements
(see [2]) we ﬁnd Proposition 20, which states:
Proposition. There are inﬁnitely many prime numbers.
Euclid’s proof (modernized). Assume to the contrary that the set
P of all prime numbers is ﬁnite, say P = {p
1
, p
2
, · · · , p
k
} for a positive
integer k. If Q := (p
1
p
2
· · · p
k
)+1, then gcd(Q, p
i
) = 1 for i = 1, 2, · · · k.
Therefore Q has to have a prime factor diﬀerent from all existing primes.
That is a contradiction.
Today many proofs of Euclid’s theorem are known. It may come as a
surprise that the following almost trivial argument has not been given
before:
New proof. Let n be an arbitrary positive integer greater than 1. Since
n and n + 1 are consecutive integers, they must be coprime. Hence the
number N
2
= n(n + 1) must have at least two diﬀerent prime factors.
Similarly, since the integers n(n+1) and n(n+1)+1 are consecutive, and
therefore coprime, the number N
3
= n(n + 1)[n(n + 1) + 1] must have
at least three diﬀerent prime factors. This process can be continued
indeﬁnitely, so the number of primes must be inﬁnite.
1
Analysis. The proof just given is conceptually even simpler than the
original proof due to Euclid, since it does not use Eudoxus’s method of
“reductio ad absurdum,” proof by contradiction. And unlike most other
proofs of the theorem, it does not require Proposition 30 of Elements
(sometimes called “Euclid’s Lemma”) that states: if p is a prime and
p|ab, then either p|a or p|b. Moreover, our proof is constructive, and it
gives integers with an arbitrary number of prime factors.
Remarks. In Ribenboim [4, pp.3–11] and Narkiewicz [3, pp.1–10] one
ﬁnds at least a dozen diﬀerent proofs of the classical theorem of Euclid,
and many other variations of the arguments listed in [1], [3], and [4] have
been published over the years (in chronological order) by: Goldbach
(1730), Euler (1737 and 1762), Kummer (1878), Perott (1881), Stieltjes
(1890), Thue (1897), Brocard (1915), olya (1921), Erd˝os (1938), Bell-
man (1947), F¨urstenberg (1955), Barnes (1976), Washington (1980),
and others. Goldbach’s proof (see [4], p.4), which uses pairwise copri-
mality of Fermat numbers, seems to be closest in spirit to the argument
we have presented.
ACKNOWLEDGMENTS. Personal and virtual conversations with
Professors Paulo Ribenboim (Queen’s University) and Eduard Kos-
tolansky (Bratislava) are gratefully acknowledged. I would also like to
thank Professor W ladyslaw Narkiewicz (Wroclaw) for bringing to my
attention Hermite’s very simple proof concerning n! + 1.
References
[1] M. Aigner and G. M. & Ziegler, Proofs from THE BOOK, Springer-Verlag, Berlin,
1999
[2] T. L. Heath,The Thirteen Books of Euclid’s Elements, vol. 2, University Press,
Cambridge, 1908; 2nd ed. reprinted by Dover, New York, 1956.
[3] W. Narkiewicz, The Development of Prime Number Theory, Springer-Verlag, New
York, 2000
[4] P. Ribenboim, The New Book of Prime Number Records, Springer-Verlag, New York,
1996
2