Math
From Tractatus
My favorite proof comes from Algebra. I was introduced to it by A First Course in Abstract Algebra by Joseph Rotman. He attributes the proof to J.H. McKay. Rotman's book is worth every dollar of its price. It is clear, easy to read, well laid out, and in 256 short pages it takes you from the basics, all the way to proving, with ease, the insolvability of the quintic. It is ture that it does not have the rigor of Hungerford's Algebra, but it is to be preferred.
The proof itself is a simultaneous proof of two of the most important Theorems in Algebra: Cauchy's Theorem, and Fermat's Theorem. Don't confuse Fermat's Theorem, with the Fermat's Last Theorem which was proven a few years ago by Andrew Wiles, and the subject of a book by Simon Singh. Fermat's Last Theorem, also known as 'The last thing Fermat made up, before he died so no one could call him on it.' Fermat's Theorem is something which he actually proved, and it is much more useful, in the sense that is a necessary precursor to modern Cryptography. If you don't grok Fermat's Theorem, you will never grok public key Cryptography. In order to avoid confusion, many people refer to Fermat's Theorem as Fermat's Little Theorem. I will not trivialize it this way.
I am prefacing the proof with a little background information. If you are a lay reader not interested in Mathematics, then I highly encourage you to skip the background, and just read the proof. I have struggled to make the essential parts of it clear, even with no understanding of the underlying concepts. I include the backgroung for those interested in mathematics, who need a refresher. If you are well grounded in Algebra, then you may wish to skip it, because I don't want you to think I consider the informal explanation a proof. You should go right to the section Formal Proof
Contents |
Background
Motivation
The lay reader may have started to realize that when I use the word Algebra I am not referring to problems like "Solve for x where x + 2 = 3." Rather I am referring to the branch of mathematics which deals with the nature of aritmetic. What does it mean to add, to multiply? What if addition gave different answers? What if 2 = 0? Or 2 + 2 = 5 You might think that speculating about things like this would be silly. It isn't. First off, these seemingly impossible situations actually do come up all the time. Further, a standard tool in the Mathematicians bag of tricks is to start with something in one universe. Show how to translate the thing to another universe, in that universe do something 'impossible,' and then translate back. Often, this gives something for free.
(add more background here, I don't want to do too much)
Warm Up
As a warmup for the non-mathematician, Let's take a moment to prove an interesting fact to ourselves. We will use this fact later. If you are mathematically inclined, then this fact will be pretty obvious.
(Add a simple argument about Lagrange's theorem here)
The Proof
Given: a group G, and a prime p.
Let's start by writing down a list of equations
where 
. Note that two of the terms could be equal, I am not saynig that g_1 is not equal to g_2. The first equation in the list is probably 0 + 0 + \dots + 0 = 0
How many equations exist with this form? Well, we can pick g_1, \dots, g_{n-1} arbitrarily, and then there is only one possibility for g_n, negative g_1 + \dots + g_{n-1}. Since there are |G|^{n-1} ways that we can pick the little g's, where |G| means 'the number of elements in G,' there must be exactly |G|^{n-1} equations. Call this list of equations X_n.
Looking at this list, there are some equations which are very similar. For instance:
g_1 + g_2 + \dots + g_{n-1} + g_n = 0
and
g_2 + g_3 + \dots + g_{n-1} + g_n + g_1 = 0
or even
g_i + g_{i+1} + \dots + g_{n-1} + g_n + g_1 + \dots + g_{i-1} = 0
Let's call equations like this 'rotations'. Note that rotations naturally group together, given one equation, you can generate all the possible rotations of it. How many of them are there?
Let's rewrite the list of equations so that all the rotations are next to each other. Our plan is to count the size of X again, but this time, do it in terms of the sets of rotations.
Our first naive way to count would be to say, "Well, each group of rotations has size p, so |X| must be a multiple of p." That would be an interesting result, but wrong. Some of the sets of rotations don't have size p. For example
0 + 0 + ... + 0 + 0 = 0
only ever rotates to itself. It is all alone in the list. So we have to check when
g_1 + g_2 + \dots + g_{n-1} + g_n = 0
and
g_i + g_{i+1} + \dots + g_{n-1} + g_n + g_1 + \dots + g_{i-1} = 0
Are actually the same equation. Suppose that they are. Well, in that case g_1 =g_i = g_{i+i-1} = g_{i+i-1+i-1} ....
>>> I need to add some text here about Lagrange's Theorem, and find a casual way to make the argument.
By Lagrange's Theorem, the sets of rotations are either size 1, for elements of order p, and 0, or size p for everything else. Let e_p be the number of elements of order p in G.
That means. |X| = |G|^{p-1} = (|G| - e_p)p + e_p + 1
Consider a group of size two. The equation says:
2^{p-1} = 1 (mod p)
Because there are no elements of order p for p > 2.
We have just proven Fermat's Theorem.
Now, suppose that |G| = p, then we have
p^{p-1} = (p - e_p)p + (e_p + 1)
Since the left side of the equation is divisible by p, the right side must also be divisible by p. Since everything else in sight is a multiple of p, e_p + 1 must be a multiple of p. That means e_p must be non-zero, so an element of order p must exist( in fact, at least p-1 such elements must exist.
We have just proven Cauchy's Theorem.
Fermat's Theorem
Discussion
Notice that we can change our proof to show that:
What this basically says is that if you raise a value to a certain power, then it will be equivalent to 1 modulo p. No matter what value you start with. The reson that this matter is that it the first step on a path where you dicover that exponents do really funny things in modular arithmetic. One of the funniest things they let you do is really good Cryptography.
Cauchy's Theorem
For a group G.
