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<q, contradicting the “biggest-ness” of p.

Advertisements

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s