## Monday, August 31, 2015

### Fermat versus Fermat

Fermat Versus Fermat
The Theorem versus the Primes
A math essay by Nathaniel Hellerstein
City College of San Francisco

Consider Fermat’s Last Theorem:
AN + BN   =   CN
has no positive integer solutions if N>2.
This theorem has finally been proven by Andrew Wiles.
But consider these equations:
13 + 23  =  1 + 8  =  9  = 4 (mod 5)
43  =  64  =  4 (mod 5)
So     13 + 23  =  43  (mod 5)   ;  a modular exception to Fermat’s Last Theorem! Call such an exception a Fermat Triple.
There are many Fermat triples; for modulo 5, the cubing function is 1-to-1 and onto:
X  mod 5             0       1       2       3       4
X3 mod 5             0       1       3       2       4
Therefore cubing is invertible, mod 5. In fact it is its own inverse:
(X3)3   =   X  mod 5
Let (x1/3) be the cube root of x, mod 5; and define the ‘cube root of addition, mod 5’, by conjugating addition by the cube root, as follows:
x +1/3 y     =    (x3 + y3)1/3   (mod 5)
x +1/3 y  =  z       if and only if      x3+y3  =  z3 .
The cube root of addition is a Fermat-triple addition; it solves  a3+b3 = c3 for any a and b.  Thus mod 5 maximally violates Fermat’s Last Theorem for cubes.
+1/3    0   1   2   3   4

0        0   1   2   3   4               A Fermat-triple addition
1        1   3   4   2   0
2        2   4   1   0   3
3        3   2   0   4   1
4        4   0   3   1   2

The cube root of addition is commutative, associative, has identity 0, inverse –x, and multiplication distributes over it:
x*(y +1/3 z)  =  x*(y3+z3)1/3   =  (x3*(y3+z3))1/3 = ((xy)3+(xz)3)1/3 =  (xy) +1/3 (xz)
So the cube root of addition fits the field axioms. Mod 5 has not just an exception to Fermat’s Last Theorem: it has an entire arithmetical system against it!
Better yet: modulo 5, any odd power equals identity or cube:
x  =  x5  = x9  = …
x3 = x7 = x11 = …
So any odd power is invertible, mod 5; therefore there are Nth roots of addition, mod 5, for any odd N:
x +1/N y     =    (xN + yN)1/N   (mod 5)
x +1/N y  =  z       if and only if      xN+yN  =  zN .
+1/N also fits the field axioms including distribution. So mod 5 has a field of exceptions to Fermat’s Last Theorem for any odd power.
There are Fermat-triples for any odd power not just mod 5, but for any modulus in which all odd powers are 1-to-1 and onto. Which moduli are these? The Fermat primes; 2(2^n)+1.

Theorem: For any Fermat prime F, the integers mod F have one-to-one odd-power functions.
Proof:
The integers mod F (a.k.a. ZF) is a field since F is a prime; so its multiplicative group (minus zero) is isomorphic to the cyclic addition group in ZF-1 = Z2^(2^n). Odd powers xN in ZF correspond to odd multiples Nx in Z2^(2^n); if N is odd then it is relatively prime to 2^(2^n), therefore it has a multiplicative inverse: an n such that nN = 1 mod 2^(2^n). Na=Nb implies nNa=nNb implies a=b; so Nx is one-to-one. N(na)=a; so Nx is onto. For odd N, the function Nx is one-to-one onto in Z2^(2^n); therefore xN is one-to-one onto in ZF. QED.

The integers modulo any Fermat prime have one-to-one onto odd power functions; therefore they also have all odd roots of addition. Fermat primes maximally violate Fermat’s last theorem; thus this article’s title!
The five known Fermat primes are:
3,   5,   17,   257,   65537
By Fermat’s Little Theorem, x3 = x mod 3; so xodd = x mod 3. All odd powers are the identity mod 3, so any addition mod 3 is a Fermat triple for all odd powers.
We have seen odd roots of addition mod 5, above. They are either + or +1/3. Each is a cube root of each other; (+1/3)1/3 = +, because x9=x mod 5. So Z5’s additions have a cube-root symmetry.

Now for mod 17. Consider these tables:
X    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
X3   0  1  8 10 13  6 12  3  2 15 14  5 11  4  7  9 16
X5   0  1 15  5  4 14  7 11  9  8  6 10  3 13 12  2 16
X7   0  1  9 11 13 10 14 12 15  2  5  3  7  4  6  8 16

From these we can derive Z17  root-addition tables.

+1/3  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16

0    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
1    1  8 15 12 10 14  4 13  7 16  9  5  6 11  2  3  0
2    2 15 16  1 13 10  7 12  3  5 11  4  8  6  9  0 14
3    3 12  1  7  6 16 11  4  6  2 14  9 13 10  0  8 15
4    4 10 13  6 15  8  2 16  9 12  3  1 14  0  7 11  6
5    5 14 10 16  8  6  1 15  2 13  7 12  0  3  4  9 11
6    6  4  7 11  2  1 14  9 10  3 15  0  5 16  8 13 12
7    7 13 12  4 16 15  9  5 11  1  0  8 10 14  3  6  8
8    8  7  3  6  9  2 10 11 13  0 16  2  4  5 15 12  1
9    9 16  5  2 12 13  3  1  0  4  6  7 15  8 11 14 10
10   10 9 11 14  3  7 15  0 16  6 12  8  2  1 13  5  4
11   11 5  4  9  1 12  0  8  2  7  8  3 16 15  6 10 13
12   12 6  8 13 14  0  5 10  4 15  2 16 11  9  1  7  3
13   13 11 6 10  0  3 16 14  5  8  1 15  9  2 12  4  7
14   14 2  9  0  7  4  8  3 15 11 13  6  1 12 10 16  5
15   15 3  0  8 11  9 13  6 12 14  5 19  7  4 16  1  2
16   16 0 14 15  6 11 12  8  1 10  4 13  3  7  5  2  9

+1/5  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
0    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
1    1 15 16 10  3  2  9 14 11  8  6  7  4  5 13 12  0
2    2 16 13 12 15 13  3  8  6 10  4  9  1  7 11  0  5
3    3 10 12 11  8 15 14 16  5 13  7  2  9  1  0  6  4
4    4  3 15  8  9  1  7  2 13 14 11  5  6  0 16 10 12
5    5  2 13 15  1  7  4  9 10  3 12  6  0 11  8 16 13
6    6  9  3 14  7  4  5  1 16  2 13  0 11 12 15  8 10
7    7 14  8 16  2  9  1  3 12 15  0  4  5  6 10 13 11
8    8 11  6  5 13 10 16 12  1  0  2 15 14  3  4  7  9
9    9  8 10 13 14  3  2 15  0 16  5  1  7  4 12 11  6
10   10 6  4  7 11 12 13  0  2  5 14 16  8 15  1  9  3
11   11 7  9  2  5  6  0  4 15  1 16 12 13 10  3 14  8
12   12 4  1  9  6  0 11  5 14  7  8 13 10 16  2  3 15
13   13 5  7  1  0 11 12  6  3  4 15 10 16  8  9  2 14
14   14 13 11 0 16  8 15 10  4 12  1  3  2  9  6  5  7
15   15 12 0  6 10 16  8 13  7 11  9 14  3  2  5  4  1
16   16 0  5  4 12 13 10 11  9  6  3  8 15 14  7  1  2

+1/7  0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
0    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
1    1  9  5  7  6  3  8  4 16 11 14 13 15 10 12  2  0
2    2  5  1 11 10  9 14 13 12  3  6  7 16  4  8  0 15
3    3  7 11 10 12 13 15 14  2  4 16  6  1  8  0  9  5
4    4  6 10 12  2 14  5 15  3  8  1 16 11  0  9 13  7
5    5  3  9 13 14 11 12 10 15  7  8  4  0  6 16  1  2
6    6  8 14 15  5 12  3  2  7 16  9  0 13  1 11 10  4
7    7  4 13 14 15 10  2 12  5  6  0  8  9 16  1 11  3
8    8 16 12  2  3 15  7  5  4  0 11  1 10  9 13 14  6
9    9 11  3  4  8  7 16  6  0 13 12 10  2 14 15  5  1
10   10 4  6 16  1  8  9  0 11 12  5 15  7  2  3  4 13
11   11 13 7  6 16  4  0  8  1 10 15 14  5 12  2  3  9
12   12 15 16 1 11  0 13  9 10  2  7  5  6  3  4  8 14
13   13 10 4  8  0  6  1 16  9 14  2 12  3 15  5  7 11
14   14 12 8  0  9 16 11  1 13 15  3  2  4  5  7  6 10
15   15 2  0  9 13  1 10 11 14  5  4  3  8  7  6 16 12
16   16 0 15  5  7  2  4  3  6  1 13  9 14 11 10 12  8

I leave computing tables for +1/9, +1/11, +1/13, and +1/15, mod 17, as an exercise for the ambitious student.

What of even powers?

X    0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
X2   0  1  4  9 16  8  2 15 13 13 15  2  8 16  9  4  1
X4   0  1 16 13  1 13  4  4 16 16  4  4 13  1 13 16  1
X8   0  1  1 16  1 16 16 16  1  1 16 16 16  1 16  1  1
X16   0  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1  1

There are many sums among the squares table:
1+1=2; that is, (1 or 16)2 + (1 or 16)2  =  (6 or 11)2
1+8=9; that is, (1 or 16)2 + (5 or 12)2  =  (3 or 14)2
1+15=16; that is, (1 or 16)2 + (7 or 10)2  =  (4 or 13)2
1+16=0; that is, (1 or 16)2 + (4 or 13)2  =   02
2+2=4; that is, (6 or 11)2 + (6 or 11)2  =   (2 or 15)2
2+13=15; that is, (6 or 11)2 + (8 or 9)2  =  (7 or 10)2
2+15=0; that is, (6 or 11)2 + (7 or 10)2  =   02
2+16=1; that is, (6 or 11)2 + (4 or 13)2  =  (1 or 16)2
4+4=8; that is, (2 or 15)2 + (2 or 15)2  =  (5 or 12)2
4+9=13; that is, (2 or 15)2 + (3 or 14)2  =  (8 or 9)2
4+13=0; that is, (2 or 15)2 + (8 or 9)2  =    02
4+15=2; that is, (2 or 15)2 + (7 or 10)2  =  (6 or 11)2
8+8=16; that is, (5 or 12)2 + (5 or 12)2  =  (4 or 13)2
9+16=8; that is, (3 or 14)2 + (4 or 13)2  =  (5 or 12)2
9+8=0; that is, (3 or 14)2 + (5 or 12)2  =    02
9+9=1; that is, (3 or 14)2 + (3 or 14)2  =  (1 or 16)2
13+13=9; that is, (8 or 9)2 + (8 or 9)2  =  (3 or 14)2
15+15=13; that is, (7 or 10)2 + (7 or 10)2  =  (8 or 9)2
16+16=15; that is, (4 or 13)2 + (4 or 13)2  =  (7 or 10)2

Some of these (maybe all) are the classic Pythagorean triples:
(m2 – n2)2 + (2mn)2  =  (m2 + n2)2
m=2, n=1  yields the triple 32+42=52 ;
m=3, n=2  yields the triple 52+122=132 ;
m=3, n=1  yields the triple 82+62=102 ;
m=4, n=1  yields the triple 152+82=02 ;
m=4, n=2  yields the triple 122+162=32 ;
m=5, n=4  yields the triple 92+62=72 ;
and so on.

ZF supports higher Pythagorean triples; for if N is odd then:
(m2 +1/N (-n2))2N  +  (21/N mn)2N  =  (m2 +1/N n2)2N
Proof: Left side = (m2 +1/N (-n2))2N  +  (21/N mn)2N
= (m2N + (-n2N))2  +  (2 mNnN)2
= (m2N - n2N)2  +  (2 mNnN)2           if N is odd
= m4N – 2m2Nn2N+ n4N +  4 m2Nn2N
= m4N + 2m2Nn2N+ n4N
=   (m2N + n2N)2
=  (m2 +1/N n2)2N =       right side

21/3 = 8 and 21/5 = 15, mod 17; therefore:
(m2 +1/3 (-n2))6  +  (8 mn)6   =   (m2 +1/3 n2)6
(m2 +1/5 (-n2))10  +  (15 mn)10   =  (m2 +1/5 n2)10
so      m=2, n=1  yields          66 + 166   =   106
and             1210 + 1310 = 310
m=3, n=1  yields          106 + 76   =   166
and             610 + 1110 = 810
m=3, n=2  yields          86  +  146   =   126
and             410 + 510 = 1410

You can derive higher Pythagorean triples by applying odd roots to Pythagorean triples. For instance, 22+72=62, and 2=83=155, and 7= 143=65, and 6=53=105; therefore 86+146=56, and 1510+610=1010 .

There are sums amongst the 4th and 8th powers:
1+16=0; that is,
(1 or 4 or 13 or 15)4 + (2 or 8 or 9 or 15)4  =  04
13+4=0; that is,
(3 or 5 or 12 or 14)4 + (6 or 7 or 10 or 11)4  =  04
1+16=0; that is,
(1,2,4,8,9,13,15,16)8+(3,5,6,7,10,11,12,14)8  =  08
But all 16th powers are 1 or 0, so the only possible sums amongst the 16th powers are trivial: 0+B=B.

The higher binary powers involve 2kth roots of -1:
If r(2^k) = -1 mod F, then
(a)(2^k) + (ra)(2^k)  =  0(2^k)
And more generally
(a*(rodd))(2^k) + (a*(reven))(2^k)  =  0(2^k)
So since 24 = -1 mod 17, and 38 = -1 mod 17:
(a*(2odd))4 + (a*(2even))4  =  04
(a*(3odd))8 + (a*(3even))8  =  08
These ‘hypercomplex’ triples include
14+24 = 24+44 = 34+64 =44+84 = 54+104 =64+124 =74+144 = 04
18+38 = 28+68 = 38+98 =48+128 = 58+158 =68+18 = 08
Since (-1)odd = -1, hypercomplex triples for power 2k are also triples for power odd*2k. For instance, 4th roots of -1 are also 12th roots; therefore  112+212 = 212+412 = 312+612 =412+812 = 512+1012 =612+1212 =712+1412 = 012

Conjecture: modulo a Fermat prime F, the Fermat triples are:
For any power N: the trivial case
0N + BN  =  BN
For odd power N: odd roots of addition:
AN  +  BN    =    ( A  +1/N  B )N
For power 2: the Pythagorean triples:
(m2 - n2)2  +  (2 mn)2  =  (m2 + n2)2
For power Odd*2: the higher Pythagorean triples:
(m2 +1/N (-n2))2N  +  (21/N mn)2N  =  (m2 +1/N n2)2N
For power Odd*2k: hypercomplex triples:
If r(2^k) = -1 mod F, then
(a)(2^k) + (ra)(2^k)  =  0(2^k)
And more generally
(a*(rodd))(Odd*2^k) + (a*(reven))(Odd*2^k)  =  0(Odd*2^k)

This seems to apply to mod 3, 5 and 17, but I haven’t checked mod 257, let alone mod 65537. I leave investigating Fermat triples in those moduli to the ambitious student. For instance, do they have fourth powers that add to a fourth power that isn’t zero? Or 8th powers and up?

I end with a Speculation: that there are only finitely many Fermat primes. My guess is that if there were infinitely many Fermat prime moduli, then they would tend towards something resembling the rational numbers; but all odd roots of addition are defined in the Fermat prime moduli, though not in the rationals.