Linear Diophantine Equations [45B]

Contributed by Francis Glassborow

A Diophantine equation is one where one of the conditions for the solution is that the values are all integers. For example there are infinitely many 'solutions' to 2y + 3x = 7; pick any value you like for y and there will always be a value for x. However this is not true if you are limited to integers for both x and y. In this case there is still an infinite number of pairs, but there are not solutions for all values of y. For example There is no solution for y = 1. However y = 2 and x = 1 works fine.

To find out more about Diophantine equations go here.

There are several investigations that lead to suitable programming projects. Here are a couple:

• Given integer values of a, b and c find the smallest total for an all integer solution to ax + by + c = 0. Be careful because not all such equations have solutions
• Given the values for a, b, c, d, e, f, g, h, find the integer solution of:
  ax + by + cz +d = 0
  ex + fy + gx + h = 0
  with the smallest value of x.

If you read the material you will find by following the above provided link you will get ideas for very many more projects of varying difficulty.

Program elements

This is an example of a program where domain knowledge is very important. However as answers can also get exceptionally large you will probably also need to explore big integer types.