2
$\begingroup$

Given the linear Diophantine equation:

$ a_1 x_1 + a_2 x_2 + ... + a_n x_n = b$

and its particular solution $(x_1^*, x_2^*, ..., x_n^*)$.

How to write down all the solutions of this equation?

$\endgroup$

closed as off-topic by Emil Jeřábek, RP_, Franz Lemmermeyer, Chris Godsil, Sebastian Goette Mar 17 '17 at 22:46

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, RP_, Franz Lemmermeyer, Chris Godsil, Sebastian Goette
If this question can be reworded to fit the rules in the help center, please edit the question.

2
$\begingroup$

First, complete the vector $(a_1, \dotsc, a_n)$ to a matrix $A$ with determinant $1.$ Then the solutions (of the homogeneous system) are all integer linear combinations of the second through $n$ columns of $A^{-1}.$ That you can complete the vector with gcd 1 to a unimodular matrix is basic to geometry of numbers, and can be proved fairly easily by induction (or see Morris Newman's book on "Integral Matrices", Thm II.1).

$\endgroup$
  • $\begingroup$ OK, but i wonder if there exists the way to find inverse of unimodular matrix without using rationals (without divisions) in O(P(n)) where P is some polynom? $\endgroup$ – Ilya Muradyan Mar 18 '17 at 10:34
  • $\begingroup$ @ИльяМурадьян There is a difference between not using divisions and not using rationals. In the proof of the result I quote you divide a set of numbers by their gcd (which leads to no rationals). I don't think you can avoid divisions, but you can certainly do all the necessary computations with integers. $\endgroup$ – Igor Rivin Mar 18 '17 at 13:31
  • $\begingroup$ ok, I've built an example. Let a = (3, 5, 7). Then A = (3 5 7 | 1 2 0 | -3 -5 -6) and A^(-1) = (-12 -5 -14 | 6 3 7 | 1 0 1). You say that x = k(6 3 7) + l(1 0 1) should be solution of an equation 3x1 + 5x2 + 7x3 = 0 for any integer k and l, but it isn't so. Where is my mistake? $\endgroup$ – Ilya Muradyan Mar 18 '17 at 14:54
  • $\begingroup$ @ИльяМурадьян My typo - by "rows" I meant "columns". Fixed now. $\endgroup$ – Igor Rivin Mar 18 '17 at 15:10

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