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.

Solution 1:

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.

Solution 2:

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.

Solution 3:

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.