PROVE There are an infinitely many primes Please show all st

PROVE: There are an infinitely many primes.

Please show all steps, so that I may increase my understanding of the solution process. Thank you.

Lemma :Every integer N > 1 has a prime factorization.

Proof by contradiction: Assume that there is an integer that does not have a prime factorization.

Then, let N be the smallest such integer. If N were prime, it would have an

obvious prime factorization (N = N). Therefore, N is not prime. This means N must be

divisible by a positive integer other than itself or 1; call this integer r. Then, 1 < r < N

and N = r · s where s is also an integer. Notice that since 1 < r < N, we also must have

1 < s < N. Since N is the smallest number bigger than 1 without a prime factorization, both

r and s must have prime factorizations.

Therefore, there exist prime numbers p1, p2, ..., pn

and q1, q2, ..., qm such that r = p1 · p2 · ... · pn and s = q1 · q2 · ... · qm. Then,

N = p1 · p2 · ... · pn · q1 · q2 · ... · qm.

We have written N as the product of prime numbers. This contradicts the assumption that N does not have a prime factorization.

Theorem: There are infinitely many prime numbers.

Proof by contradiction: Assume there are finitely many prime numbers. Then, we can

say that there are n prime numbers, and we can write them down, in order:

Let 2 = p1 <p2 < ... < pn be a list of all the prime numbers. The key trick in the proof is to define the

integer

N = 1 + p1 · p2 · ... · p_n.

Since N > p_n, and p_n is the largest prime number, N is not prime. However, from the

lemma, N must have a prime factor. This means one of the primes in our list must divide

N; in other words, there exists an integer i with 1 i n such that pi divides N. Since pi

divides both N and the product of all the primes, it must also divide N p1 · p2 · ... · p_n = 1.

Since p_i 2, it is impossible that pi divides one, so we have a contradiction. Hence, our

assumption that there are finitely many prime numbers must have been false.