Possible Duplicate:
Largest integer that can’t be represented as a non-negative linear combination of $m, n = mn - m - n$? Why?

Q: Suppose $u$ and $v$ are positive integers, and $k$ a number such that $\gcd(u, v)$ divides $k$. If $k > uv - u - v$, show that there are nonnegative integers $x$ and $y$ so that $k = ux + vy$.

I know that there are integers $x$ and $y$ so that $k = ux + vy$ (since $\gcd$ can be expressed this way, and $k$ is a multiple of $\gcd$), but I'm not sure how to use given condition to prove that nonnegative $x$, $y$ exist.


marked as duplicate by user7530, Gerry Myerson, user53153, mrf, Nate Eldredge Jan 21 '13 at 8:24

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ What are $a$ and $b$? $\endgroup$ – user7530 Jan 21 '13 at 3:19
  • $\begingroup$ sorry, i have edited the question. $\endgroup$ – user59074 Jan 21 '13 at 3:20
  • $\begingroup$ Duplicate of this question (and others). $\endgroup$ – Math Gems Jan 21 '13 at 3:31