Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Euclid's proof of the infinitude of primes"

(creation)
(reworded proof.)
Line 1: Line 1:
−
'''Euclid's proof of the infinitude of primes''' is a [[proof]] by [[Euclid]] that the number of [[prime number]]s is [[infinite]].
+
'''Euclid's proof of the infinitude of primes''' is a classic and well-known [[proof]] by the Greek mathematician [[Euclid]] that there are infinitely many [[prime number]]s.
  
 
==Proof==
 
==Proof==
−
We proceed by [[proof by contradiction | contradiction]].  Suppose there are only [[finite]]ly many [[prime number]]s; let's call them <math>p_1, p_2, p_3, \ldots, p_n</math>. Let <math>x=p_1\cdot p_2\cdot p_3 \cdots p_n + 1</math>.  When <math>x</math> is divided by any of our primes <math>p_1, p_2, p_3, \ldots, p_n</math> it leaves a [[remainder]] of 1, so none of these primes divide <math>x</math>.  Since every [[positive integer]] has at least one prime factor, <math>x</math> has some prime factor (possibly itself) not in the set <math>\{ p_1,p_2,p_3,\ldots,p_n\}</math>.  Thus <math>\{ p_1,p_2,p_3,\ldots, p_n\}</math> does not contain all prime numbers. Contradiction!  Our original assumption must have been false, so there are in fact infinitely many primes.
+
We proceed by [[proof by contradiction | contradiction]].  Suppose there are in fact only finitely many prime numbers, <math>p_1, p_2, p_3, \ldots, p_n</math>. Let <math>N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1</math>.  Since <math>N</math> leaves a remainder of 1 when divided by any of our prime numbers <math>p_k</math>, it is not divisible by any of them. However, the [[Fundamental Theorem of Arithmetic]] states that all positive integers have a unique prime factorization. Therefore, <math>N</math> must have a prime factor (possibly itself) that is ''not'' among our set of primes, <math>\{p_1, p_2, p_3, \ldots, p_n\}</math>.  This means that <math>\{p_1, p_2, p_3, \ldots, p_n \}</math> does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.
  
 
==See Also==
 
==See Also==
−
*[[Number theory]]
+
* [[Number theory]]
−
*[[Euclid]]
+
* [[Prime]]
 +
* [[Euclid]]
  
 
[[Category:Proofs]]
 
[[Category:Proofs]]
 
[[Category:Number theory]]
 
[[Category:Number theory]]

Revision as of 19:47, 18 March 2008

Euclid's proof of the infinitude of primes is a classic and well-known proof by the Greek mathematician Euclid that there are infinitely many prime numbers.

Proof

We proceed by contradiction. Suppose there are in fact only finitely many prime numbers, $p_1, p_2, p_3, \ldots, p_n$. Let $N = p_1 \cdot p_2 \cdot p_3 \cdots p_n + 1$. Since $N$ leaves a remainder of 1 when divided by any of our prime numbers $p_k$, it is not divisible by any of them. However, the Fundamental Theorem of Arithmetic states that all positive integers have a unique prime factorization. Therefore, $N$ must have a prime factor (possibly itself) that is not among our set of primes, $\{p_1, p_2, p_3, \ldots, p_n\}$. This means that $\{p_1, p_2, p_3, \ldots, p_n \}$ does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.

See Also

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Euclid%27s_proof_of_the_infinitude_of_primes&oldid=24137"