Exercise 910Number theory › Divisibility and gcdHigh schoolAdded 3 Nov 2026

Infinitely many primes

#Euclid#primes#proof by contradiction

Statement

Prove that there are infinitely many prime numbers.

Hint

Assume finitely many $p_1,\ldots,p_n$ and consider $N=p_1\cdots p_n+1$ .

Show solutionHide solution

Contradiction. Suppose finitely many primes $p_1,\ldots,p_n$ . Let $N=p_1\cdots p_n+1>1$ .

Prime divisor. $N$ has a prime divisor $p$ , which must be one of the $p_i$ .

Contradiction. $p\mid N$ and $p\mid p_1\cdots p_n$ , so $p\mid N-p_1\cdots p_n=1$ , impossible.

Conclusion. There are infinitely many primes.