That One Sentence Proof
So... I've seen this proof about 4 years ago and at that time I wasn't mathematically strong enough to understand what was going on with this proof. However, the proof is explained in a lecture of Number Theory I today so I'm writing what I understood here.
Lemma. Let be a finite set, and let be a function such that (we call such function "involution"). Then the parity of the number of fixed points of matches the parity of the cardinality of . In particular, if is odd then there exists a fixed point of .
Proof. Since is finite, we can give an algorithm that runs in finite time as the following. Let be the empty set initially. While pick and pair it with , then insert both and into . If they are the same, then is a fixed point, otherwise, a pair of distinct elements is counted (note that if then we're sure that also because if were to be in then either for some old , which must've already been in , a contradiction, or for some old in which case and were already paired and inserted to , a contradiction). We keep repeating this process until . Then this gives the following equation.
We modulo this equation by and see that the parity of must be equal to the parity of the number of fixed points.
In the particular case, if is odd then it is not possible that there is no fixed point.
One Sentence Proof with multiple sentences. (Zagier, idea from Heath-Brown, inspired by Liouville) The idea of that one sentence proof is to prove the existence of positive integers such that when is a prime. We consider the set , and consider the involution defined as
Since swaps and , if has an odd number of fixed point then there must be at least once that so that the swapping gives a fixed point. Once that happens, we see that there is a tuple of the form in , meaning that , that is, , which completes the proof. Now, by the lemma, it is enough to show that is odd, and this will show that has a fixed point.
To show that is odd, we begin by defining another involution as the following.
Now we need to check three things. First, is well-defined. This is not hard to see--the only undefined case is when and when . If then . This cannot be prime since it's a square! If then is divisible by , a contradiction.
Second, is an involution. Well this is the boring part... but you get it. We check three cases: and see that if then , so must go to the third case, which gives back . The second case is when and the third case is . They are tedious and similar to check.
Third, the only fixed point of is . Well the existence is simple: just plug in and check that it belongs to . The uniqueness can now be seen by the following. Suppose is another fixed point of , then . The only possible case for this is the case that (trying to equate with gives a problem that , and trying to equate with gives a problem that ). And therefore, . This means . Plugging back, we have , but is prime so must be . Now is constrained to be automatically.
With these three facts, we know that is an involution with exactly one fixed point, so is odd. Since is odd, must have a fixed point too, so there is such that and this completes the proof.