Description of RESTA's Algorithm

Last update: 10th January 2000

How does this program work ?

Let's take the case of (6,2,5).
We need to solve the equation:

a6+b6=c6+d6+e6+f6+g6

For 6th power, we have the relations:

if a = 0 mod 2, then a6 = 0 mod 8
if a <> 0 mod 2, then a6 = 1 mod 8
if a = 0 mod 3, then a6 = 0 mod 9
if a <> 0 mod 3, then a6 = 1 mod 9
if a = 0 mod 7, then a6 = 0 mod 7
if a <> 0 mod 7, then a6 = 1 mod 7

These relations are very important.

Now, we can deduce some restrictions on a, b, c, d, e, f and g !

The first one is that a and b cannot be both multiple of 2, 3 or 7.
If a and b were both multiple of 2 for example, then c, d, e, f and g are necessarily multiple of 2, so all terms are multiple of 2 and the solution is not primitive.

We will try to find c and d that can be related to a and b.
Let's enumerate the conditions on a and b modulo 7.

1) if a6 = 0 mod 7 and b6 = 0 mod 7 then c6 = 0 mod 7, d6 = 0 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6= 0 mod 7, so all values are divisible by 7, SOLUTION NOT PRIMITIVE, so IMPOSSIBLE CASE !

2) if a6 = 0 mod 7 and b6 = 1 mod 7 then:
c6 = 0 mod 7 and d6= 1 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6 = 0 mod 7
or:
c6 = 1 mod 7 and d6= 0 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6 = 0 mod 7

3) if a6 = 1 mod 7 and b6 = 0 mod 7 then:
c6 = 0 mod 7 and d6= 1 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6 = 0 mod 7
or:
c6 = 1 mod 7 and d6= 0 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6 = 0 mod 7

4) if a6 = 1 mod 7 and b6 = 1 mod 7 then c6 = 1 mod 7 and d6 = 1 mod 7, e6 = 0 mod 7, f6 = 0 mod 7, g6= 0 mod 7

And we have now:

e6 = 0 mod 7, f6 = 0 mod 7, g6 = 0 mod 7
so:
a6+b6-c6-d6 divisible by 76

There is a wonderful trick that can be used there !!!
Suppose that we have a, b and c then we can deduce d because a6+b6-c6-d6 is divisible by 76
This is done by using a table of residues modulo 76 =117649.