h2g2 The Hitchhiker's Guide to the Galaxy: Earth Edition

Entry: A day with Fermat in Toulouse [1640] - A33894002
Author: NotaFBene - U11273605

------- A day with Fermat in Toulouse -------
---- Or : On Fermat and the cubic roots of unity (mod p^k)
---- Just imagine . . . . picture Toulouse in southern France, 1640 . . .

Pierre de F. closes up at the end of a hectic day at the office, where he works as a magistrate at city hall. He gets a headache from those church prelates dominating everything, as if they had the truth in their pocket. After a sober but nourishing meal he retreats into his study and relaxes with his hobby: studying the old Greeks that were just recently translated into Latin, the international scientific language of the day. . . Especially the 'Arithmetica' of Diophantus is fascinating. He just discovered that Pythagoras' a^2+b^2=c^2 for integers, without common factor, occurs for primes c of form c=4n+1, starting with the well known 3^2+4^2=(4+1)^2, and 12^2+5^2=(3.4+1)^2. Would it be possible to generalize this to higher powers? Could the sum of two cubes be a cube, etc.?

From his young friend Blaise Pascal in Paris he just got a letter, (say) about the multiplicative structure (using factorial n!) of the coefficients in the expansion of (a+b)^n arranged in a triangle, skipping the a's and b's (clever trick to dispose of cluttering detail) although the coefficients are generated purely by addition, like a two-dimensional FiBonacci array, summing two neighbours repeatedly. - In fact, he just found that factorial structure himself, and he answered Blaise: . . is'nt it marvelous that truth is the same in Toulouse as in Paris ?! Quite different from theology, where truth depended on the last priest or cardinal you talked to.

