Difference between revisions of "Euclid's proof of the infinitude of primes"
Enderramsby (talk | contribs) (→See Also) |
m (fixed) |
||
(One intermediate revision by the same user not shown) | |||
Line 12: | Line 12: | ||
[[Category:Proofs]] | [[Category:Proofs]] | ||
[[Category:Number theory]] | [[Category:Number theory]] | ||
− | + | [[category:Mathematics]] | |
{{stub}} | {{stub}} |
Latest revision as of 10:45, 28 September 2024
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.