# Reduce and Solve fail to provide explicit integer solutions

Why is Reduce or Solve unable to provide explicit solutions over integers for such simple system of equations?

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, x4}, Integers]


Since x3=1/x1 in all four alternatives it is evident that x1=1 or x1=-1 and so we have four solutions:

(x1==1&&x2==2&&x3==1&&x4==3)||(x1==1&&x2==3&&x3==1&&x4==2)||(x1==-1&&x2==-3&&x3==-1&&x4==-2)||(x1==-1&&x2==-2&&x3==-1&&x4==-3)


On the other hand Reduce provides explicit solutions for this similar (but more complicated) system of equations:

Reduce[{5 x1^2+4 x1 x3+3 x3^2==4,5 x1 x2+2 x2 x3+2 x1 x4+3 x3 x4==1,5 x2^2+4 x2 x4+3 x4^2==3},{x1,x2,x3,x4},Integers]


(x1==-1&&x2==0&&x3==1&&x4==1)||(x1==1&&x2==0&&x3==-1&&x4==-1)

• This is a nonlinear Diophantine system. It's known there is no algorithm to determinate its solvability (see Wiki for info). MMA does its best. Dec 11, 2023 at 12:29
• Just to compare. The command of Maple 2023 isolve({x1*x3 = 1, 2*x2*x4 = 12, x1*x4 + x2*x3 = 5}) fails. Dec 11, 2023 at 15:47

What is even more strange that using Reduce twice (or Reduce with Solve) provides the explicit solutions:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3,
x4}, Integers] // Reduce
Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3,
x4}, Integers] // Solve


(x1 == -1 && x3 == -1 && x2 == -3 &&
x4 == -2) || (x1 == -1 && x3 == -1 && x2 == -2 &&
x4 == -3) || (x1 == 1 && x3 == 1 && x2 == 2 &&
x4 == 3) || (x1 == 1 && x3 == 1 && x2 == 3 && x4 == 2)

{{x1 -> -1, x2 -> -3, x3 -> -1, x4 -> -2}, {x1 -> -1,
x2 -> -2, x3 -> -1, x4 -> -3}, {x1 -> 1, x2 -> 2, x3 -> 1,
x4 -> 3}, {x1 -> 1, x2 -> 3, x3 -> 1, x4 -> 2}}


Even FullSimplify fails:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3,
x4}, Integers] // FullSimplify


Also works with some alternate variable orders. For instance:

Reduce[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12},
{x4, x1, x2, x3}, Integers]
(*
(x4 == -3 && x1 == -1 && x2 == -2 && x3 == -1) ||
(x4 == -2 && x1 == -1 && x2 == -3 && x3 == -1) ||
(x4 == 2 && x1 == 1 && x2 == 3 && x3 == 1) ||
(x4 == 3 && x1 == 1 && x2 == 2 && x3 == 1)
*)


It maybe should be reported to WRI, since better behavior seems possible.

• That's even stranger. (+1) Dec 11, 2023 at 15:21
• Actually I think the double-Reduce is stranger. Even in human, by-hand work, it can make a difference which variable you eliminate first. And it is documented that Reduce depends on the order of the variables, which is what made me think to try a different order. I still think Reduce should probably be able to do a better job here, and the double-Reduce supports that claim. Dec 11, 2023 at 18:17

Here is a partial workaround in 13.3.1 on Windows 10:

FindInstance[{x1 x3 == 1, x2 x3 + x1 x4 == 5, 2 x2 x4 == 12}, {x1, x2, x3, x4}, Integers, 5]


FindInstance::fwsol: Warning: FindInstance found only 4 instance(s), but it was not able to prove 5 instances do not exist. {{x1 -> -1, x2 -> -3, x3 -> -1, x4 -> -2}, {x1 -> -1, x2 -> -2, x3 -> -1, x4 -> -3}, {x1 -> 1, x2 -> 2, x3 -> 1, x4 -> 3}, {x1 -> 1, x2 -> 3, x3 -> 1, x4 -> 2}}