jsCoq – Infinitude of Primes

Welcome to the jsCoq Interactive Online System!

## Infinitude of Primes

As a relatively advanced showcase, we display a proof of the
infinitude of primes in Coq.

The proof relies on the [Mathematical Components](https://math-comp.github.io) library from the [MSR Inria team](http://ssr.msr-inria.inria.fr/) team led by Georges Gonthier, so our first step will be to load it:

```coq
From Coq Require Import ssreflect ssrfun ssrbool.
From mathcomp Require Import eqtype ssrnat div prime.
```

### Ready to do Proofs!

Once the basic environment has been set up, we can proceed to the proof:

```coq
(* A nice proof of the infinitude of primes, by Georges Gonthier *)
Lemma prime_above m : {p | m < p & prime p}.
Proof.
```

The lemma states that for any number `m` there is a prime number larger than `m`.

Coq is a _constructive system_, which among other things implies that to show the existence of an object, we need to actually provide an algorithm that will construct it.

In this case, we need to find a prime number `p` that is greater than `m`. What would be a suitable `p`?

Choosing `p` to be the first prime divisor of `m! + 1` works. As we will shortly see, properties of divisibility will imply that `p` must be greater than `m`.

```coq
have /pdivP[p pr_p p_dv_m1]: 1 < m`! + 1 by rewrite addn1 ltnS fact_gt0.
```

Our first step is thus to use the library-provided lemma `pdivP`, which states that every number is divided by a prime. Thus, we obtain a number `p` and the corresponding hypotheses `pr_p : prime p` and `p_dv_m1`, "p divides m! + 1".

The ssreflect tactic `have` provides a convenient way to instantiate this lemma and discard the side proof obligation `1 < m! + 1`.

```coq
exists p => //; rewrite ltnNge; apply: contraL p_dv_m1 => p_le_m.
```

It remains to prove that `p` is greater than `m`. We reason by contraposition with the divisibility hypothesis, which gives us the goal "if `p ≤ m` then `p` is not a prime divisor of  `m! + 1`".

```coq
by rewrite dvdn_addr ?dvdn_fact ?prime_gt0 // gtnNdvd ?prime_gt1.
Qed.
```

The goal follows from basic properties of divisibility, plus from the fact that if `p ≤ m`, then `p` divides `m!`, so that for `p` to divide `m! + 1` it must also divide 1, in contradiction to `p` being prime.

<i>¡Salut!</i>