Changes: Euclid's Proof

Revision as of 08:23, 26 January 2017

Euclid's proof proved that there was an everlasting set of prime numbers. He was the first person to prove this. It is a proof by contradiction — it assumes the opposite of what it is trying to prove and then shows that this is not possible.

The Proof

The proof states the following:

If there is a limited set of primes, then all these primes can be multiplied together to attain an integer result.

However, if you add one to this number, the resulting number will be one more than a multiple of all the primes in the set and will therefore not be divisible by any other prime factors. Therefore, this number is a prime outside of the original set of primes.

This proves that you cannot have an finite set of primes and that there are infinitely many primes.

Important Pages
Divisibility and Sieves	Divisibility Rules (by rule) \| (by list) \| Sieve of Eratosthenes
Proofs and Theorems	Euclid's Proof \| Goldbach's Conjecture \| Prime Number Theorem \| Integer
Prime Numbers	Timeline of the History of Prime Numbers \| The Largest Known Prime Number
Help	Getting Started
Different Bases	What Digit a Prime Number in a Base Can End In

@@ Line 1: / Line 1: @@
-'''Euclid's proof''' proved that there was an everlasting set of prime numbers. He was the first person to prove this, even though many other mathematicians proved it another way. It is a proof by contradiction- it states the opposite and shows that it is not possible.
+'''Euclid's proof''' proved that there was an everlasting set of prime numbers. He was the first person to prove this. It is a proof by contradiction — it assumes the opposite of what it is trying to prove and then shows that this is not possible.
 ==The Proof==
 The proof states the following:
+If there is a limited set of primes, then all these primes can be multiplied together to attain an integer result. <br>
-If there is a limited set of primes, then you can get all the primes and multiply them together. However, if you add one to the number, it will not have any prime factors because all the prime factors have been in the previous number and if you add one to a number, all the prime factors in the previous number do not go into it. Thus, the new number is a prime.
+However, if you add one to this number, the resulting number will be one more than a multiple of all the primes in the set and will therefore not be divisible by any other prime factors. Therefore, this number is a prime outside of the original set of primes. <br>
+This proves that you cannot have an finite set of primes and that there are infinitely many primes.
 {{Important Pages}}