Integer Solutions

Q: Is there a simple way to compute the solutions to for , , for a specified , ?

A: Adam Strzebonski (adams@wolfram.com) answers: In Version 5, you can use Reduce, though it requires changing the value of a system option. By default, Reduce writes out integer solutions of explicitly if the number of integers in is less than 11.

Otherwise, the solutions are represented as .

Here is the general parametric solution to the given problem with .

Changing the value of a Reduce system option yields explicit solutions.

Here are all the solutions to the given problem with .

Although this approach is simplest in that it requires just a single command and no manual preprocessing of the input, it is not very efficient. Reduce has no special methods for solving equations and inequalities over the primes, other than by generating primes in a given finite interval. If we give the problem to Reduce directly, it uses a general method for solving systems of equations and inequalities over the integers, and then removes the numeric solutions that are not prime. Changing the system options causes to be represented as 249 explicit values, from which we get 249 integer solutions for and and only then does it remove those that are not prime.

A more efficient way of solving this particular problem is to make Reduce generate only prime values for , and then select those for which is prime.

Here is a comparison of the two methods.