Fermat on FLT

...not Fermat's last theorem, but Fermat's little theorem. When I took an introductory number theory course I was inordinately amused by this coincidence of abbreviations. Fermat's little theorem is more useful; I came across it most recently because we're explaining RSA cryptography to the Ideas in Mathematics class. For those of you who don't know it, the RSA algorithm works as follows. In order to enable people to encrypt messages to be sent to you, in such a way that only you can decrypt them, calculate three numbers n, e, and d. The number n is the product of two large primes p and q; e is some number relatively prime to φ(n) = (p - 1)(q-1); d is the multiplicative inverse of e modulo φ(n). Then publicize the numbers n and e; keep d secret. Calculating d from these in the obvious way requires factoring φ(n).

A plaintext message T is then encrypted as a ciphertext C, where C = T^e mod φ(n); a ciphertext message C is then decrypted by taking C^d mod φ(n). The reason that decryption is the inverse of encryption -- which is of course what one wants -- is Euler's theorem, which states that a^φ(n) mod n = 1 whenever n and a are relatively prime positive integers. Assuming T and φ(n) are relatively prime, then, applying the encryption map and then the decryption map to some plaintext message T gives T^de mod n; but de is one more than some multiple of φ(n), so that's just T. (This is only true when T and φ(n) are relatively prime.)

Anyway, the point of this post really wasn't to talk about RSA cryptography, but to point to a letter written from Fermat to Frenicle in 1640. One often hears that Fermat very rarely proved things but just made motions saying "I have a proof", but the only such remark one actually hears repeated is the famous statement of Fermat's Last Theorem:

Cubum autem in duos cubos, aut quadratoquadratum in duos quadratoquadratos, et generaliter nullam in infinitum ultra quadratum potestatem in duos ejusdem nominis fas est dividere: cujus rei demonstrationem mirabilem sane detexi. Hanc marginis exiguitas non caperet.

which translates as something like:

It is impossible for a cube to be the sum of two cubes, a fourth power to be the sum of two fourth powers, or in general for any number that is a power greater than the second to be the sum of two like powers. I have discovered a truly marvelous demonstration of this proposition that this margin is too narrow to contain.

(I don't know Latin, so I take no responsibility for the correctness of this translation.) It turns out that there's a less famous remark regarding the Little Theorem:

Et cette proposition est généralement vraie en toutes progressions et en tous nombres premiers; de quoi je vous envoierois la démonstration, si je n'appréhendois d'être trop long.

That is:

This proposition [Fermat's Little Theorem] is generally true for all progressions and for all prime numbers; I would send you the demonstration if I did not fear that it were too long.

(The "progressions" refer to Fermat's phrasing of the theorem, in which he refers to the p-1 term of a geometric progression a, a², a³, ... and claims that it is one more than a multiple of p.) The rest of the letter includes other such statements without proofs, but illustrated with copious examples. (The link I provided is to the version of David Zhao and Amanda Bergeron, which includes both the French text of the letter and their English translation; the English translation of Fermat's French I gave above is my own.)