Diophantine equation with constraints

115 Views Asked by At

Suppose that we have the following: $aX+bY+cZ=d$

where $X, Y, Z$ are positive integers and

$X+Y+Z \le g$

Does the condition to have $gcd(a,b,c)|d$ (to show a solution exists) still valid in this problem? How to know if we only have a unique solution?

2

There are 2 best solutions below

2
On

Let $e=\gcd(a,b,c)$ .

This means that $a=e\cdot a', b=e \cdot b',c=e \cdot c'$.

But $aX+bY+cZ=d$, so this means that $e\cdot(a'X+b'Y+c'Z)=d$. So $e$ must divide $d$.

1
On

No, even if $\gcd(a,b,c)\mid d$, a solution might not exist with the extra assumptions on $X,Y,Z$.

Take for example $$ 2X+2Y+2Z=2. $$ Clearly there is no solution to this that has all of $X,Y,Z$ strictly positive.

Or take $$ X+Y+Z=100 $$ and $g=5$. This also clearly has no solutions.

So $\gcd(a,b,c)\mid d$ is no longer a sufficient condition, though it is of course still necessary.

To determine whether there is a unique solution, I would parametrise the non-restricted problem using the usual method, and then analyse the result of that. When I have some time to think about it, I might try to find a general sufficient criterion.