0
$\begingroup$

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!

enter image description here

Link: https://mathworld.wolfram.com/DiophantineEquation.html

$\endgroup$
5
$\begingroup$

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    *)

your specific solution:

{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}}    *)
$\endgroup$
1
  • 2
    $\begingroup$ 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}} $\endgroup$ – Daniel Lichtblau Oct 25 '20 at 21:24

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.