TOPICS
Search

Euclid's Theorems


A theorem sometimes called "Euclid's first theorem" or Euclid's principle states that if p is a prime and p|ab, then p|a or p|b (where | means divides). A corollary is that p|a^n=>p|a (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 (Tietze 1965, pp. 7-9). 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, ..., p, the number

 N=2·3·5...p+1,
(1)

known as the ith Euclid number when p=p_i is the ith prime, is either a new prime or the product of primes. If N is a prime, then it must be greater than the previous primes, since one plus the product of primes must be greater than each prime composing the product. Now, if N is a product of primes, then at least one of the primes must be greater than p. This can be shown as follows.

If N is composite and has no prime factors greater than p, then one of its factors (say F) must be one of the primes in the sequence, 2, 3, 5, ..., p. It therefore divides the product 2·3·5...p. However, since it is a factor of N, it also divides N. But a number which divides two numbers a and b<a also divides their difference a-b, so F must also divide

 N-(2·3·5...p)=(2·3·5...p+1)-(2·3·5...p)=1.
(2)

However, in order to divide 1, F must be 1, which is contrary to the assumption that it is a prime in the sequence 2, 3, 5, .... It therefore follows that if N is composite, it has at least one factor greater than p. Since N is either a prime greater than p or contains a prime factor greater than p, a prime larger than the largest in the finite sequence can always be found, so there are an infinite number of primes. Hardy (1992) remarks that this proof is "as fresh and significant as when it was discovered" so that "two thousand years have not written a wrinkle" on it.

A similar argument shows that p!+/-1 must be either prime or be divisible by a prime >p. Kummer used a variation of this proof, which is also a proof by contradiction. It assumes that there exist only a finite number of primes p_1, p_2, ..., p_r. Now define N=p_1p_2...p_r and consider N-1. It must be a product of primes, so it has a prime divisor p_i in common with N. Therefore, p_i|N-(N-1)=1 which is nonsense, so we have proved the initial assumption is wrong by contradiction.

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

 n=k!=product_(i=1)^ki,
(3)

where k! is a factorial. Then the k-1 consecutive numbers n+2, n+3, ..., n+k are composite, since

n+2=(1·2...k)+2
(4)
=2(1·3·4...k+1)
(5)
n+3=(1·2...k)+3
(6)
=3(1·2·4·5...k+1)
(7)
n+k=(1·2...k)+k
(8)
=k[1·2...(k-1)+1].
(9)

Guy (1981, 1988) points out that while p_1p_2...p_n+1 is not necessarily prime, letting q be the next prime after p_1p_2...p_n+1, the number q-p_1p_2...p_n is conjectured always to be a prime known as a Fortunate prime, though this has not been proven.


See also

Divide, Euclid Number, Fortunate Prime, Prime Number, Proof by Contradiction

Explore with Wolfram|Alpha

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.Derbyshire, J. Prime Obsession: Bernhard Riemann and the Greatest Unsolved Problem in Mathematics. New York: Penguin, p. 34, 2004.Dunham, W. "Great Theorem: The Infinitude of Primes." Journey through Genius: The Great Theorems of Mathematics. New York: Wiley, pp. 73-75, 1990.Flannery, S. and Flannery, D. In Code: A Mathematical Journey. London: Profile Books, pp. 42-43, 2000.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.Hardy, G. H. and Wright, E. M. An Introduction to the Theory of Numbers, 5th ed. Oxford, England: Clarendon Press, 1979.Havil, J. Gamma: Exploring Euler's Constant. Princeton, NJ: Princeton University Press, p. 28, 2003.Ribenboim, P. The New Book of Prime Number Records. New York: Springer-Verlag, pp. 3-12, 1989.Tietze, H. Famous Problems of Mathematics: Solved and Unsolved Mathematics Problems from Antiquity to Modern Times. New York: Graylock Press, pp. 7-9, 1965.

Referenced on Wolfram|Alpha

Euclid's Theorems

Cite this as:

Weisstein, Eric W. "Euclid's Theorems." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/EuclidsTheorems.html

Subject classifications