Fermat’s little theorem
An “etymological” and visual exploration of Fermat’s little theorem, one of the keys to understanding the RSA encryption algorithm.
In a 1640 letter to his friend Frénicle de Bessy, Pierre de Fermat wrote that:
Tout nombre premier mesure infailliblement une des puissances — 1 de quelque progression que ce soit, et l’exposant de la dite puissance est sous-multiple du nombre premier donné — 1 ; et, après qu’on a trouvé la première puissance qui satisfait à la question, toutes celles dont les exposants sont multiples de l’exposant de la première satisfont tout de même à la question.
which, keeping all the archaisms of the original French version, translates to English as:
Every prime number measures infallibly one of the powers minus one of any progression, and the exponent of said power is a sub-multiple of the given prime minus one; and, after one has found the first power that satisfies the question, all powers whose exponents are multiples of the exponent of the first one satisfy similarly the question.
A fairly difficult proposition to parse, for most of us at least. Students of modern mathematics are more familiar with the more succinct form:
If p is a prime and a is any integer not divisible by p, then a ^ (p − 1) − 1 is divisible by p.
There is merit however in going back to Fermat’s initial proposition and checking that the modern version captures all that Fermat’s prose contains, and this is what this article proposes to do, with visual supports.
Part 1: Progressions and Powers
Every prime number measures infallibly one of the powers minus one of any progression
Fermat calls a “progression” what is nowadays known in French known as a “suite géométrique”, and in English still known as a “geometric progression”, that is to say, a “sequence of numbers where each term after the first is found by multiplying the previous one by a fixed, non-zero number called the common ratio.” For example, “2, 4, 8, 16, 32, etc.” is a progression of ratio 2, and “3, 9, 27, 81, etc.” is a progression of ratio 3.
If we use the convention that progressions start from their ratio r, we can see that the n-th element of any such progression is r to the power n, or the n-th power of ratio r. For example, the third element of the progression of ratio 2 is 8 = 2³ or the third power of 2, and for the progression of ratio 3, it is 27 = 3³, the third power of 3.
When Fermat mentions a given n-th “power of any progression”, he therefore means a given n-th “element” of a geometric progression.
If we stack progressions vertically in ascending ratio order, we can get a better sense of what Fermat’s little theorem’s first fragment means:
Fermat states that “every prime number measures one of the powers minus one of any progression”, that is to say, for every prime number, there exists a column of this table such that all numbers of that column minus one are multiples of that prime. For instance, in column 6, the sixth powers minus one are: 63 — 728 — 4,095 — 15,624 — 46,655 — 117,648 — 262,143 — 531,440 — 999,999, which are multiples of prime number 7 — with the exception of the sixth power minus one from the progression of 7 (117,648) (see NB). Hence for prime 7, there does exist a column of the table such that 7 divides almost all powers minus one.
NB: the accurate statement that Fermat should have made, is that “every prime number measures one of the powers minus one of any progression”… with the exceptions of progressions whose ratios are a multiple of the given prime,(e.g. for prime 7, progressions 7, 14, 21, etc.). This is “fixed” in the modern formulation, specifying that “if p is a prime and a is any integer not divisible by p, then a ^ (p − 1) − 1 is divisible by p.”
Part 2: Primes minus one
…the exponent of said power is a sub-multiple of the given prime minus one; and, after one has found the first power that satisfies the question, all powers whose exponents are multiples of the exponent of the first one satisfy similarly the question.
In the second half of his proposition, Fermat posits that powers which exhibit this behaviour are sub-multiples of the prime minus one. For example, for prime 7, candidate powers are 2, 3, or 6. Powers 2 and 3 do not verify the property of having their values minus 1 divisible by 7 (e.g. 9²-1=80 is not divisible by 7), but power 6 does (as shown in Part 1). Power 6 is therefore “the first power that satisfies the question”, and Fermat goes on to say that as a result, all multiples of 6 also verify the property that their values minus one are divisible by 7 (e.g., n¹²-1 should be divisible by 7 for all n other than multiples of 7).
This means that, according to Fermat, the prime minus one always verifies the proposition: indeed, if at least one sub-multiple of the prime minus one is valid, and the multiples of that solution are all valid too, then the prime minus one is either the first valid exponent, or a multiple of the first valid exponent, hence valid itself.
As a result, the theorem can be reformulated as:
(A) Given a prime p, the (p-1)-th power minus one of any progression (except those whose ratio is a multiple of p) is divisible by p. (B) If p-1 is not prime, then one or more of p-1’s sub-multiples may share the same property. (C) Multiples of exponents found in (A) and (B) also share the property that their powers are divisible by p.
Several proofs of (A) exist for example on Wikipedia. We can on the other hand easily prove (C) here: if aⁿ-1 ≡ 0 [mod p] for all integers a not divisible by p, then given a multiple n ·m of n, we have (aᵐ)ⁿ-1≡ 0 [mod p] too, since aᵐ is another integer not divisible by p. (B) requires that we find one and only one instance where sub-multiples of the prime minus one indeed verify the same property… but, I am unable to find or build such an example. Nevertheless, the fact that Fermat thought it important to mention that possibility seems in my mind to nicely foreshadow the work of Euler more than a century later and that of Carmichael in the 20th century (more on this thought in Part 4).
At this point we are mostly done deciphering Fermat’s original statement. One might wonder however, whether the relationship identified in (A) is anything special, that is, whether it only occurs for primes, or in fact happens for most numbers, which would make the proposition a lot less interesting. With a computer, we can empirically answer that question by calculating a table of the first n powers modulo n+1 of the first m progressions, similar to what we did in Part 1.
Replicating the above chart with more powers and progressions, with a coloured scale to represent numbers, we get the following chart:
We can numerically test the prevalence of primes among the integers for which the property holds(i.e., for which columns appear in the chart above), and conversely, we can verify that the proposition holds for each of the first few primes, with the Python code pasted below:
The code shows that for the first 10,000 integers, the property was verified for 1,229 integers, all of which were primes; conversely, all 1,229 primes smaller than 10,000 verified the property.
In practice, while it is unproven* that property (A) is only true for primes, it is a marker of primes often enough that the property is used as a part of primality tests, that is, a number is said to be a probable prime if it verifies property (A). Other methods can be used in conjunction with the Fermat test to increase the level of confidence that a number is indeed prime.
NB*: it is often noted that “Fermat’s primality test and is a necessary but not sufficient test for primality” (Wolfram Alpha). However, to my knowledge, this statement is always made about an interpretation of Fermat’s little theorem which limits it to a subset of candidate progressions, eliminating all which are not co-prime to the test number (see Part 3).
Part 3: Carmichael numbers
We noted in Part 1 that Fermat’s verbatim statement that “every prime number measures one of the powers minus one of any progression” is incorrect without the addition that it is only true for progressions “whose ratio is not a multiple of that prime”. We formulated this condition by necessity, and we could argue that this was the smallest possible correction we could make to Fermat’s statement, i.e., limiting its generality the least, or even more simply, limiting the meaning of any in any progression the least.
However, we could have formulated the condition in a different way, by correcting the statement to: “every prime number measures one of the powers minus one of any progression” … “so long as the ratio is co-prime to that prime.”
In the rest of this article, we denote (A) the property with its former addition, and (A*) the alternative formulation that:
(A*) Given a prime p, the (p-1)-th power minus one of any progression (so long as their ratio is co-prime to p) is divisible by p
Though these alternative statements are in practice identical when the number being tested is prime — eliminating multiples of a prime is equivalent to filtering only to numbers who are co-prime to that prime — they in fact introduce important nuances when testing Fermat’s property on non-primes.
For example, if, while unable to determine whether number 561 is prime, we decided to put it to the test by computing the 560th power minus one of any progression and verifying whether those values are divisible by 561, we would:
- under (A), test whether the property holds for all progressions other than 561, and n · 561 for all integers n > 1 (which we did in Part 2)
- under (A*), test whether the property holds for all progressions, except those whose ratio is a multiple of 3, of 11, or of 17
561 fails the former and passes the latter.
We can re-run our code snippet from Part 2, adapting it from (A) to (A*), to check how many such numbers appear:
We find this time, that for the first 10,000 integers, property (A*) was verified for 1,236 integers, 1,229 of them prime, 7 of them not. As before, all primes under 10,000 did on the other hand verify the property. The numbers which verified (A*) under 10,000 without being prime are: [561, 1105, 1729, 2465, 2821, 6601, 8911], also known as the Carmichael numbers.
Visually, small Carmichael numbers are hard to mistake for prime numbers, since, being the composites of rather small primes, property (A) holds true for them for only a fraction of all possible progressions.
For example, a⁵⁶⁰-1 = 0 mod 561 is false for a in [3, 6, 9, 11, 12, 15, 17, 18, 21, 22, etc.] In fact, we can compute that, for the first 1000 progressions, 561 exhibits property (A) for only 57% of all progressions.
Left, we show a zoomed-in version of the charts presented in Part 2, focused this time on the region around 561: the colour in each cell represent the n-th power modulo n+1 of an integer m, where n is given by the column number and m is given by the row number.
Compare columns 556 and 562 (highlighted in pink), standing for primes 557 and 563; to column 560 (highlighted in red) standing for Carmichael number 561. While the former appear all dark, the latter exhibits an array of colours difficult to mistake for the pattern of a prime.
Things tend to get “better” the larger the Carmichael number, and for example, 252,601 exhibits property (A) for 95% of the first 252,601 progressions, meaning two things:
- for large numbers, the visual representation of Carmichael numbers starts to look very similar to that of prime numbers
- even under interpretation (A) testing the primality of large numbers by sampling progressions is insufficient, as large Carmichael numbers can exhibit property (A) for a large majority of progressions
Generally though, the conclusion of this Part 3 is that under interpretation (A*), Carmichael numbers indeed prove that Fermat’s primality test is not a sufficient test for primality.
Part 4: Euler’s theorem, Carmichael’s theorem, and a conclusion
While interpretation (A*) seemingly weakens Fermat’s little theorem by making the converse of (A*) false (on the other hand, it seems to me that the converse of (A) might be true —can an informed reader please comment?), it opens the door to evolutions of Fermat’s little theorem, such as Euler’s theorem.
Euler’s theorem
From the starting point that integers n and a are co-prime positive integers, as in interpretation (A*), Euler proposes in 1763 that:
where φ(n), the totient function, counts the positive integers relatively prime to n up to n.
In the special case where n is prime, φ(n) = n-1, making Euler’s theorem strictly equivalent to Fermat’s little theorem. More broadly however, Euler’s theorem offers a generalisation of Fermat’s little theorem, by giving all numbers, not just primes, interesting relationships to powers of a majority of progressions.
Replicating the approach from Part 2 using this time, the φ(n)-th power modulo n in each column n, we get the following visualisation:
Carmichael’s theorem
Building on Euler’s theorem, Carmichael proposes that for any integer n, there exists λ(n) ≤ φ(n) verifying:
for all integers a co-prime with n, where λ(n) is the smallest integer verifying the property. For this reason, λ(n) is also known as the reduced totient function or the least universal exponent function.
Wikipedia lists the Euler’s totients and Carmichael’s reduced totients for the first few integers, and interestingly, we find that Carmichael’s totients are always sub-multiples of Euler’s ones when they are not equal to them.
As an illustration of Carmichael’s theorem, one can verify that:
- Using 15 as a non-prime example, Euler’s totient φ(15) = length[1, 2, 4, 7, 8, 11, 13, 14] = 8
- By Euler’s theorem: a⁸ mod 15 = 1 for any a co-prime to 15, and we can verify that for example, 7⁸ mod 15 = 1, or 11⁸ mod 15 = 1
- And finally, given Carmichael’s totient λ(15) = 4 we should be able to see that a⁴ mod 15 = 1 for any a co-prime to 15, which we indeed verify with 7⁴ mod 15, and 11⁴ mod 15, both equal to 1.
Conclusion
While we have journeyed far from Fermat’s original statement (that is, we consider only co-primes (a, p) under interpretation (A*) rather than eliminating only multiples a = n·p for all integers n, and on the other hand we have expanded the exponent universe to all integers versus initially just primes), I cannot help but think that Fermat’s mysterious proposition (B) that sub-multiples of the highest valid exponent for property (A) may also be valid, for which I could not find any example under the initial interpretation, finds its resolution in Euler and Carmichael’s work — via Euler, who provided the general form of the highest valid exponent verifying (A) for any integer (Euler’s totient) — and via Carmichael, who formalised the concept of “the first power, sub-multiple of the given [highest valid exponent] satisfying similarly the question” with his reduced totient function.
Was Fermat’s mysterious proposition (B) foresight, or great intuition on his part? Were Euler and Carmichael accomplices in creating a resolution for Fermat’s incomplete statement?
A summary
- Fermat’s original formulation of what is now known as his little theorem describes the special relationship each prime number p has with the (p-1)-th power of any integer — Fermat omits to mention exceptions to that “any”, also mentions mysterious sub-multiples of (p-1) which allegedly share the same special relationship.
- Fermat’s statement as is provides the basis for beautiful visuals, which also tend to confirm that the special relationship described in Fermat’s letter is fairly unique to primes, no other numbers exhibiting the same patterns.
- Carmichael numbers are proposed as counterexamples to the notion that Fermat’s property only applies to primes, but the visuals show that this rebuttal relies on a different interpretation of Fermat’s letter (the exceptions to that “any”). We also learn that maybe, maybe indeed large Carmichael numbers can trip us up in numerical primality tests that wouldn’t test Fermat’s property on all powers, but on samples of powers.
- It turns out that the different interpretation of Fermat’s letter required to understand the Carmichael argument opens the door to a much larger understanding of Fermat’s theorem: Euler and Carmichael expand the special relationship to all integers n, not just primes, and instead of having that relationship with n-1, those n have it with their totient (n-1 for primes indeed, but different for non-primes).
- Strangely, Fermat’s mysterious remark about submultiples does not seem to work for primes, but does for non-primes, where Carmichael’s totients play the role of valid submultiples to Euler’s totients. A conclusion or connection established by chance, intuition, inspiration, or all of the above, across centuries.
With this, we are now conceptually equipped to enter the final chapter of this Bitwise series, the RSA encryption algorithm. Until next time!
