# Infinity of primes

Q.1. Prove that there are infinitely many primes.

Solution.

Assume to the contrary a finite set of primes $\{p_1, p_2, ..., p_k\}$. $\ldots (1)$.

Consider $n = p_1 \times p_2 \times ... \times p_k + 1$.

Now, $p_i | n-1$ $\forall$ $1 \leq i \leq k$.

$\therefore n$ is not a multiple of any prime from the assumed finite set.

Hence, $n$ satisfies the definition of a prime number (i.e. one which is not a multiple of primes strictly smaller than itself.)$\ldots (2)$.

Q.2. Prove that there are infinitely many primes of the form $4n -1$.

Solution.

Claim. A number of the form $4n-1$ always has a prime factor of the form $4n-1$.

Proof of claim.

Consider any $k = 4n-1$.

If $k$ is prime, we are done.

Else, $k = k_1. k_2$, where $k_1 \equiv 1 (mod 4)$ and $k_2 \equiv 3 (mod 4)$. (verify!)

If $k_2$ is prime, we are done. Else, proceed as above.

The process concludes (if it does not find a greater prime of the form $4n-1$) at 3.

Hence, the claim is proved.

Assume there are only a finite number of primes of the form $4n-1$. Their product is either of the form $4n-1$ or $4n+1$. Add either $4$ or $2$, as the case may be, to obtain the next number, call it $p$, of the form $4n-1$.

Now, $p$ is not a multiple of any of the primes from the assumed finite set, contradicting the statement of the claim.

$-$