What are the $p$ such that $p, p+2, p+4$ are all primes?
Necessarily $p, p+2$ or $p+4$ is a multiple of 3, hence equal to 3. Since $p \geqslant 2$, we have $p=3$. Conversely, $p=3$ is a solution.

## Lemma 3.

Let $n \geqslant 2$, and let $p$ be the smallest divisor of $n$ that is greater than or equal to 2. Then $p$ is prime.

Proof. Let $d$ be a positive divisor of $p$. If $d \neq 1$, then $d \geqslant 2$ (since $d$ is not zero, as $d$ divides $n$, and $n$ is not zero). Since $d$ divides $p$ and $p$ is not zero, we have $d \leqslant p$. But on the other hand, $d$ divides $p$, so $d$ divides $n$. The choice of $p$ ensures that $d \geqslant p$, hence $d=p$. Therefore, $p$ is prime.

In particular, this implies that every integer greater than or equal to 2 has a prime divisor!

## Theorem 4.

There are infinitely many prime numbers.

Proof. Suppose, for the sake of contradiction, that there are only finitely many prime numbers, say $p_{1}, \ldots, p_{n}$, and let $N=p_{1} \ldots p_{n}+1$. Let $p$ be a prime divisor of $N$. It is clear that $p$ cannot be any of $p_{1}, \ldots, p_{n}$, which provides the desired contradiction.

There is (at least to date) no formula to find prime numbers. In general, to show that a number is prime, one simply checks that it has no other prime divisor than itself...

## Example 5.

Is 127 prime? It is not divisible by 2, 3, 5, or 11. It is easy to verify that it is not divisible by 7 either. In fact, there is no need to perform further checks! Indeed, if 127 were not prime, it would have a divisor $a$ strictly between 1 and 127. We could write $127=a \cdot b$, with $1<a, b<127$. But then $a \leqslant \sqrt{127}$ or $b \leqslant \sqrt{127}$. By symmetry, we can assume $a \leqslant \sqrt{127}$. Then $a$ has a prime divisor $p$, which is in turn less than or equal to $\sqrt{127}$. Therefore, it is sufficient to check that no prime number less than or equal to $\sqrt{127}$ divides 127, and since $\sqrt{127}<12$, it is enough to test all prime numbers less than or equal to 11.