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$
  • 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 '18 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 '18 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 '18 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 '18 at 21:16
  • $\begingroup$ @anderstood Your method could deliver {x,y} "solutions" that have gcd a strict divisor of 30. $\endgroup$ – Daniel Lichtblau Mar 23 '18 at 21:44
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$
  • $\begingroup$ Any ideas why this one works but not the initial one? $\endgroup$ – anderstood Mar 23 '18 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 '18 at 21:26
  • $\begingroup$ @user64494 If you have a better example, could you include it in the question? $\endgroup$ – Carl Woll Mar 23 '18 at 21:28
  • $\begingroup$ @Carl Woll: Done. $\endgroup$ – user64494 Mar 23 '18 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 '18 at 22:17

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.