Often I wish that I knew more mathematics and understood it more deeply. But then I wouldn’t have the pleasure of discovering afresh things that other people have known for years. (In some cases hundreds of years.)
Last week, in a discussion of Fermat primes and the Hilbert curve, ShreevatsaR remarked:
BTW, you only need to try primes that are factors of \((4^k – 1)\) for some \(k\)…. Considering powers of 4 up to 32 and prime factors greater than 65537, this means just the primes 87211, 131071, 174763, 178481, 262657, 524287, 2796203, 3033169, 6700417, 15790321, 715827883, 2147483647.
In response I asked (innocently, if skeptically):
Are there primes other than 2 that are known not to be factors of \((4^k – 1)\) for some \(k\)?
ShreevatsaR immediately replied: No, every odd prime must divide some \((4^k – 1)\). And he gave a proof based on the pigeonhole principle. The primes he had listed in his earlier comment are just those that happen to divide \((4^k – 1)\) for an unusually small value of \(k\).
In the middle of the night I had a little epiphany: This is just Fermat’s Little Theorem in disguise. One version of the Little Theorem says: If \(p\) is a prime and \(a\) is a natural number, then either \(p\) divides \(a\) or \(p\) divides \(a^{(p-1)} - 1\). To get back to ShreevatsaR’s statement, just observe that for any prime \(p\) other than 2, \(p-1\) is even, and so we can introduce an integer \(k = \frac{(p-1)}{2}\), making \(4^{k} - 1\) equivalent to \(2^{(p-1)} - 1\).
My previous encounters with Fermat’s Little Theorem have been in the context of primality testing. If you have some natural number \(n\) and you want to find out if it’s a prime, calculate \(2^{(n-1)} - 1 \bmod n\); if the result is anything other than zero, \(n\) is composite. (Unfortunately, the converse statement is not to be relied upon: If \(2^{(n-1)} - 1 \bmod n = 0\), it does not always follow that \(n\) is prime—but that’s a story for another time.)
ShreevatsaR’s comment brought to light something I had never thought about: We know that a prime \(p\) divides \(2^{(p-1)} - 1\), but \(p\) might also divide some smaller number \(2^{(m-1)} - 1\) with \(m < p\). I went searching for the smallest such \(m\) for all primes less than 10,000. Here are the results:
Each dot in the graph represents a prime \(p\). The horizontal coordinate of the dot is the magnitude of \(p\); the vertical coordinate is the least \(m\) such that \(p\) | \(2^{(m-1)} - 1\). Of the 1228 primes shown, 470 lie along the diagonal, indicating that the least \(m\) is in fact equal to \(p\). Another 348 dots lie along a line of slope \(\frac{1}{2}\): For each of these primes, \(p\) divides \(2^{\frac{(p-1)}{2}} - 1\) as well as \(2^{(p-1)} - 1\). The smallest such \(p\) is 7, which divides \(2^3 - 1 = 7\) as well as \(2^6 - 1 = 63\). It’s easy to pick out other sets of points on lines of slope \(\frac{1}{3}\), \(\frac{1}{4}\) and so on. Toward the bottom of the graph, where the least \(m\) gets smaller, the points are sparse and patterns are more difficult to perceive, but the alignments are still present.
The procedure effectively divides the primes into classes distinguished by the value of \(r=\frac{p-1}{m-1}\):
r=1: 3, 5, 11, 13, 19, 29, 37, 53, 59, 61, 67, 83, 101, 107... r=2: 7, 17, 23, 41, 47, 71, 79, 97, 103, 137, 167, 191, 193... r=3: 43, 109, 157, 229, 277, 283, 307, 499, 643, 691, 733... r=4: 113, 281, 353, 577, 593, 617, 1033, 1049, 1097, 1153... r=5: 251, 571, 971, 1181, 1811, 2011, 2381, 2411, 3221... r=6: 31, 223, 433, 439, 457, 727, 919, 1327, 1399, 1423...
There is nothing new or original about all this. Gauss wrote about it in Disquisitiones Arithmeticae in 1801. The primes in the first list are those for which the multiplicative order of 2 mod p is \(p-1\); in other words, the set of residues 2 mod p repeats with period \(p-1\), the largest possible. In Gauss’s terminology, 2 is a primitive root of these primes. In 1927 Emil Artin conjectured that there are infinitely many primes in this set. For the second series the multiplicative order of 2 mod p is \(\frac{p-1}{2}\), for the third group it is \(\frac{p-1}{3}\), and so on. The OEIS has more on each of these series.
Nothing new, but I found the graph a useful aid to understanding. (I would not be surprised to learn that the graph isn’t new either.)
Trivia: What is the largest value of \(r\) encountered in this set of primes? Well, 8191 divides \(2^{(14 - 1)} - 1\). As a matter of fact, 8191 is equal to \(2^{(14 - 1)} - 1\). Thus we have:
\[r = \frac{p-1}{m-1} = \frac{8190}{13} = 630 .\]
Three more of the primes listed by ShreevatsaR are also of the form \(2^{n} - 1\). On the assumption that we have a boundless supply of such primes, it would appear there is no limit to the value of \(r\). [Update: Please see the comments, with illuminating contributions by ShreevatsaR, Gerry Myerson and (via Stack Exchange) David Speyer.]
Very interesting; I had never thought of this! About the assumption in the final paragraph that we have a boundless supply of such primes (primes of the form \( 2^n - 1 \)), this is basically an open problem; see Mersenne primes. Apparently, as of now only 48 such primes are known. (The value of \( r \) that the largest known one gives is \( \dfrac{2^{57885161} - 1}{57885161} \) which is very large indeed.)
Both Mersenne primes and Fermat primes turned up in the context of the previous post because \( 4^k - 1 \) has the factorization \( (2^k - 1)(2^k + 1) \), and a number of the form \( 2^k - 1 \) can be prime only if \( k \) is prime, and a number of the form \( 2^k + 1 \) can be prime only if \( k \) is a power of \( 2 \). [Both for essentially the same reason: \( x^n - y^n \) has a factor \( x - y \), so in the first case if \(k = ab \) then \( 2^k - 1 = (2^a)^b - 1 \) has a factor \( 2^a - 1 \), and in the second case if \( k \) has an odd factor \( a \) (say \( k = ab \) again) then \( 2^k - 1 = (2^b)^a - (-1)^a \) has a factor \( 2^b - (-1) \).]
It may be possible to prove that there is no limit to the value of \( r \) even without assuming there are infinitely many Mersenne primes, but this is for someone who knows more number theory to answer. :-)
The sequence of r-values 1, 1, 2, 1, 1, 2, 1, 2, 1, 6, … is tabulated at the OEIS. No indication there of whether it’s known to be unbounded, but I didn’t chase up the citations given there.
David Speyer has posted a proof that r is unbounded at math.stackexchange.com