How would one go about solving the system of five equations:






over the integers? I have no immediate way of answering this question, since it looks to be solved by some "trick." Inequalities may help, although it says "over the INTEGERS" and most inequalities only deal with positive reals.

EDIT: I dont see how congruence's can work, as that may limit the number of solutions, but only to a certain congruence class. For example, we may find that p=1 mod 3, say, but this will only give us an infinite number of p's to check. Unless, of course, we get a congruence contradiction, in which case there would be no solution, but the solution $(3,2,1,5,4)$ works-noted below. (sorry my computer is acting up and wont let me comment)

  • $\begingroup$ How about some congruence tricks? Do we know at least one solution to this equation? $\endgroup$ – Srivatsan Sep 7 '11 at 0:23
  • 1
    $\begingroup$ The congruence checks will eliminate many possibilities. With these equations, the values can't be too large as the quadratics will be too dominant. So if you can get down to a few equivalence classes, you can do a search. $\endgroup$ – Ross Millikan Sep 7 '11 at 2:05
  • 1
    $\begingroup$ I would like to stir up some more discussion of this problem, as I dont think it should be that hard (granted I have not solved it), and it seems interesting enough. Consider each equation as a quadratic in its respective variable. It seems we can utilize some inequalities in this way, noting that the discriminant is greater than zero. We may also notice that the sum of all the right hand side must be greater than zero. I firmly believe there must be a rigorous and non-handwavy way to solve this problem as Andy suggested, and I know that there is someone on this forum who can solve this :) $\endgroup$ – user15699 Sep 7 '11 at 23:08
  • $\begingroup$ @Sravan: I have converted your answer to a comment. Answers should be reserved for posts that answer the question. But because you do not have 50 reputation points yet, you can only comment on your own questions and answers. So, the "add comment" button will only appear for you once you gain 50 points. $\endgroup$ – Zev Chonoles Sep 7 '11 at 23:29

Not a direct answer but too big for a comment: Rewrite your question as $$ \begin{pmatrix} p-1 &-1&2&-2&-1&8\\ 1&q+2&1&-2&-2&6\\ -3&-2&r-1&-2&-2&31\\ -2&-1&-1&s-2&-2&2\\ -1&-2&-3&-2&t-1&8 \end{pmatrix} \begin{pmatrix} p\\q\\r\\s\\t\\1 \end{pmatrix} = 0 $$ I would go for the nullspace of this matrix which is not simplifying much but maybe allow for a cleaner search. For example, $s$ and $t$ columns look suspicious :).

EDIT: A small Matlab routine gave a solution as $\begin{pmatrix}p &q &r &s &t\end{pmatrix} = \begin{pmatrix}3 &2 &1 &5 &4\end{pmatrix}$

EDIT2 : I forgot to write that I have massaged the problem a bit by applying some row manipulations from the left which is the only detail that I wanted to stress but I wrote anything but that.

  • 1
    $\begingroup$ I obtained the same solution in Mathematica: Reduce[Thread[{{1, 1, -2, 2, 1}, {-1, -2, -1, 2, 2}, {3, 2, 1, 2, 2}, {2, 1, 1, 2, 2}, {1, 2, 3, 2, 1}} . {p, q, r, s, t} - {8, 6, 31, 2, 8} == {p, q, r, s, t}^2], {p, q, r, s, t}, Integers] $\endgroup$ – J. M. isn't a mathematician Sep 7 '11 at 2:22
  • $\begingroup$ @J.M. : I wish I knew Mathematica better. Now I am wondering if there is any chance that the null space computation without the vector structure given in my answer would lead to the congruence relations that were discussed above. In other words, suppose we are only given with the matrix above. And we solve for an arbitrary nullspace vector restricted to integer valued entries? Would that give us more than one answer? I couldn't make sure. It feels like it should. $\endgroup$ – user13838 Sep 7 '11 at 10:08
  • $\begingroup$ I haven't tried. Unfortunately, I am not at the machine with Mathematica right now, so I can't experiment. Sorry. $\endgroup$ – J. M. isn't a mathematician Sep 7 '11 at 10:11
  • $\begingroup$ @J.M. : No problem at all. $\endgroup$ – user13838 Sep 7 '11 at 13:00

If you add all your equations you get

By completing the square you can rewrite this as

Obviously, the only solution is $p=3$, $q=2$, $r=1$, $s=5$, $t=4$.


A start: I would start by trying to find combinations which simplify things and work modulo small primes. The first equation tells us that $q$ and $t$ are both even or both odd. The second says $p$ and $r$ are likewise the same parity, and the third says $p$ is odd. Deleted: an assertion based on $s^2-q^2$ which had an algebra error.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.