1
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

You are correct in thinking that the equation $ax + by = z$ can only have integer solutions for all sufficiently large $z$ if $(a,b) = 1$. However, if $(a,b) = 1$, You can in fact always find a $z_0$ such that, for all $z\ge z_0$, the equation has a solution. There is even a simple closed form for this: $z_0 = (a-1)(b-1)$.

This can be proved by noting that, if we allow $x$ and $y$ to be negative, than any $z$ may be written in the form $ax + by$, in many different ways. This is still possible, in fact, if we restrict $x$ to be in the range $0\le x < b$. In that case, there is always a unique choice of values for $x$ and $y$ (this can be shown using modular arithmetic). So, to find the largest number that we can't represent with $x$ and $y$ positive, we let $x = b-1$ (the largest possible value less than $b$)and $y = -1$ (the largest possible negative value), and get $z = a(b-1) + -b = ab - a - b$, so all integers greater than $z_0 = ab-a-b+1 = (a-1)(b-1)$ are representable as $ax + by$ with $x,y >0$.

$\endgroup$

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.