# Algorithm for solving system of integer polynomial equations

I'm looking for an algorithm to solve a system of $n$ positive integer polynomial equations, assuming that there exists one and only one solution to the system.

Could anyone point me in the right direction or literature?

Example: Assume that the number of variables is $n$, usually we expect $10 \le n \le 50$. Assume that $n=5$ for the example. We need to solve: $$x_1 = 5$$ $$x_1^2 x_2 x_3 = 100$$ $$x_2^2 x_3 + x_1 + x_4^2 = 62$$ $$x_5 x_4 + 2 x_5 = 9$$ $$x_1 + x_5 x_2 + x_3 x_4 = 21$$ $$x_1 + x_2 + x_3 + x_4 + x_5 = 17$$ Solution: From $x_1 = 5$ we get that $x_2 x_3 = 4$, thus $(x_2,x_3)=(1,4),(2,2),(4,1)$. From the third equation $x_5(x_4 + 2) = 9$, thus $(x_4, x_5) = (1, 3), (7, 1)$. From the last equation we have that $x_2 + x_3 + x_4 + x_5 = 12$, since the sum of $x_2 + x_3 = 4, 5$ and $x_4 + x_5 = 4, 8$, it means only option is $x_4 = 7, x_5 = 1, x_2 = 2, x_3 = 2$.

Note that I need an algorithm to do this , such that it is automated.

• If you do not show the system of equations - how to solve it? – individ Aug 26 '16 at 16:05
• I'm looking for a general algorithm to solve any such system. I don't have any concrete system, I can make one up, but the goal is to have a general algorithm for solving it (e.g. like for instance the Greatest Common Divider algorithm, or Gaussian Elimination) – Alex Botev Aug 26 '16 at 16:18
• For systems of linear equations - standard method of Gauss. For quadratic and slightly higher extent have to wait until about it will tell. While about it to speak. Some systems can be found there. artofproblemsolving.com/community/… It is better to write the system - could work to solve it. – individ Aug 26 '16 at 16:32
• What degrees? How many variables? You should consider posting a minimal example for a small $n$ at least. – dxiv Aug 26 '16 at 16:47
• In general, deciding whether a solution to a system of polynomial equations exists is undecidable (this was Hilbert's tenth problem). This implies that any algorithm giving a solution to a system of equations guaranteed to have a root has time complexity growing faster than any computable function. I'd suspect the situation is no better for systems with a unique solution, but I can't tell. – Milo Brandt Aug 26 '16 at 21:12

If (and it's a big if) some variable has degree $1$ in one of the polynomials, you can substitute for that variable, obtaining a smaller set of equations in fewer variables, but in general with higher degrees.
Somewhat more generally, you can take a Groebner basis of your system of polynomials. In the example, I took a grevlex basis (using Maple's Groebner package) and obtained $[1]$, indicating that the system is inconsistent. With $20$ replaced by $21$ in the fifth equation, the grevlex basis was $[-1+x_5, x_4-7, -2+x_3, -2+x_2, x_1-5]$, from which you can read off the solution.