Difference between revisions of "Euclid's proof of the infinitude of primes"
Enderramsby (talk | contribs) (→See Also) |
|||
(5 intermediate revisions by 5 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. | |
+ | |||
+ | ==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== | ||
+ | * [[Proof by contradiction]] | ||
+ | * [[Number theory]] | ||
+ | * [[Prime]] | ||
+ | * [[Euclid]] | ||
+ | |||
+ | [[Category:Proofs]] | ||
+ | [[Category:Number theory]] | ||
+ | |||
+ | {{stub}} |
Latest revision as of 11:57, 14 August 2022
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, . Let
. Since
leaves a remainder of 1 when divided by any of our prime numbers
, 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,
must have a prime factor (possibly itself) that is not among our set of primes,
. This means that
does not contain all prime numbers, which contradicts our original assumption. Therefore, there must be infinitely many primes.
See Also
This article is a stub. Help us out by expanding it.