TransWikia.com

Linear diophantine equation

Mathematica Asked on July 23, 2021

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

One Answer

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

Correct answer by Roman on July 23, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP