﻿ Fermat's congruence

# Fermat's Congruence Modulo a Prime-Power

Let a, b, and c be natural numbers relatively prime in pairs and let p be a prime greater than 3.  The congruence ap+bpcp(mod p2), p does not divide abc, is an example of Fermat's congruence modulo a prime power.  Probabilistic arguments and empirical evidence indicate the probability for a given p, 6 divides p+1, that there do not exist a, b, and c such that ap+bpcp (mod p2), p does not divide abc, is approximately e-1/6, or about .85 (here e=2.71828...).  Since the primes greater than 3 are either of the form 6k+1 or 6k-1 and primes of one form occur as frequently as primes of the other form, this criterion precludes first-case solutions (where p does not divide abc) of Fermat's equation ap+bp=cp for about 42% of the primes.  If 1+(d-1)pdp(mod p2) where d is a natural number less than p, then (1, d-1, d) will be referred to as a "reduced" solution of ap+bpcp(mod p2), p does not divide abc.  The following theorems are stated without proof, but the proofs are elementary.  That only reduced solutions need be considered is shown by the following theorem;

(1) ap+bpcp(mod p2), p does not divide abc, only if 1+(d-1)pdp(mod p2), 1<d<p, where dca-1(mod p).

(A proof uses the lemma that if f and g are integers and p divides f-g, then p2 divides f p-gp.)  Let ti (i=0, 1, 2, ..., (p-1)) be the number of numerically consecutive roots of the congruence xp-1yi(mod p2), 0<x<p2, where yi=ip+1.  (If, for example, x1, x1+1, and x1+2 are roots, the number of consecutive roots in this sequence will be considered to be 2.  Similar counting of consecutive roots applies for longer sequences.)  The problem of finding the number of reduced solutions can be reformulated as follows;

(2) The number of reduced solutions of ap+bpcp(mod p2), p does not divide abc, equals t0.

(A proof uses Euler's theorem that if f and m are relatively prime natural numbers, then f φ(m)≡1(mod m) where φ(m) is Euler's "phi" function.)  y0, y1, y2, ..., yp-1 are the roots of the congruence yp≡1(mod p2), 0<y<p2.  By Euler's theorem, if p does not divide f, then f p(p-1)≡1(mod p2), and hence the congruence xp-1y0(mod p2), 0<x<p2, has exactly p-1 roots.  In general, the congruence xp-1yi(mod p2), 0<x<p2, has exactly p-1 roots.  None of these congruences have a common root, so, taken together, the roots of these congruences are in some order the integers between 0 and p2 not divisible by p.  That there are consecutive roots of these congruences is shown by the following theorem;

(3) t0+t1+t2+...+tp-1=p-2.

(A proof uses the lemma that the congruence xp-1≡(x+1)p-1(mod p2), 0<x<p2, has exactly p-2 roots.)  Additive inverses of roots of these congruences account for the following theorem;

(4) If x1 and x2=x1+1 are roots of xp-1yi(mod p2), 0<x<p2, then (p2-x2) and (p2-x1) are also roots and (p2-x1)=(p2-x2)+1.  If x1 and x2=x1+1 are roots of xp-1yi(mod p2), 0<x<p2, where i≠-(2p-1-1)/p(mod p), then x1 and (p2-x2) are distinct.  If i≡-(2p-1-1)/p(mod p), then x1=(p2-1)/2 and x2=x1+1 are roots of xp-1yi(mod p2), 0<x<p2, and x1 and (p2-x2) are not distinct.

By Theorem (4), exactly one of t0, t1, t2, ..., tp-1 is odd.  Let ui=ti/2 if ti is even, or (ti-1)/2 if t i is odd.  The ui values, i≠0, are distributed as if ui were a random variable having a Poisson probability distribution with a parameter of 1/2.  The distribution of the ui values, i≠0, for the p<10000 is;

 Number Fraction Poisson ui=0 3477534 .606353 .606531 ui=1 1742663 .303856 .303265 ui=2 0433319 .075555 .075816 ui=3 0071744 .012509 .012636 ui=4 0008949 .001560 .001580 ui=5 0000895 .000156 .000158 ui=6 0000058 .000010 .000013 ui=7 0000002 .000000 .000001 Total 5735164 .999999 1.000000

An explanation for the probability distribution of the ui values, i≠0, is that the probability that a root of xp-1yi(mod p2), 0<x<p2, is one larger than another root is 1/p (since the p-1 roots have p(p-1) possible values) and that there are (p-1)/2 possible independent roots one larger than another root.  The probability distribution of the ui values, i≠0, would then be P(x)=((p-1)/2 "choose" x)(1/p)x(1-1/p)(p-1)/2-x, x=0, 1, 2, ..., (p-1)/2.  ((e "choose" f) where e and f are non-negative integers denotes a binomial coefficient.)  This binomial probability distribution is very closely approximated by a Poisson probability distribution with a parameter of 1/2.

