Skip to main content
2 of 2
added tags
Pete L. Clark
  • 65.4k
  • 12
  • 241
  • 381

Positive solutions of linear Diophantine equations

Let $A$ be a non-negative integer $k\times n$-matrix (i.e. each entry is non-negative and integer) with $rank(A) = k < n$. Let $b$ be a $k$-dimensional vector with positive integer entries. Consider a system of linear Diophantine equations $Ax = b$ and suppose that there exists an integer solution of these system. I'm interested in the following question. Are there conditions on $b$ that would guarantee the existence of a non-negative integer solution of $Ax = b$? Is it enough to take each entry of $b$ sufficiently large?

I suppose the answer to this question has been known for a long time. Unfortunately, I'm not an expert in this area so I would be thankful for any help or references.

SIB
  • 351
  • 3
  • 10