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.