As discussed in the note On Case 1 of Fermat's Last Theorem, the congruence (x+1)^p - (x)^p - 1 = 0 (mod p^2) (1) must have a non-trivial solution x coprime to p in order for there to exist an integer solution of Fermat's equation x^p + y^p + z^p = 0 with xyz coprime to p. (Incidentally, the numbers 1093 and 3511 are the only known primes such that x=1 is a root of congruence (1)). However, this congruence has at least one non-trivial root for every prime p of the form 3k+1. (Here non-trivial means other than x = 0 or -1 modulo p). On the other hand, there are no non-trivial solutions at all for most primes of the form 3k-1. The exceptions less than 7000 are listed below 59 83 179 227 419 443 701 857 887 911 929 971 977 1091 1109 1193 1217 1223 1259 1283 1289 1439 1487 1493 1613 1637 1811 1847 1901 1997 2003 2087 2243 2423 2477 2579 2591 2729 2777 2969 3089 3137 3191 3203 3251 3467 3527 3533 3881 3917 3929 4001 4079 4091 4643 4649 4691 4889 4943 5189 5303 5351 5711 5843 5849 5903 6257 6359 6389 6551 6569 6581 6947 6959 The total numbers of primes of the form 3k-1, and the numbers of these "exceptional" primes, up to various levels are listed below Tot Excpt dens 1000 86 13 0.151 2000 153 30 0.196 3000 221 40 0.181 4000 277 51 0.184 5000 337 59 0.175 6000 397 66 0.166 7000 454 74 0.162 Clearly if x is a root of (1) for a given prime p, then so is x+kp for every k, so we can represent all the non-trivial roots by just those in the range 1 to p-2. Furthermore, if x is a root, then -(x+1) is also a root, in view of (-(x+1)+1)^p - (-(x+1))^p = (-x)^p - (-(x+1))^p (mod p^2) Therefore, we can represent all the non-trivial roots by the set of roots in the range from 1 to (p-1)/2. The table below shows the number of primes of the form 3k-1 less than 160000, along with the number exceptional primes in this range. # of primes number of range the form exceptional 3k-1 primes ratio -------------- ----------- ----------- --------- 0 - 10000 616 96 0.15584 10000 - 20000 520 83 0.15961 20000 - 30000 497 83 0.16700 30000 - 40000 479 72 0.15031 40000 - 50000 463 66 0.14254 50000 - 60000 466 77 0.16523 60000 - 70000 449 74 0.16481 70000 - 80000 448 65 0.14508 80000 - 90000 436 71 0.16284 90000 - 100000 432 78 0.18055 100000 - 110000 427 66 0.15456 110000 - 120000 432 67 0.15509 120000 - 130000 440 73 0.16590 130000 - 140000 427 63 0.14754 140000 - 150000 408 64 0.15686 150000 - 160000 421 59 0.14014 ----- ----- -------- 0 - 160000 7361 1157 0.15717 It certainly appears that the density of exceptional primes among all primes of the form 3k-1 is fairly constant, independent of the size of the primes involved. It's also worth noting that whenever a prime of this form has (non-trivial) solutions, the number of solutions in the reduced range 1 to (p-1)/2 is a multiple of three (as explained below). The distribution of the number of solutions for the primes less than 160000 is shown below # of primes # of solutions p = 3k-1 solutions ----------- -------------- 6204 0 1055 3 98 6 4 9 The density seems to drop roughly by factors of 1/6, 1/11, and 1/24 for each additional set of three roots, suggesting that primes with 12 roots would have a density of roughly 1/48 times the density of primes with 9 roots. The reason that these roots occur in sets of 3 is easier to see if we consider the whole range of residues from 1 to p-2. Over this range the solutions of (x+1)^p - x^p - 1 = 0 (mod p^2) occur in sets of six related values, because if x is a solution, then another solution is given by replacing x with either -(1+x) as we saw previously, or with -(1 + 1/x), where the inverse is taken modulo p. The former has a period of 2, whereas the latter has a period of 3, and together these substitutions generate a group of order 6 with the members a(x) = x b(x) = 1/x c(x) = -(1+x) d(x) = -1/(1+x) e(x) = -x/(1+x) f(x) = -(1+x)/x This is isomorphic to the group of symmetries of an equilateral triangle. The operation with period 2 is like flipping the triangle over in the plane, and the operation with period 3 is like rotating the triangle through 120 degrees. In general, these operations can be used to partition the residues modulo p into equivalence classes of 6 elements that are related according to these operations. For example, with p=59 we get the following sets a b c d e f -- -- -- -- -- -- 1 1 57 29 29 57 2 30 56 39 19 28 3 20 55 44 14 38 * 4 15 54 47 11 43 * 5 12 53 49 9 46 6 10 52 42 16 48 7 17 51 22 36 41 8 37 50 13 45 21 18 23 40 31 27 35 24 32 34 33 25 26 The two sets marked with asterisks are the values that satisfy (1) in the range from 1 to p-2. Obviously for each set we have the relations a + c = d + e = b + f = -1 (mod p) ab = cd = ef = 1 Notice that for primes congruent to +1 (mod 3) there is always a degenerate set corresponding to the algebraic factor (1 + x + x^2)^2 of equation (1) when p is of this form. (For more on this, see the note Sums of Powers in Terms of Symmetric Functions. For example, with p=31 we have the sets a b c d e f -- -- -- -- -- -- 1 1 29 15 15 29 2 16 28 10 20 14 3 21 27 23 7 9 4 8 26 6 24 22 5 25 25 5 25 5 11 17 19 18 12 13 Here we see that 5 and 25 are roots of (1+x+x^2)^2 = 0 (mod 31)^2. Also, the set containing 1 always consists of just three distinct elements, +1, -2, and (p-1)/2. So, if p is of the form 6k+1, the residues from 1 to p-2 are partitioned into one set with 3 members, one set with 2 members, and then the remaining (p-2)-3-2 = 6k+1-2-3-2 = 6(k-1) residues are partitioned into k-1 sets. On the other hand, if p is of the form 6k-1, the algebraic factor (1+x+x^2) occurs only to the 1st power, so there is no degenerate set of 2 elements. Thus the residues are patitioned into one set of 3 elements, and then the remaining (p-2)-3 = 6k-1-2-3 = 6(k-1) residues are partitioned into k-1 sets. We recall that only the primes 1093 and 3511 have the degenerate set containing 1 as solutions of (1). Just to give one more example of an exceptional prime, with p=83 we have the partition a b c d e f -- -- -- -- -- -- 1 1 81 41 41 81 2 42 80 55 27 40 3 28 79 62 20 54 4 21 78 33 49 61 5 50 77 69 13 32 6 14 76 71 11 68 7 12 75 31 51 70 8 52 74 46 36 30 * 9 37 73 58 24 45 10 25 72 15 67 57 16 26 66 39 43 56 17 44 65 23 59 38 18 60 64 48 34 22 19 35 63 29 53 47 Again the set marked with an asterisk represents the solutions of congruence (1) in the range 1 to p-2. Regarding the density of these primes, notice that the expression (x+1)^p - x^p - 1 is always a multiple of p, so we can divide that out, and we are left with a polynomial that wish to set equal to zero modulo p (so that the full expression vanishes modulo p^2). For any given value of x, if we assume the value of this polynomial is randomly distributed over the residues mod p, we can say that the chances are about 1/p that it will vanish. Now, the number of independent x values that we can try is really only (p-5)/6 (which is k-1 from above), because the solutions cover the equivalence classes described above. Thus, for any given prime p we have (p-5)/6 attempts, each of which has a 1/p probability of success, so overall the probability of at least one solution (up to equivalence class) should be about [(p-5)/6](1/p) = (1/6)(1 - 5/p) Thus it isn't too surprising that the density is roughly 1/6 = 0.167. It would be interesting to know if there is any other way of characterizing these exceptional primes, besides evaluating (1).

Return to MathPages Main Menu