Question

(Euclid) Prove that there are infinitely many primes.

Short answer

It is proved that there are infinitely many primes.

Step-by-step solution

The Fundamental Theorem of Arithmetic

Theorem 1.7 states that any integer n except $0,\pm 1$ would be theproduct of primes. Theprime factorization seems to be unique in the following way. When $n=p_1,p_2,...,p_r$ and $n=q_1,q_2,...,q_s$ where each $p_i,q_j$ prime, then $r=s$ (i.e., the number of factors will be the same).Then, it is rearranged and renamed the $q\text{'}s$ as shown below:

role="math" localid="1646247136401" $p_1=\pm q_1{p}_2=\pm q_2{p}_3=\pm q_3,...,p_r=\pm q_r$

Show that there are infinitely many primes

Assume that there exist only finitely many primes, i.e., $p_1,p_2,...,p_k$ denote every prime. Consider that role="math" localid="1646247664950" $n=p_1,p_2,...,p_{k+1}$.

According to the fundamental theorem of arithmetic, all numbers could be expressed as the product of the prime number. Namely, all numbers would be prime or contain prime factors.

It is observed that n is not divided by any of the primes $p_1,p_2,...,p_k$ because it does not divide the remainder 1.

As a result, either $n$ should prime or there should exist prime $p_{k+1}$ in which $p_{k+1}|n$.

This is contrary to the statement, which states that $p_1,p_2,...,p_k$ are all primes.

Hence, it is proved that there are infinitely many primes.