2
$\begingroup$

For example,

Solve[{x + y == 150, GCD[x, y] == 30}, {x, y}, Integers]

Solve::nsmet: This system cannot be solved with the methods available to Solve.

The same issue with FindInstance.

Addition. A more difficult system is

{x+y+z==15000, GCD[GCD[x,y],GCD[y,z]]==5,x > 0, y > 0, z > 0}

Variables are assumed to be integer.

$\endgroup$
5
  • 1
    $\begingroup$ Not sure if it helps but you could use Bézout's identity: Solve[{x + y == 150, p*x + q*y == 30}, {x, y, p, q}, Integers]. $\endgroup$
    – anderstood
    Mar 23, 2018 at 20:53
  • $\begingroup$ @anderstood: Thank you for the idea. Here is my try: FindInstance[{x + y == 150, px + qy == 30, x >= 1, y >= 1, p >= 1, q >= 1}, {x, y, p, q}, Integers] outputs {} and FindInstance[{x + y == 150, px + qy == 30, x >= 1, y >= 1}, {x, y, p, q}, Integers] performs {{x -> 149, y -> 1, p -> 0, q -> 30}}. $\endgroup$
    – user64494
    Mar 23, 2018 at 21:08
  • $\begingroup$ @Bill: This is a toy example. Think of a big system with a lot of variables and something like GCD[x,GCD[y,z]]. $\endgroup$
    – user64494
    Mar 23, 2018 at 21:14
  • $\begingroup$ $p$ and $q$ could be negative, but the issue is to enforce that $p$ and $q$ are coprime. $\endgroup$
    – anderstood
    Mar 23, 2018 at 21:16
  • $\begingroup$ @anderstood Your method could deliver {x,y} "solutions" that have gcd a strict divisor of 30. $\endgroup$ Mar 23, 2018 at 21:44

1 Answer 1

3
$\begingroup$

Here is a variation that works:

{x, y} /. Solve[
    x+y==150 && x==30p && y==30q && 0<x<=y && GCD[p,q]==1,
    {x, y, p, q},
    Integers
]

{{30, 120}, {60, 90}}

Addendum

(For the more complicated example)

Since GCD[GCD[x,y], GCD[y,z]]==5 is equivalent to GCD[x,y,z]==5, your more complicated example could be done using:

FindInstance[
    {
    x+y+z==15000, x==5p, y==5q, z==5r, GCD[p,q,r]==1, 0<x<=y<=z
    },
    {x,y,z,p,q,r},
    Integers
]

{{x -> 5, y -> 5, z -> 14990, p -> 1, q -> 1, r -> 2998}}

A faster alternative that yields all (reverse) ordered solutions for this particular example is:

With[{parts = IntegerPartitions[3000, {3}]},
    5 Pick[parts, GCD @@@ parts, 1]
] //Short

{{14990,5,5},{14985,10,5},{14980,15,5},{14975,20,5},<<479993>>,{5010,5005,4985},{5005,5005,4990},{5005,5000,4995}}

$\endgroup$
5
  • $\begingroup$ Any ideas why this one works but not the initial one? $\endgroup$
    – anderstood
    Mar 23, 2018 at 21:14
  • $\begingroup$ @Carl Voll:+1. This is a toy example. Think of a big system with a lot of variables and something like GCD[x,GCD[y,z]]. $\endgroup$
    – user64494
    Mar 23, 2018 at 21:26
  • $\begingroup$ @user64494 If you have a better example, could you include it in the question? $\endgroup$
    – Carl Woll
    Mar 23, 2018 at 21:28
  • $\begingroup$ @Carl Woll: Done. $\endgroup$
    – user64494
    Mar 23, 2018 at 21:36
  • $\begingroup$ @Carl Woll: Many thanks from me to you. Your approach is a handwork which exploits concrete features of a system. I am interested in a more or less general method , say to solve {x+y+z==15000, GCD[x,y]+GCD[y,z]]==90,x > 0, y > 0, z > 0}. Brute force is of a little interest for me. $\endgroup$
    – user64494
    Mar 23, 2018 at 22:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.