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.
On
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
On
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.
On
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.
On
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.
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.