Fermat's Congruence Modulo a Prime-Power
Created | Updated Nov 28, 2008
It's commonly thought that mathematics is deterministic, but there are well-defined variables that appear to have random values . Such a variable is involved in Fermat's congruence modulo a prime-power. Some mathematical background will be required to say what Fermat's congruence modulo a prime-power is. A natural number is a positive integer. A non-zero integer x is said to divide an integer y if y is an integer multiple of x. An integer x is said to be congruent to an integer y modulo a non-zero integer z (denoted by x≡y(mod z)) if z divides x-y. An integer x is said to be a least residue of an integer y modulo a non-zero integer z if x≡y(mod z) and 0≤x<z. Integers x and y are said to be relatively prime if they have no common divisors other than 1 or -1. If x and y are relatively prime non-zero integers, there exists a multiplicative inverse of x (denoted by x-1) modulo y such that xx-1≡1(mod y). Let a, b, and c be natural numbers relatively prime in pairs and let p be a prime greater than 3. The congruence ap+bp≡cp(mod p2), p does not divide abc, is an example of Fermat's congruence modulo a prime power (p values of 2 and 3 have been arbitrarily excluded here).
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+bp≡cp(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)p≡dp(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+bp≡cp(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+bp≡cp(mod p2), p does not divide abc, only if 1+(d-1)p≡dp(mod p2), 1<d<p, where d≡ca-1(mod p).
(A proof uses the lemma that if f and g are integers and p divides f-g, then p2 divides fp-gp.) Let ti (i=0, 1, 2, ..., (p-1)) be the number of numerically consecutive roots of the congruence xp-1≡yi(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+bp≡cp(mod p2), p does not divide abc, equals t0.
(A proof uses Euler's theorem that if f and m are relatively prime integers, 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 fp(p-1)≡1(mod p2), and hence the congruence xp-1≡y0(mod p2), 0<x<p2, has exactly p-1 roots. In general, the congruence xp-1≡yi(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-1≡yi(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-1≡yi(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-1≡yi(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 ti 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;
An explanation for the probability distribution of the ui values, i≠0, is that the probability that a root of xp-1≡yi(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 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-1≡x1p-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;
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 greatest integer 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 either of these p. (It's unlikely that this can be proved rigorously.)
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+bp≡cp(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)p≡dp(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+bp≡cp(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+bp≡cp(mod p2), p does not divide abc, only if 1+(d-1)p≡dp(mod p2), 1<d<p, where d≡ca-1(mod p).
(A proof uses the lemma that if f and g are integers and p divides f-g, then p2 divides fp-gp.) Let ti (i=0, 1, 2, ..., (p-1)) be the number of numerically consecutive roots of the congruence xp-1≡yi(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+bp≡cp(mod p2), p does not divide abc, equals t0.
(A proof uses Euler's theorem that if f and m are relatively prime integers, 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 fp(p-1)≡1(mod p2), and hence the congruence xp-1≡y0(mod p2), 0<x<p2, has exactly p-1 roots. In general, the congruence xp-1≡yi(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-1≡yi(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-1≡yi(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-1≡yi(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 ti 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 | .6063530 | .606531 |
| ui=1 | 1742663 | .3038558 | .303265 |
| ui=2 | 0433319 | .0755547 | .075816 |
| ui=3 | 0071744 | .0125094 | .012636 |
| ui=4 | 0008949 | .0015603 | .001580 |
| ui=5 | 0000895 | .0001560 | .000158 |
| ui=6 | 0000058 | .0000101 | .000013 |
| ui=7 | 0000002 | .0000003 | .000001 |
| Total | 5735164 | .9999996 | 1.000000 |
An explanation for the probability distribution of the ui values, i≠0, is that the probability that a root of xp-1≡yi(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 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-1≡x1p-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 greatest integer 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 either of these p. (It's unlikely that this can be proved rigorously.)
