Feynman on Fermat's Last Theorem

Lemma: If x and y are coprime, then the gcd of x + y and (x^n + y^n)/(x + y) divides n.

Proof: Expand out the polynomial division (note that x + y does indeed divide x^n + y^n), and then divide the result by (x + y) again, observing a remainder of ny^(n - 1). Thus, the gcd of interest is the same as gcd(x + y, ny^(n - 1)). As y^(n - 1) is coprime to x + y (by coprimeness of x and y), this is furthermore the same as gcd(x + y, n), completing the proof.

Lemma: If x^p + y^p + z^p = 0, for odd prime p, with z indivisible by p, then (x + y) and (x^p + y^p)/(x + y) are coprime p-th powers.

Proof: As z is indivisible by p, so is -z^p = x^p + y^p, and thus so is its factor x + y. At this point, invoking the above lemma and the primeness of p, we find that (x + y) and (x^p + y^p)/(x + y) are coprime; as their product is a p-th power (-z^p), we conclude they are furthermore each p-th powers.

Sophie Germain's theorem: Suppose p is an odd prime, t is a prime, and the mod-t exponent-p case of FLT is true (in the sense that there is no solution to x^p + y^p + z^p = 0 (mod t) where x, y, and z are nonzero (mod t)), but the non-modular exponent-p (A) case of FLT fails (in the sense that there IS some solution to x^p + y^p + z^p = 0 in integers, all indivisible by p, which we can assume minimal so that x, y, and z are pairwise coprime). Then p is a p-th power modulo t.

Proof: Invoking the above lemma, we have some a, b, c such that a^p = y + z, b^p = x + z, and c^p = x + y.

Furthermore, since mod-t FLT is true, we have that (precisely) one of x, y, or z is zero mod t; WLOG, let this be x. But as 2x = b^p + c^p - a^p, we can invoke mod-t FLT again to conclude that one of b, c, or a is zero mod t. It cannot be b or c, as y and z, respectively, are nonzero mod t; thus, a is zero mod t. Thus, y + z = 0 (mod t), and therefore, by expanding out the polynomial (y^p + z^p)/(y + z), we see that its integer value is equal to py^(p - 1) modulo t. As x is zero mod t, we must have furthermore that (x^p + y^p)/(x + y) must be y^(p - 1) modulo t (note that this is nonzero modulo t). As the former and latter are both p-th powers by the above lemma, so is their ratio in modulo t arithmetic, which is p, completing the proof.

We can now rephrase Sophie Germain's theorem like so: To establish the (A) case of FLT for exponent p, it suffices to find some prime t such that BOTH the mod-t exponent-p case of FLT is true AND p is not a p-th power modulo t.

Such a t is the auxiliary prime for p discussed above. Note that the truth or falsehood of this condition on t relative to p is decidable by finite search.

A couple more comments: As a consequence of the multiplicative group modulo a prime being cyclic, we have that, for primes p and t, EVERY value is a p-th power modulo t unless t is 1 mod p. Thus, an auxiliary prime t for odd prime p must be of the form kp + 1. Furthermore, as t cannot be 2, it must be an odd prime, and therefore k must be even. Finally, we can also rule out k divisible by 3 by again invoking the cyclicity of the multiplicative group modulo t (were k divisible by 3, we would have some primitive cube root of 1 modulo t which was furthermore a p-th power; the three powers of this value would sum to zero and thus provide a counterexample to the mod-t exponent-p case of FLT). So when searching for auxiliary t to prime p, we are looking for primes of the form kp + 1 where k is an even value not divisible by 3; for all such k up through 16, Germain and Legendre managed to prove that conversely, whenever kp + 1 is prime, it satisfies all the conditions to be an auxiliary prime for p (with a slight exception for the two cases where p = 3 and k is 14 or 16), which provides auxiliary primes for each p I do not at the moment know if there are auxiliary primes for each p (and I suspect no one does?), nor how one goes about showing that, for various k, kp + 1 is automatically an auxiliary prime whenever prime (or whether this generalizes beyond k = 16). Oh well. More to learn, always.

Couldn't we argue in the same way that there are unlikely to be any solutions to the simpler equation x^n = z^n?

After all, taking p(x) = x^(1/n - 1)/n to be the probability that x is an n-th power, as Feynman does, and then integrating p(x^n) dx from x = x_0 to infinity to find the expected number of n-th powers of the form x^n for x > x_0, as Feynman does with p(x^n + y^n), we find for n > 2 that this comes out to 1/(x_0^(n - 2) * n * (n - 2)), which is quite small for sizable x_0 and n.

This yields, for example, that the expected number of solutions (and thus an upper-bound for the probability of the existence of any solutions) to the equation x^100 = z^100 with x > 10 should be 1 out of 98 googol. This is about as certain as certain gets that there are no solutions... and yet solutions are as ubiquitous as ubiquitous gets!

Actually, I'd say it is odd to find this sort of analysis to give great confidence about the results, not just because it ignores the possibility of structure, but also because it ignores the possibility of coincidence!

After all, there are some things which we probably want to call mathematical coincidences which heuristic argument would tell us are bogglingly unlikely and yet which nonetheless happen. For example, another probabilistic argument: Consider the basic arithmetic 2-ary operations +, -, * , and ^. There are 20!/(10! * 11!) full binary trees with 11 leaf nodes, 10^4 ways to label their internal nodes with one of these 4 operations, and 11! ways to assign the values 0 through 10 to those leaf nodes in some permutation. Thus, there are at most 20!/10! * 10^4 (overall, less than 10^16) values which can be generated using these operators and the natural numbers up through 10 once each (and this is an overestimate, ignoring the structure of, e.g., commutativity of + and * which causes less distinct values to be produced).

We would expect, therefore, that the closest we could get one of those values to line up with a particular unrelated mathematical constant, even focusing only on the fractional part, is no more than about 16 or so decimal digits. If there are thousands of mathematical constants we might compare it to, perhaps we'd get a match to about 20 digits on one.

And yet! And yet (1 + 9^(0 - 4^(6 * 7)))^(3^(2^(10 * 8 + 5))) lines up with e to 18457734525360901453873570 digits.

Now, what's happening here is that we have this other nice lining up of 9^(4^(6 * 7)) = 3^(2^(10 * 8 + 5)), which we can then plug into e ~= (1 + 1/n)^n with huge n. And this, in turn, is because 9 = 3^2 and 4 = 2^2 and 1 + 2 * 6 * 7 = 10 * 8 + 5. There's a bit of an explanation. And yet... surely if anything is a coincidence, this is?

So... I guess what I'm saying is, it is odd to use probabilistic arguments to rule out coincidence. The whole thing that makes a coincidence remarkable is that it is the sort of thing we would consider unlikely, and yet such things do occur, even in mathematics.