Tool By Zeal Point

1. Assume the opposite : Suppose there are only finitely many prime numbers: $P_{1}, P_{2}, P_{3}, \dots, P_{r}$

2. Build a new number : Multiply all the primes and add 1: $N = P_{1} \times P_{2} \times P_{3} \times \dots \times P_{r} + 1$

3. Check divisibility : When $N$ is divided by any prime in our list, the remainder is always 1. Ex: $N \div$ P₁ $\to remainder 1$

So, none of the listed primes divides $N$ .

4. What can N be ?

There are two possibilities:

$N$ itself is prime, or

$N$ is composite, but then it must have a prime factor.

That prime factor cannot be any prime from our original list.

5. Contradiction : We assumed that our list contained all prime numbers. But we have found a prime that is not in the list. Therefore, our assumption is wrong.

6. Ex : Take the first three primes: $2, 3, 5.$ Construct: $N = 2 \times 3 \times 5 + 1 = 31.$ And 31 is a prime number.

7. Conclusion : $There are infinitely many prime numbers.$

Note: Multiply all known primes + 1

$P^{1} P^{2} P^{3} \dots P^{r} + 1$

It will not be divisible by any of the primes in your list, proving that the list can never be complete.

=================================

Q. Which of the following statements correctly explains Euclid’s proof that there are infinitely many prime numbers ?

A. The sum of all prime numbers is always prime.
B. The product of all listed primes plus 1 gives a number not divisible by any listed prime.
C. Every number greater than 1 is prime.
D. The product of two primes is always prime.

Solution

Suppose the complete list of primes is: $2, 3, 5, 7$

Construct:

$N = (2 \times 3 \times 5 \times 7) + 1 = 211$

Now 211 is not divisible by 2, 3, 5, or 7.

Therefore, there must be a prime number not included in our original list.

Hence, the list of primes can never be complete.

Ans: B

Trick : $All listed primes \times each other + 1$

This proves that there are infinitely many prime numbers.

Why Prime Numbers Never End : Euclid’s Proof — Infinitely Many Prime Numbers