# A new proof of Euclid's Theorem

> 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-new-proof-of-euclids-theorem

- **Authors:** Filip Saidak
- **Topic:** Mathematics
- **Original:** http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.206.1507&rep=rep1&type=pdf
- **Pages:** 2
- **Annotations:** 16 comments in 8 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/a-new-proof-of-euclids-theorem

## Annotations

### Annotation 1 (page 1)

Beside the passage: “A NEW PROOF OF EUCLID’S THEOREM”

**Annotation** by Luís Batalha (2016-01-10):

> Euclid's Theorem is one of the fundamental results in number theory, which asserts that there are infinitely many prime numbers. The first proof of Euclid's Theorem was in the 9th book of Euclid's geometric treatise ( Elements) in 300 B.C. .
>
> ![The frontispiece of Sir Henry Billingsley's first English version of Euclid's Elements, 1570](https://upload.wikimedia.org/wikipedia/commons/c/cf/Title_page_of_Sir_Henry_Billingsley%27s_first_English_version_of_Euclid%27s_Elements%2C_1570_%28560x900%29.jpg)
>
> Figure: The frontispiece of Sir Henry Billingsley's first English version of Euclid's Elements, 1570

### Annotation 2 (page 1)

Beside the passage: “FILIP SAIDAK”

**Annotation** by Luís Batalha (2016-01-10):

> In this paper Filip Saidak, Professor at The University of North Carolina at Greensboro, comes up with a proof that is conceptually even simpler than Euclid's proof. Euclid's Theorem has been proved by several other famous mathematicians including Euler and Paul Erdos. Euler's and Erdo's proofs relied on the  fundamental theorem of arithmetic: that every integer has a unique prime factorization.  To see their proofs [click here](https://en.wikipedia.org/wiki/Euclid%27s_theorem#Proof_using_factorials)

### Annotation 3 (page 1)

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

**Annotation** by Luís Batalha (2016-01-10):

> $Q = p_1.p_2...p_k + 1= P+1 $ is either prime or not.
>
> 1. If Q is prime then by contradiction there's one more prime in the set P
>
> 2. If Q is not prime, there is a $p_i$ in the set P that divides Q. By definition, since $p_i$ is in the list it will also divide P. If $p_i$ divides Q and P it will also divide its difference $Q-P=1$, which is a contradiction since no prime number divides 1. This means that $p_i$ is a prime number and can't be in the list!
>
> As can be seen, Euclid proves the result by contradiction, assuming that the initial set P contains all the prime numbers. Saidak's proof unlike Euclid's avoids the "reductio ad absurdum" method.

**Reply** by Daniel Roca González (2016-01-12):

> While Euclid's proof is usually reworded like this, it is not actually necessary to use contradiction in this way. Instead of assuming P is the finite set of all prime numbers, you can take $P$ to be any finite set of primes, and follow in the same way.
>
> The proof shows that $Q$ has a prime factor which is not in $P$, which already proves the premise since $P$ was arbitrary. You can use this iteratively(just put the new prime in the set $P$ and apply the proof again to get a new prime) to generate an infinite set of primes, just like Saidak's proof, and it's just as simple.

**Reply** by Tom McNamara (2016-01-13):

> Daniel Roca González: Yes.

### Annotation 4 (page 1)

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

**Annotation** by Heinrich Hartmann (2016-01-12):

> Why are you not specific here. Just pick one, say 2.

**Reply** by Tom McNamara (2016-01-13):

> Saidak's new proof seems awfully similar to his restatement of Euclid's proof. In both cases the key is that any finite set of primes $\{p_1, p_2, ..., p_n\}$ can be extended by appending the prime factors of $p_1p_2(...)p_n+1$, which don't belong to ${p_1, ..., p_n}$.

### Annotation 5 (page 1)

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

**Annotation** by Luís Batalha (2016-01-10):

> Two numbers are coprime if their highest common factor (or greatest common divisor) is 1.

### Annotation 6 (page 1)

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

**Annotation** by Luís Batalha (2016-01-10):

> Besides being a concise constructive proof, Saidak's relies solely on the property that consecutive integers are coprime and that's what makes this proof unique.

**Reply** by Heinrich Hartmann (2016-01-12):

> Why should there be 3 different prime factors?

**Reply** by Heinrich Hartmann (2016-01-12):

> And even if there were three, why can't two of them coincede? E.g. $2 \cdot 2 \cdot 3$ ? You are not giving a complete argument here.

**Reply** by Joe Koester (2016-01-12):

> Coprime means that two numbers share no common prime factors. $n$ and $n+1$ share no prime factors, so $n(n+1)$ must have at least 2 prime factors. Consequently, the number after $n(n+1)$, $n(n+1)+1$ shares no common factors with $n(n+1)$, so it must share no common factors with either $n$ or $n+1$ since you can't get new prime factors by multiplying together $n$ and $n+1$

**Reply** by Erik Postma (2016-01-12):

> @Heinrich The implicit claim is that $N_i$ contains at least $i$ different prime factors. $N_i + 1$ is coprime with $N_i$, so it has $\geq 1$ prime factor different from the $\geq i$ different prime factors in $N_i$. Thus, $N_{i+1} := N_i (N_i + 1)$ has $\geq i+1$ different prime factors.  Together with the base case that $N_1 := n > 1$ has at least one prime factor, this proves the claim via induction.

**Reply** by Heinrich Hartmann (2016-01-26):

> Thx @Erik for spelling it out. I think this argument deserves a little more elaboration than just "Similarly" in a proof of an elementary result, that should be digestible by beginners.

### Annotation 7 (page 1)

Beside the passage: “1”

**Annotation** by Heinrich Hartmann (2016-01-12):

> This is another incomplete argument. Be precise: "which process" and why are the generated numbers different from each other?

### Annotation 8 (page 2)

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

**Annotation** by Heinrich Hartmann (2016-01-12):

> IMO you are not giving a complete argument here. If you spell out the details to make it rigorous by modern standards, you will likely need more then half a page.
>
> Euclids proof, on the other hand is super clean and concise.

## Full text

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

#### Page 1

American Math. Monthly, Vol 113, No. 10, December 2006.

A NEW PROOF OF EUCLID’S THEOREM [Annotation 1]

FILIP SAIDAK [Annotation 2]

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 Alexandria, 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 [Annotation 3] 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 [Annotation 4] n and n + 1 are consecutive integers, they must be coprime. Hence the [Annotation 5] 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 [Annotation 6] indeﬁnitely, so the number of primes must be inﬁnite. 

1 [Annotation 7]

#### Page 2

Analysis. The proof just given is conceptually even simpler than the [Annotation 8] 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), P´olya (1921), Erd˝os (1938), Bellman (1947), F¨urstenberg (1955), Barnes (1976), Washington (1980), and others. Goldbach’s proof (see [4], p.4), which uses pairwise coprimality 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 Kostolansky (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

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/a-new-proof-of-euclids-theorem. More annotated papers: https://fermatslibrary.com/llms.txt