Multiplicative inverses of the roots of the congruence xp-1≡1(mod p2), 0<x<p2, account for the different probability distribution of the t0 values.  Suppose x1 is a root of xp-1≡1(mod p2), 0<x<p2, and that x1 is one larger than another root.  Denote the least residue of 1-x1 modulo p2 by f(x1).  Then f(x1) is a root of xp-1≡1(mod p2), 0<x<p2, and f(x1) is one larger than another root.  Let x1-1 denote an integer such that x1x1-1≡1(mod p2) and denote the least residue mod p2 of x1-1 by g(x1).  Then g(x1) is a root of xp-1≡1(mod p2), 0<x<p2.  Also, (x1-1)p-1x1 p-1(mod p2) and hence (1-x1-1)p-1≡1(mod p2).  Then (x1-1-1)p-1≡1(mod p2) so that g(x1) is one larger than another root of xp-1≡1(mod p2), 0<x<p2.  The values of f(x1), gf(x1), fgf(x1), gfgf(x1), fgfgf(x1), and gfgfgf(x1) are the least residues modulo p2 of 1-x1, (1-x1)-1, -x1(1-x1)-1, -x1-1(1-x1), x1-1, and x1 respectively.  These are the formal values (modulo p2) of the cross ratio function of geometry and complex analysis.  Denote {f(x1), gf(x1), fgf(x1), gfgf(x1), fgfgf(x1), gfgfgf(x1)} by S(x1).  Suppose that x2 is a root of xp-1≡1(mod p2), 0<x<p2, and that x2 is one larger than another root . Then S(x2) is a permutation of S(x1) or no element of S(x2) is in S(x1).  Whether the elements of S(x1) are distinct is determined by the following theorem;

(5) The elements of S(x1) are distinct unless an element equals 2 or a root of x2-x+1≡0(mod p2), 0<x<p2.  If 2 is an element of S(x1), then the distinct elements of S(x1) are 2, (p2+1)/2, and p2-1.  If a root of x2-x+1≡0(mod p2), 0<x<p2, is an element of S(x1), then both roots of x2-x+1≡0(mod p2), 0<x<p2, are elements of S(x1) and the distinct elements of S(x1) are these two roots.  If p≡1(mod 6), then x2-x+1≡0(mod p2), 0<x<p2, has two roots, otherwise x2-x+1≡0(mod p2), 0<x<p2, has no roots.

If p≠1(mod 6) and 2p-1≠1(mod p2), let v=t0/6, or if p≡1(mod 6) and 2p-1≠1(mod p2), let v=(t0-2)/6, or if p≠1(mod 6) and 2p-1≡1(mod p2), let v=(t0-3)/6, or if p≡1(mod 6) and 2p-1≡1(mod p2), let v=(t0-5)/6.  The v values are distributed as if v were a random variable having a Poisson probability distribution with a parameter of 1/6.  The distribution of the v values for the p<100000 is;

 Number Fraction Poisson v=0 8150 .849844 .846482 v=1 1324 .138060 .141080 v=2 0112 .011679 .011757 v=3 0003 .000313 .000653 v=4 0001 .000104 .000027 Total 9590 1.000000 .999999

An explanation for the probability distribution of the v values is that the probability that a root of xp-1≡1(mod p2), 0<x<p2, is one larger than another root is 1/p and that there are about [(p-1)/6] (the brackets denote the floor function) possible independent roots one larger than another root.  The probability distribution of the v values would then be P(x)=([(p-1)/6] "choose" x)(1/p)x(1-1/p)[(p-1)/6]-x, x=0, 1, 2, ..., [(p-1)/6].  This binomial probability distribution is very closely approximated by a Poisson probability distribution with a parameter of 1/6.

Wieferich's theorem states that there can be first-case solutions of Fermat's equation ap+bp=cp only if 2p-1≡1(mod p2).  Mirimanoff's theorem states that there can be first-case solutions of Fermat's equation only if 3p-1≡1(mod p2).  There shouldn't be any p such that 3p-1≡2p-1≡1(mod p2) since the sum of (1/p)(1/p) over all p converges and the only p less than 3*109 such that 2p-1≡1(mod p2) are 1093 and 3511, and 3p-1≠1(mod p2) for both of these p.  (It's unlikely that this can be proved rigorously.)

Klösgen1 computed the solutions of the congruence 1+Y p+Zp≡0(mod p2) for all primes less than 20000 and found similar probabilities.  In Paulo Ribenboim's account of this result (given in his book Fermat's Last Theorem For Amateurs, Springer-Verlag, 1999) the cross-ratio function and the Poisson probability distribution aren't mentioned.

References

Klösgen, W., Untersuchungen über Fermatsche Kongruenzen, Gesellschaft Math. Datenverarbeitung, No. 36, 1970, 124 pp., Bonn.

Software

The above propositions were confirmed using MSVC++™.  Use test1s and test2s to find consecutive roots of xp-1≡1(mod p2), 0<x<p2.  Use test3s to find consecutive roots of the congruences xp-1y(mod p2), 0<x<p), yp≡1(mod p2).  Subroutines used are carry, lmbd, div12864, div6432, mul6432, mul6464, mul3232, sub128, and sub64.  A prime and primitive root look-up table used is inputs.  Readers may copy and modify this software.  No guarantee is made that it is error-free.