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 and using these, we may form the number:

.

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

Now must be one of since these are all of the primes (by assumption).

So also divides .

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

____

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 and any subgroup we must have that divides . Also, the order of an element of must divide .

*Proof:*

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

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

To prove the second claim, take to be the cyclic subgroup of generated by some element of . Then where is the order of in .

This subgroup has elements and by the first claim we have that divides . 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 be the largest.

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

Let be a prime divisor of . Then 1 mod , meaning that has order in the multiplicative group .

This group has order , since is prime and so by Lagrange’s theorem we must have that and so , which is what we wanted.

____

### Like this:

Like Loading...

*Related*

This entry was posted on April 17, 2011 at 9:44 pm and is filed under Elementary Number Theory. You can follow any responses to this entry through the RSS 2.0 feed.
You can leave a response, or trackback from your own site.

## Leave a Reply