I am submitting this proof that there are infinitely many primes because it has come to my attention that this simple proof is one key to understanding a lot of math.
The original document is available here . It is possibly the easiest proof I have come across and because of that, I am able to understand it ;-). I’ve made some additions to simplify it even further.
Euler’s Proof that there are infinitely many primes
This is a proof by contradiction. That is, we shall prove that a STATEMENT is TRUE by assuming that the NEGATION of the STATEMENT is TRUE and reach a contradiction.
The STATEMENT to be proved is There are infinitely many positive primes.
Proof: Suppose there are NOT infinitely many primes — i.e., there are only finitely many positive primes, say K of them. List them all: p1, p2, p3, … , pK.
Now define some positive integer, m, by
m = ( p1 × p2 × p3 × … × pK ) + 1.
Since m > pj, for all j = 1, …, K, m is NOT a prime.
Thus, for some j, pj is a factor of m. Thus
m/pj = [( p1 × p2 × p3 × … × pK ) + 1 ] /pj is greater than, > 1
by multiplying & rearranging the equation we get
m/pj = ( p1 × p2 × p3 × … × pK )/pj + 1/pj
1/pj = m/pj – ( p1 × p2 × p3 × … × pK )/pj
now we know that m/pj > 1 and also that ( p1 × p2 × p3 × … × pK )/pj >1
thus 1/pj = [ m/pj – ( p1 × p2 × p3 × … × pK )/pj ] must also be > 1
But we know that 1/(pj) must satisfy 0 < 1/(pj) < 1.
This is a contradiction (to our above TRUE statement?).
thus the original statement must be wrong and There are infinitely many positive primes is TRUE.