How to solve a system with GCD?

Question

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.

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]. — anderstood, Mar 23 '18 at 20:53
@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}}. — user64494, Mar 23 '18 at 21:08
@Bill: This is a toy example. Think of a big system with a lot of variables and something like GCD[x,GCD[y,z]]. — user64494, Mar 23 '18 at 21:14
$p$ and $q$ could be negative, but the issue is to enforce that $p$ and $q$ are coprime. — anderstood, Mar 23 '18 at 21:16
@anderstood Your method could deliver {x,y} "solutions" that have gcd a strict divisor of 30. — Daniel Lichtblau, Mar 23 '18 at 21:44

Carl Woll · Accepted Answer · 2018-03-23 22:05:26Z

3

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

answered Mar 23 '18 at 21:12

Carl Woll

111k5 gold badges177 silver badges294 bronze badges

$\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

add a comment |

1 Answer 1