## Infinitude of primes via Lagrange’s theorem and Mersenne numbers.

I thought i’d start easy for my first non-introductory post.

We all know Euclid’s proof on the infinitude of prime numbers.

Euclid’s (famous) Proof:

Suppose there are finitely many primes $p_1, p_2, \mathellipsis, p_n$ and using these, we may form the number:

$N = (p_1p_2\mathellipsis p_n) + 1$.

This is a number bigger than $1$ (since all primes are bigger than $1$ and there certainly exists at least one prime number). Thus $N$ has a prime divisor $p$.

Now $p$ must be one of $p_1, p_2, \mathellipsis, p_n$ since these are all of the primes (by assumption).

So $p$ also divides $p_1 p_2\mathellipsis p_n$.

But then $p$ must divide $1$, giving a contradiction (since no prime number divides $1$).

____

There are millions of proofs of this result but I stumbled on an equally nice one in “Proofs from THE BOOK”. It turns out that there is a more algebraic proof involving Lagrange’s theorem.

Lagrange’s theorem:
Given any finite group $G$ and any subgroup $H$ we must have that $|H|$ divides $|G|$. Also, the order of an element of $G$ must divide $|G|$.

Proof:
Choose an element $g$ of $G$ and consider the map from $H$ to $gH$ which sends $h$ in $H$ to $gh$. This map can be shown to be a bijection, meaning that all cosets of $H$ in $G$ have the same number of elements (this number being $|H|$). Also, it is easy to show that any two cosets of $H$ in $G$ are either disjoint or equal.

So $G$ is partitioned into disjoint cosets, each having $|H|$ elements. Thus $|H|$ divides $|G|$ (the number of elements of $G$ can be found by adding up so many copies of $|H|$ under the partition). This proves the first claim.

To prove the second claim, take $H$ to be the cyclic subgroup of $G$ generated by some element $x$ of $G$. Then $H = \{e,x,x^2,...,x^{n-1}\}$ where $n$ is the order of $x$ in $G$.

This subgroup has $n$ elements and by the first claim we have that $|H|$ divides $|G|$. This proves the second claim.

____

We are now ready to see a less known proof of the infinitude of primes.

Alternative proof of the infinitude of primes:

Again, suppose that there are only finitely many primes and let $p$ be the largest.

We prove that the Mersenne number $2^p - 1$ has a prime divisor bigger than $p$, giving a contradiction (since we are assuming that there is no prime bigger than $p$). Actually, we will see that all prime divisors of $2^p - 1$ are bigger than $p$ but this isn’t really the point.

Let $q$ be a prime divisor of $2^p - 1$. Then $2^p\equiv$ 1 mod $q$, meaning that $2 \bmod q$ has order $p$ in the multiplicative group $(\mathbb{Z}/q\mathbb{Z})^{\times}$.

This group has order $q-1$, since $q$ is prime and so by Lagrange’s theorem we must have that $p|(q-1)$ and so $p < q$, which is what we wanted.

____