# basic number theory question (gcd) [duplicate]

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 EldredgeJan 21 '13 at 8:24

• What are $a$ and $b$? – user7530 Jan 21 '13 at 3:19