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!
Link: https://mathworld.wolfram.com/DiophantineEquation.html
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
Get help from others!
Recent Questions
Recent Answers
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP