# Linear diophantine equation

How to use Mathematica to solves any linear diophantine equation of the form ax+by=c, whenever it is solvable.

Such as this example, How to get the x = -165, y = 238. Thanks!

There is a whole set of solutions:

Solve[1027 x + 712 y == 1, {x, y}, Integers]

(*    {{x -> 547 + 712 * c1, y -> -789 - 1027 * c1}} for integer c1    *)


check if this is correct in general:

1027 x + 712 y /. {x -> 547 + 712*c1, y -> -789 - 1027*c1} // Expand
(*    1    *)


{x -> 547 + 712*c1, y -> -789 - 1027*c1} /. c1 -> -1
(*    {x -> -165, y -> 238}    *)


This happens to be the solution with smallest norm, which may be why you were looking for it:

Minimize[x^2 + y^2 /. {x -> 547 + 712*c1, y -> -789 - 1027*c1}, c1, Integers]
(*    {83869, {c1 -> -1}}    *)


Find this L2-norm-minimizing solution in one go:

Minimize[{x^2 + y^2, 1027 x + 712 y == 1}, {x, y}, Integers]
(*    {83869, {x -> -165, y -> 238}}    *)


Alternatively (thanks @DanielLichtblau) minimize the L1-norm and find the same solution (with the advantage of having an integer linear programming problem, for which there are excellent heuristic algorithms):

Minimize[{Abs[x] + Abs[y], 1027 x + 712 y == 1}, {x, y}, Integers]
(*    {403, {x -> -165, y -> 238}}    *)


more solutions:

Table[{x -> 547 + 712*c1, y -> -789 - 1027*c1}, {c1, -10, 10}]
(*    {{x -> -6573, y -> 9481},
{x -> -5861, y -> 8454},
{x -> -5149, y -> 7427},
{x -> -4437, y -> 6400},
{x -> -3725, y -> 5373},
{x -> -3013, y -> 4346},
{x -> -2301, y -> 3319},
{x -> -1589, y -> 2292},
{x -> -877, y -> 1265},
{x -> -165, y -> 238},
{x -> 547, y -> -789},
{x -> 1259, y -> -1816},
{x -> 1971, y -> -2843},
{x -> 2683, y -> -3870},
{x -> 3395, y -> -4897},
{x -> 4107, y -> -5924},
{x -> 4819, y -> -6951},
{x -> 5531, y -> -7978},
{x -> 6243, y -> -9005},
{x -> 6955, y -> -10032},
{x -> 7667, y -> -11059}}    *)

• The minimization can work as an ILP also: In[1201]:= Minimize[{a + b, {a >= x, a >= -x, b >= y, b >= -y, 1027*x + 712*y == 1}}, {a, b, x, y}, Integers] Out[1201]= {403, {a -> 165, b -> 238, x -> -165, y -> 238}} – Daniel Lichtblau Oct 25 '20 at 21:24