# Solvability conditions for linear system of diophantine equations

Let $Ax=B$ be a system of linear diophantine equations, where $A$ is a full rank $n \times 2n$-matrix with integer entries. In the case $n=1$ we have solutions parameterized by $\mathbb{Z}$ iff $gcd(a_{11},a_{12})$ divides $b_{11}$. Is there a similar statement for arbitrary $n$ of the form "We get solutions paramterized by $\mathbb{Z}^n$ iff condition on $B$"

EDIT: Since I know basically nothing about diophantine equations, it could be that this question is far from being research level.. if so, just tell me and I will delete it and bring it up in math SE

• Integer values = integer entries, I assume... – Igor Rivin Sep 13 '16 at 21:00
• yup, sorry, 1:1 german translation ;) – Bipolar Minds Sep 13 '16 at 21:02
• The answer you're looking for is probably the one given by Noam Elkies in this thread: mathoverflow.net/questions/208147/… – RP_ Sep 13 '16 at 21:03
• hm, I was hoping for something more concrete, like a general condition on B in terms of gcd's of the entries of $A$.. but I think you're right, thx – Bipolar Minds Sep 13 '16 at 21:12
• @BipolarMinds if you wish to reply to a comment and have that person be notified that there is some kind of response, you need to start with an at sign @ and then, at least, the first three letters of that username. Usually, if you type that much, it will allow you to click on a complete version of that username, which is what i did here... – Will Jagy Sep 13 '16 at 21:47

Let $X$ be the set of all $n\times n$ minors of $A$, and let $Y$ be the set of all $n\times n$ minors of $(A\,| B)$. Then the equivalent condition is that $\gcd(X)=\gcd(Y)$. Indeed, this condition is equivalent if the system is in the Smith form, and moreover it is preserved by $SL(n,\mathbb Z)$-transforms.
• as a neat aside: If (as in my case) $A$ is the concatenation of two upper triangular matrices, then $|X|=C_n$ is the $n$th Catalan number – Bipolar Minds Sep 13 '16 at 22:28
• @ilyabogbanov if $0\in X$ and $0\in Y$ then does $gcd(X)=gcd(Y)$ hold and what if $0\in X$ and $0\notin Y$ and $gcd(X\backslash\{0\})=gcd(Y)$ holds? – T.... Mar 14 '17 at 23:45