No, that would never happen to his dear Mathematics, brought forward as the new science by Galileo (from Italy, in his 7-th year of house arrest, and two years before his death, for criticising the geo-centric, if not ego-centric, worldview pushed by the church), and by Descartes (who fled to Holland to save his skin, and escape the sad lot of Geordano Bruno at the stake in 1600; Galileo's students prepared an escape for him to Holland, but he felt too weak and old for the trip).
--- Authority had no place in Math: everybody with a clear and open mind, possibly helped by some calculation device, that he sometimes borrowed from Blaise who designed one (photo)* , could check it out and find new laws, and test for the truth himself.

Later, Leibniz in Germany, even made a multiplier from that device, which sold quite well. Of course it worked decimal, that beautiful code introduced from Arabia to Europe some 400 years ago by FiBonacci (the son of Bonacci). Leibniz did give a fleeting thought to binary code, which was just coming from China, where it was used for the philosophy of balance (yin/yang) and in a 3+3 bit code for the 8 x 8 = 64 hexagrams of the I-Ching (book of Changes) [ic-59] since 2000 BC. But the number wheels in the calculator would be too many for quick carry propagation which was the bottleneck for speed, as well as requiring too much of the crank turning the wheels.

So Pierre sharpened his feather to do some doodling by hand in his notebook, using p-ary code in order to find some structure, and possibly find solutions to
[1] : a^p+b^p = c^p . . prime p>2 (composite powers he quickly found inessential). From Pascals' triangle he saw that p divides each number in the p-th row, except the 1's at the two ends, proven easily by their newly discovered factorial coefficient nature. And slowly his Small Theorem (FST) took shape: a^p+b^p=(a+b)^p for the last p-ary digit, or as it is now known: n^p = n mod p for all n (using the modulo notation of Gauss who thus formulated arithmetic 'closure' for residues mod m, in 1801). This was exciting because the exponent distributes over addition, most unusual, and probably leading to inequality for integers, rather than equality. Could FST also be possible mod p^k for k>1, and some special a,b ? That would at least provide a solution to his root equation [1] mod p^k.

(begin NB)
To show what his Small Theorem FST is about : take any odd prime p (like 3, 5, 7, 11, 13, 17, 23, 29, 31 etc, having no proper divisor) and do residue arithmetic mod p. Normal number notation base p uses n = c.p + r, with carry 'c' and unique residue r from 0, to p-1. For residue arithmetic reset carry c=0. Fermat considered p-th powers g^p mod p, trying to find a generator g < p such that all its powers g = g^1, g^2, g^3, ..., g^(p-1) would be different. For instance mod p=7, then g=2 yields g^2= 4 and g^3= 8 = 1 mod 7 will not do since only half of the residues r < 7 are generated. But 3 does work : 3, 3^2 = 9 (base 10) = 1.7 + 2 = 2 mod 7, 3^3 = 3.3^2 = 3.2 = 6 = -1 mod 7. We can stop at -1 mod p , because the remaining h=(p-1)/2 powers mod p are the complement -g^i of those g^i (i=1..h) already found. Now 3 is called a primitive root of unity 1 (mod 7), since it generates all p-1 non-zero residues mod p. In short the generated p-1 cycle is: 3, 2, -1, -3, -2, 1 (mod 7). Now FST states that for every prime there is such primitive root g, generating a full p-1 cycle. It suffices (usually) to look for a primitive root among the divisors of p-1 (not proven), for instance p=191 has p-1 = 2.5.19 of which 19 is a primitive root (but not 2 or 5), its powers mod 191 generate a cycle of length 190.

Notice that in any such full cycle we have g^(p-1) = 1 mod p, the end of the cycle before it repeats itself, and g^h = -1 halfway. In fact it is easy to see that for any non-negative residue r < p holds r^(p-1) = 1 mod p, or : r^p = r (mod p). Even an extension to higher precisions mod p^k (k digit base p arithmetic) holds :
For odd prime p and any precision k > 1 there is a primitive root g < p that generates a cycle of length (p-1).p^{k-1} of residues mod p^k, denoted extension FST_k. The reason is that the powers of p+1 generate mod p^k a residue cycle of length p^{k-1}. For instance the cycle mod 7^2 is 6.7 = 42 long (D.Adam's magic number), generated for instance by 03, given in 7 columns of 6 residues with two 7-ary digits each:

+03 +43 +13 +53 -44 -04 -34
+12 +62 +42 +22 -65 -15 -35
+36 +46 +56 +66 -61 -51 -41
+44 +04 +34 -03 -43 -13 -53
+65 +15 +35 -12 -62 -42 -22
+61 +51 +41 -36 -46 -56 -66 = +01

Notice (mod 7^2) : -56 = 11 = p+1 = [3^{p-1}]^{p-1} , and (11)^7 = 01 : a length p cycle.
The cubic roots a^3=1 are 42 and 24 = (-42)-1, hence 42 + 24 + 01 = 00 (mod 7^2),
. . . and they are p-th powers : 42 = 3^14 = (3^2)^7, 42 = 3^28 = (3^4)^7 (mod 7^2).
(end NB)

And indeed, after some more trials, at p=7 there was something interesting mod 7^2 (using base 7 number code): 42+01=43 where a=42=a^7 and a+1=(a+1)^7, and another pair b, b+1 with similar properties: 24+01=25. Moreover b=1/a, and a+b= 66 = -1 (mod 7^2). So a^2+a+1=0, implying (a+1)^2=a and (a+1)^6=1 --> p-1 cycle mod p^2. He convinced himself that this holds for any prime p=6n+1, so 3 divides p-1, allowing a 3-cycle {a, a^2, a^3=1} in the p-1 cycle, to be called the 'core' of the cyclic group of roots of 1 mod p^k, for any k>=1 --- (now using the 'group' concepts of Abel and Galois, who factored Gauss' closure around 1830, into an uncoupled product resp. cascade- coupled product of cycles: solvable groups; the final chapter of what Nicolo Fontana, alias Tartaglia the stutterer from Brescia, started around 1540 when he found, just in time before a challenged competition, a formula for the roots of any cubic equation - subsequently stolen by Cardano and published in his "Ars Magna" in 1543, without reference to its source).

So this p-1 cycle would be his Medium Theorem (FMT) or 'Core theorem': n^p = n mod p^k (for odd prime p and any k>0, and p-1 special fixed-point core-residues coprime to p) as extension of FST to higher precisions k. It provides a solution to his k-digit Large Theorem (FLT/k): a^p+b^p= -1 mod p^k . . [2] for odd prime p, k>1 with {a,b} "in-core" where a^p=a, b^p=b and b=1/a, a^3=1 mod p^k, sothat a^2+a+1=0: the cubic root solution of his equation mod p^k (prime p=6n+1). Now the full FLT for positive integers that he was after, and which he suspected to yield inequality for all primes p>2, would follow if ... [2] were the only possible solution of FLT/k, apart from some scaling factor. Then the exponent distributes over a sum: a^p+b^p=(a+b)^p mod p^k, clearly impossible for integer p-th powers < p^{kp} since the 'mixed terms' with a^i.b^(p-i) in the expansion do not sum to zero (which they do mod p^k for the cubic root case).

In fact, notice the recursion (a+b)(a^n+b^n) = a^{n+1} + b^{n+1} + ab(a^{n-1} + b^{n-1}). Writing S(n) for a^n+b^n, and shifing n+1 --> n this becomes: S(n) = (a+b).S(n-1) - ab.S(n-2) . . [3]. Then it is not difficult to derive, given {a,b} in core, that: a+b = -1 --> ab=1, so actually a cubic root-pair is the only solution 'in-core' for k>2. In this case [3] becomes S(n)= -{S(n-1)+S(n-2)} which is like a negative FiBonacci sequence. Starting with -1, -1 it yields for increasing n the repeated sequence {-1,-1,+2}* with period 3 : precisely as expected for cubic roots!

But what about other possible solutions not in core ? . . Without a clue, and Pascal's Calculator (PC) too slow and not geared for p-ary code to do some more experiments, he quit. Putting his notebook away, he let the problem rest. . .
If only he could have gone till p=59 (peanuts for our PC's) then he would have found a clue, and discovered a different kind of root which indeed is not 'in-core' with all three terms. With of course the next questions: if that would be the end of it - or maybe there would be still other types of FLT/k roots, and : would some EDS (Exponent Distributes over a Sum) type of argument hold for these new roots ?

----------
NB: For intro's see on author's homepage (N.F.Benschop = NotaFBene) :
. . . http://home.iae.nl/users/benschop/nf-abstr.htm
and online the full published direct FLT proof (Nov.2005) :
. . . http://pc2.iam.fmph.uniba.sk/amuc/_vol74n2.html (pp 169-184)

Re: Gnomon's reply (to previous uncorrected V1 of this Entry)
about seeking verification of my direct approach to FLT.

I'm not after verification, because that was already done: see publication in the Acta Mathematica of Nov.2005 (of the Univ. Bratislava, who specialize in the application of semigroups to elementary number theory, promoted by prof. Stefan Schwarz there, who originated the known journal "Semigroup Forum" in the sixties). http://pc2.iam.fmph.uniba.sk/amuc/_vol74n2.html (pp 169-184)

I'm just flabbergasted by the lack of interest in a short and direct FLT proof, which I think can be followed (verified) by anyone interested in basic math (residue-and-carry method). The prerequisites such as residue arithmetic, and Fermat's Small Theorem (which he found at about the same time he made his remark on FLT in the margin) are added to the text.

In fact there are still plenty of discussions (e.g. on sci.math) about what Fermat possibly could be so enthusiastic about while making his 'marvelous proof' remark in the margin. My suggestion: he just found his Small Thm FST (mod p), extended it to mod p^k, and noticed the cubic root solution with the exponent distributing over addition (a+b)^p = a+b (mod p^k), blocking extension to integers. He also must have realized that he needed to prove such cubic root solutions are the only ones (which they are not, see the full paper; there are 'triplet' solutions for some p >= 59). Since he found no way to prove this, he let the matter rest. -- NFB

Light critique, 2 points:

Careful and rigorous definition of ALL terms used in any mathematical treatment, taking nothing for granted, improve intelligibility for a lay audience. (Perhaps in an appendix. Though this may seem monotonously tedious for the author, it spares the eager student considerable confusion and frustration and increases appeal.):

I've been shopping for standard math and Greek letter fonts (when I have time) and have yet to find any I consider altogether satisfactory... does help when one has a comprehensive array of signs and symbols in hand and doesn't need to improvise.

Other points: I like the moment of personalization from paragraph two, the correspondence between Fermat and Pascal. Nice to see those personalities coming alive.

Commentary on the immolation of Giordano Bruno: besides a premier pioneering algebraist he was also an important pioneering cryptanalyst, applying his algebraic skills to decrypting secret messages. I often think that his immolation may have more to do with that, a revenge effort exerted through the Holy Office (The Inquisition) than with his 'heretical' (and precolonial!) suggestions that the stars might be other suns and that there might be "souls to be saved" there on worlds orbiting those suns.

Other points: I like the moment of personalization from paragraph two, the correspondence between Fermat and Pascal. Nice to see those personalities coming alive.

Commentary on the immolation of Giordano Bruno: besides a premier pioneering algebraist he was also an important pioneering cryptanalyst, applying his algebraic skills to decrypting secret messages. I often think that his immolation may have more to do with that, a revenge effort exerted through the Holy Office (The Inquisition) than with his 'heretical' suggestions that the stars might be other suns and that there might be "souls to be saved" there on worlds orbiting those suns.

Thanks ITIWBS for your comments. I'll see what I can do more qua definitions and explanations. -- NFB

Thanks, all, for giving such helpful feedback about a rather complex subject!

Just a note to say as we had to move two versions of this out of Peer Review, the final, definitive (!) thread is at:

F48874?thread=5326772