A theorem sometimes called ``Euclid's First Theorem'' or Euclid's Principle states that if is a Prime and , then or (where means Divides). A Corollary is that (Conway and Guy 1996). The Fundamental Theorem of Arithmetic is another Corollary (Hardy and Wright 1979).

Euclid's Second Theorem states that the number of Primes is Infinite. This theorem, also called the
Infinitude of Primes theorem, was proved by Euclid in Proposition IX.20 of the Elements.
Ribenboim (1989) gives nine (and a half) proofs of this theorem. Euclid's elegant proof proceeds as follows. Given a
finite sequence of consecutive Primes 2, 3, 5, ..., , the number

(1) |

(2) |

A similar argument shows that and

(3) |

It is also true that there are runs of Composite Numbers which are arbitrarily long. This can
be seen by defining

(4) |

(5) | |||

(6) | |||

(7) |

Guy (1981, 1988) points out that while
is not necessarily Prime, letting be the next Prime
after
, the number
is almost always a Prime, although it has
not been proven that this must *always* be the case.

**References**

Ball, W. W. R. and Coxeter, H. S. M. *Mathematical Recreations and Essays, 13th ed.* New York: Dover, p. 60, 1987.

Conway, J. H. and Guy, R. K. ``There are Always New Primes!''
In *The Book of Numbers.* New York: Springer-Verlag, pp. 133-134, 1996.

Cosgrave, J. B. ``A Remark on Euclid's Proof of the Infinitude of Primes.'' *Amer. Math. Monthly*
**96**, 339-341, 1989.

Courant, R. and Robbins, H. *What is Mathematics?: An Elementary Approach to Ideas and Methods, 2nd ed.*
Oxford, England: Oxford University Press, p. 22, 1996.

Dunham, W. ``Great Theorem: The Infinitude of Primes.''
*Journey Through Genius: The Great Theorems of Mathematics.* New York: Wiley, pp. 73-75, 1990.

Guy, R. K. §A12 in *Unsolved Problems in Number Theory.* New York: Springer-Verlag, 1981.

Guy, R. K. ``The Strong Law of Small Numbers.'' *Amer. Math. Monthly* **95**, 697-712, 1988.

Hardy, G. H. *A Mathematician's Apology.* Cambridge, England: Cambridge University Press, 1992.

Ribenboim, P. *The Book of Prime Number Records, 2nd ed.* New York: Springer-Verlag, pp. 3-12, 1989.

© 1996-9

1999-05-25