# A proof via Lagrange’s theorem

Let’s assume for the sake of contradiction that there are finitely many primes. Let $p$ denote the biggest prime. Since $2^p-1>p$, it cannot be prime. It must be divisible by some other prime $q$. Another way to say this is that

$2^p\equiv1\pmod q$

This means that the order of $2$ in the multiplicative group $\mathbb Z/q\mathbb Z^\times$ must be a divisor of $p$. BUT $p$ IS PRIME! So $2$ must have order $p$. But then Lagrange’s theorem says that $p$ must be a divisor of the size of the group (which is $q-1$). In particular, $p, contradicting the “biggest-ness” of $p$.

Advertisements