Number Theory

http://2tor4u.blogspot.com/2010/10/prime-numbers.html

Theorem: There are infinitely many primes.

            Background knowledge:

^·          The fundamental theorem of arithmetic¹ states that every positive integer (except for 1) can be uniquely factored as a product of primes

We will now proceed by mirroring Euclid’s² proof.

Proof: Suppose that there were only finitely many primes. Then we can say there are n prime numbers, where n is some natural number. Furthermore, we can list out all of the primes from smallest to largest as follows: p₁=2, p₂=3, p₃=5, … , p_n= the n^th prime number. Let

ψ = p₁p₂p₃…p_n + 1. Then ψ - p₁p₂p₃…p_n = 1. Now, the fundamental Theorem of arithmetic states that since ψ is a positive integer greater than 1, ψ can be written as a product of primes. That is, there is some prime q which divides ψ.

Suppose that q was one of the primes p₁, p₂, p₃, …, p_n. Then q would divide the product p₁p₂p₃…p_n. In particular, since q divides ψ and q divides p₁p₂p₃…p_n, we get that q divides

ψ - p₁p₂p₃…p_n also. Recall that ψ - p₁p₂p₃…p_n = 1. Thus, q divides 1, which implies that q=1. This contradicts with our former establishment that q is prime.

Thus it must be the case that q is a prime different from each of the primes p₁, p₂, p₃, …, p_n. In particular, we arrive at the conclusion that p₁, p₂, p₃, …, p_n is not a complete list of all the primes, contradicting with our original assumption. Thus, there cannot be finitely many primes.

1. The following link provides a proof of the fundamental theorem of arithmetic http://planetmath.org/ProofOfFundamentalTheoremOfArithmetic.html
2. To learn more about Euclid and his proof visit http://mekurt.blogspot.com/2011/04/infinitude-of-prime-numbers-euclid.html