# How to solve a system with GCD?

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

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

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

• Any ideas why this one works but not the initial one? – anderstood Mar 23 '18 at 21:14
• @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]]. – user64494 Mar 23 '18 at 21:26
• @user64494 If you have a better example, could you include it in the question? – Carl Woll Mar 23 '18 at 21:28
• @Carl Woll: Done. – user64494 Mar 23 '18 at 21:36
• @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. – user64494 Mar 23 '18 at 22:17