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

m
(Move to Euclid's Theorem)
(Tag: New redirect)
 
(5 intermediate revisions by 2 users not shown)
Line 1: Line 1:
'''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.
+
#REDIRECT [[Euclid's Theorem]]
 
 
==Proof==
 
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==
 
* [[Number theory]]
 
* [[Prime]]
 
* [[Euclid]]
 
 
 
[[Category:Proofs]]
 
[[Category:Number theory]]
 
 
 
{{stub}}
 

Latest revision as of 17:56, 21 February 2025

Redirect to: