I just recently learned about "Frobenius Numbers" from watching Numberphile on youtube (http://www.youtube.com/watch?v=vNTSugyS038) and they look strikingly like Diophantine equations in some sense... But what seems off is that every Diophantine equation I've seen thus far doesn't have an integer solution for every value past some other value.. The example they use is using various discrete combinations of packages of chicken nuggets, it is impossible to order some combinations of nuggets less than some $x$ (of which I forget off the top of my head), and that every value greater than $x$ can be obtained through some linear combination of the available bunches.
For example, in another video from Arsdigita, it is argued that $7x+11y=z$ has positive integer solutions $(x,y)$ for every $z\geq 61$.
One thing I learned is that $ax+by=z$ has a solution if and only if $(a,b)\mid z$. So is the link here that $(a,b)=1$? How does one determine starting at which value of $z$ that positive solutions can always be found?