I came across a question which asked how sorting would help in searching for counterexamples to the conjecture that $$u^6 + v^6 + w^6 + x^6 + y^6 = z^6$$ has no non trivial solutions in integers.

The answer said to make two files containing values of $u^6 + v^6 + w^6 \pmod W$ and $z^6 - y^6 - x^6 \pmod W$. $W$ is the word size of the computer. Sort these, search for duplicates and go for further steps.

Can someone explain what these further steps would be in detail ?

  • 2
    $\begingroup$ What are your thoughts on the matter? Have you tried completing this algorithm? $\endgroup$ – Yuval Filmus Jun 26 '16 at 15:46

You want to find solutions to $u^6 + v^6 + w^6 = z^6 - x^6 - y^6$. Obviously any solution would also have to be a solution modulo k, for every k. So the idea is to find the set of all possible values of $u^6 + v^6 + w^6$ modulo W, and the set of all possible values of $z^6 - x^6 - y^6$, and you need to find the elements that are common to both sets.

Question: What is the easiest way to check which elements two sets have in common? Answer: Sort the elements, that makes the search very easy.

The further steps: If you are lucky then both sets had few elements in common. So you can deduce values of u, v, w, x, y, z modulo W or modulo some other value. Which means you have reduced the search space. If there was a good amount of reduction, try different values instead of W. And at some point you start with an exhaustive search, but with fewer values needing to be searched.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.