Question

Prove that there are infinite primes by using proof by contradiction.

Answer 1

Let us suppose that there is a finite number, n, of primes.

(As part of a proof by contradiction, we must be very careful and assume the opposite of the statement that we are trying to prove.  Further, we should be super careful that we don't assume anything else!  So, whatever follows from this point on, should just follow from the statement above, with no further assumptions.)

Let 2 = p1 < p2 < ... < pn

Now, we inspect the integer N = 1 + p1 · p2 · ... · pn.

Since N > pn, and pn is the largest prime number, N is not prime by our assumption.

However, if we divide N by any of the prime numbers, we get 1 as the remainder.  (For example, N % p_i = 1, for any 1 <= i <= n.)

Therefore N is not a multiple of any prime number, and therefore it must be a prime number itself.

This is a contradiction that the p_n was the largest prime number.

-> <-

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

Answer 2

For Proof of Contradiction, we are going to start with the following assumption:

There is a finite number of prime numbers.

Let's call these numbers p₁, p₂, p₃ ... p_n.

Next, we are going to create a new number, N, by multiplying all of our prime numbers, and then adding 1. This means:

N = p₁ x p₂ x p₃ x ... x p_n + 1

Now, let's break this down. N is now a number that is NOT divisible by ANY of the numbers in our list of prime numbers, because we added 1 (dividing N by any of the numbers in our list of "p" prime numbers results in a remainder of 1). Now, the point of this fact isn't that we've created a new prime number (it could very well be a composite number), but rather that BECAUSE we can't divide this new number by any of our prime numbers from our list, that this new number, N, is either prime, itself, OR it is a composite number.

Now, because of the Unique Prime Factorization Theorem, we know that:

1. Existence: Every integer greater than 1 either is a prime number itself or can be factored into prime numbers.

2. Uniqueness: This factorization is unique, up to the order of the factors. That means if you factorize a number into primes in two different ways, the sets of primes you get will be the same, though they might appear in a different order.

Because of this theorem, we know that N does have prime factors, which means that either N is prime, or it has prime factors that are NOT in our current list (because by adding 1, we already ensured that none of our current numbers can be used to divide N evenly). This, then, proves that our finite list of prime numbers is NOT accurate, thereby proving, by contradiction, that there are infinite prime numbers.

Answer 3

Start with a counter-assumption: Let's imagine the scenario where the set of prime numbers is limited. Denote these finite primes as P1, P2, P3,...Pn

Create a novel number: Now, form a new number, N= (P1*P2*P3*...Pn )+ 1 Notice that N is greater than any prime in our assumed finite set.

Examine N's prime factors: Every number greater than 1 is either a prime itself or can be decomposed into a unique set of prime factors (Fundamental Theorem of Arithmetic).

Unravel the contradiction:

If N itself is a prime, it's not in our original list, which contradicts our assumption of having listed all primes.

If N is composite, its prime factors cannot be any of P1, P2 ,...Pn because dividing 

N by any of these primes leaves a remainder of 1. 

Thus, N must be divisible by some prime not in our original list, contradicting our assumption again.

Inference: The initial assumption of a finite number of primes leads us to a contradiction.

Therefore, the only logical conclusion is that the number of primes is infinite.