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|.

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: