All sixth powers are either a multiple of 13 or one away from a multiple of 13:

1 = 13x0 +1

64 = 13x5 -1

729 = 13x56 +1

4096 = 13x315 +1

5^6 = 13x1202 -1

6^6 = 13x3589 -1

7^6 = 13x9050 -1

8^6 = 13x20265 -1

etc.

To check that it works for ALL sixth powers, you only need to check the first 13, since:

(n+m)^a = (n)^a (mod m)

Proof: if you multiply out the left-hand side, one term will be (n)^a, plus several other terms which will all contain m, and therefore be a multiple of m, and not affect its value, modulo m.

In actual fact you only have to look at the first 6, since

(m-n)^a = (-n)^a (mod m), for precisely the same reason.

To be sure that there are no numbers higher than 13 that work, you only need to look at the first couple of sixth powers (and the numbers either side of them) and see what their factors are.

The only numbers that divide into (63, 64, OR 65) AND (728, 729 OR 730) are 1,2,3,4,5,7,8,9,13.

13 is the highest of this list, so as long as it proves to be a valid solution, it will be the highest such solution.