The Frobenius Coin Problem I am asked to prove that:  

For integers $n, x,y > 0$, where $x,y$ are relatively prime, 
      every $n \ge (x-1) (y-1)$ can be expressed as $xa + yb$, with nonnegative integers $a,b \ge0$.

How should I approach this? I have very limited knowledge in number theory.
 A: Key Idea $ $ In the plane $\,\mathbb R^2,\,$ a line $\rm\,a\,x+b\,y = c\,$ of negative slope has points in the first quadrant $\rm\,x,y\ge 0\ $ iff its $\rm\,y$-intercept $\rm\,(0,\,y_0)\,$ is in the first quadrant, i.e. $\,\rm y_0 \ge 0\,.$  We can use an analogous "normalized" point test to check if a discrete line $\rm\,m\,x + n\,y = k\,$ has points in the first quadrant.
Hint $\ $  Normalize $\rm\,k = m\, x + n\, y\,$ so  $\rm\,0 \le x < n\,$
by adding a multiple of $\rm\,(-n,m)\,$ to $\rm\,(x,y)$
Lemma $\rm\ \ k = m\ x + n\ y\,$  for some integers  $\rm\,x,\,y \ge 0\,$
$\iff$ its normalization has $\rm\,y \ge 0.$ 
Proof $\ (\Rightarrow)\ $ If $\rm\ x,\, y \ge 0\,$  normalizing adds $\rm\,(-n,m)\,$ zero or more times, preserving $\rm\,y \ge 0\,.\,$
$(\Leftarrow)\ \,$ If the normalized rep has $\rm\ y < 0,\,$ then $\rm\,k\,$ has no representation with $\rm\, x,\,y \ge 0\,\, $ since to shift so that $\rm\,y > 0\,$
we must add $\rm\,(-n,m)\,$ at least once, which forces $\rm\,x < 0,\,$ by $\rm\,0\le x < n.\ \ \ $ QED
To solve the OP, note that since  $\rm\, k = m\ x + n\ y\, $ is increasing in both $\rm\,x\,$ and $\rm\,y,\,$ it is clear that the largest non-representable $\rm\,k\,$ has normalization $\rm\,(x,y) = (n\!-\!1,-1),\,$ i.e. the lattice point that is rightmost (max $\rm\,x$) and topmost (max $\rm\,y$) in the nonrepresentable lower half $\rm (y < 0)$ of the normalized strip, i.e. the vertical strip where $\rm\, 0\le x \le n-1.\,$ Thus $\rm\,(x,y) = (\color{#0a0}{n\!-\!1},\color{#c00}{-1})\,$ yields that  $\rm\, k = mx+ny = m\,(\color{#0a0}{n\!-\!1})+n\,(\color{#c00}{-1}) =  mn\! -\! m\! -\! n\ $ is the largest nonrepresentable integer. $\ $ QED
Notice that the proof has a vivid geometric picture: 
representations of $\rm\,k\,$ correspond to lattice points $\rm\,(x,y)\,$
on the line $\rm\, n\ y + m\ x = k\,$  with negative slope $\rm\, = -m/n\,.\,$
Normalization is achieved by shifting forward/backward 
along the line by integral multiples of the vector $\rm\,(-n,m)\,$
until one lands in the normal strip where $\rm\,0 \le x \le n-1.\,$ If the normalized rep has $\rm\,y\ge 0\,$ then we are done; otherwise, by the lemma, $\rm\,k\,$ has no rep with both $\rm\,x,y\ge 0\,.\,$ This result may be viewed as a discrete analog of the fact that, in the plane $\,\mathbb R^2,\,$ a line of negative slope has points in the first quadrant $\rm\,x,y\ge 0\ $ iff its $\rm\,y$-intercept $\rm\,(0,\,y_0)\,$ lies in the first quadrant, i.e. $\rm y_0 \ge 0\,.$
There is much literature on this classical problem. To locate such work 
you should ensure that you search on the many aliases, 
e.g. postage stamp problem, Sylvester/Frobenius problem, 
Diophantine problem of Frobenius, Frobenius conductor, 
money changing, coin changing, change making problems, 
h-basis and asymptotic bases in additive number theory, 
integer programming algorithms and Gomory cuts, 
knapsack problems and greedy algorithms, etc.
A: This problem is similar to the "coin problem", where you need to find the smallest integer from which every integer can be obtained with a linear combination of the values of your coins with positive coefficients.
For your problem with 2 numbers (aka 2 coin values), a solution can be found here : http://www.cut-the-knot.org/blue/Sylvester.shtml#solution
A: We sketch a proof. For my comfort, I will use $a$ and $b$ instead of $x$ and $y$. Sorry!  So we show that every $n\ge (a-1)(b-1)$ is representable in the form $au + bv$ with $u$ and $v$ being nonnegative integers.
1. Because $a$ and $b$ are relatively prime, there exist integers $x_0,y_0$ (not necessarily both $\ge 0$) such that $ax_0+by_0=1$. Thus (multiplying through by $n$) we find that there exist integers $x_1,y_1$ such that $ax_1+by_1=n$.
2. Infinitely many solutions of the equation $ax+by=n$ are given by $x=x_1-tb$, $y=y_1+ta$, where $t$ ranges over the integers. (Actually these are all solutions, but we won't need this.)
3. Let $t$ be the smallest positive integer such that $y_1+ta\ge 0$. We show that $x_1-tb\ge 0$.  We have 
$$a(x_1-tb)+b(y_1+ta)=n \ge (a-1)(b-1),$$
thus
$$a(x_1-tb) \ge (a-1)(b-1) - b(y_1+ta).$$
But $y_1+ta\le a-1$, else we could decrement $t$. 
Thus 
$$a(x_1-tb)\ge (a-1)(b-1)-b(a-1) = -(a-1) > -a,$$
and therefore $x_1-tb> -1$, so that $x_1-tb \geq 0$ (since $x_1-tb \in \mathbb{Z}$). So we have produced the required non-negative solution. 
A: By the extended Euclidean algorithm one finds $u,v\in\mathbb Z$ with $ux+vy=1$, hence for any integer $n$ we can find a representation $n=a x+b y$ with $a,b\in\mathbb Z$.
With $ax+by=n$ we also have $(a+ky)x+(b-kx)y=n$, hence there exist solutions to $n=ax+by$ with $a\ge 0$. Among all those solutions pick one that minimizes $a$.
Then $0\le a\le y-1$ because otherwise $(a-y)x+(b+x)y$ would be "better".
If $n\ge (x-1)(y-1)$, we find that
$$by = n-ax\ge (x-1)(y-1)-(y-1)x = 1-y>-y $$
hence $b>-1$, i.e. $b\ge 0$ as required.
A: Let me show another proof of this elementary problem (in terms of $a$ and $b$ as constants and $x$, $y$ as variables). 
Let $i$ be the least (non-negative) residue of $y$ modulo $a$. Then one can rewrite the form $ax+by$ as $ax+b(i+az)=bi+a(x+bz)$. Given $0 \leq i \leq a-1$, we obtain the sequence $bi+an$, $n\geq 0$, of integers, which can be represented by the form (and only elements of these sequences possess this property). 
Suppose that $a$ and $b$ are coprime positive integers. It follows from the extended Euclidean algorithm that $b$ is an invertible element of $\mathbb{Z}/a\mathbb{Z}$. Therefore, the multiplication by $b$ is an automorphism of the ring $\mathbb{Z}/a\mathbb{Z}$. Thus, all $bi$'s are distinct modulo $a$, i.e. two different sequences contain no common elements. 
Note that the smallest element of each of these sequence is less than or equal to $b(a-1)$, i.e. they "begin" not later than this "moment". Obviously, any integer $N \geq b(a-1)$ appears in exactly one of those sequence. Moreover, the sequence that corresponds to $b(a-1)+m$, $0<m \leq a-1$, contains $b(a-1)+m-a \geq b(a-2)$, since it begins not later than $b(a-2)$. Thus, any integer $N \geq b(a-1) + 1 - a = (a-1)(b-1)$ can be represented by the form.
It suffices to see that $ax+by=(a-1)(b-1)-1$ has no non-negative solutions.
A: HINT:
We have
$$a x + b y = (a - q y) x + (b + q x) y$$
Therefore, every number that is an integer combination
$n = a x + b y$ is also an integer combination $n = a x + b y$, with $0 < a \le y$.
Now, consider a number $n > x y$ that is an integral combination of $x$, $y$, that is $n = a x + b y$. We may assume that $0 \le a \le y$. We conclude that $b >0$.
Since $x$, $y$ is relatively prime, every integer is an integer combination of $x$, $y$. This and the previous arguments implies: every integer $> x y$ is a positive integral combination of $x$, $y$.
Let us also show that $x y$ is not a positive integral combination of $x$, $y$. Indeed, consider
$$x y = a x + b y$$ Then $a x$ is divisible by $y$, and since $(x,y) = 1$,  $a$ is divisible by $y$, $\&$ c $\ldots$
Note: it is easier to consider the problem for $a$, $b>0$, rather than $a$, $b\ge 0$. This is also @Atom: 's observation.
