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

• If you also allow negative coefficients $a,b$, then we would get that all natural numbers can be written in the form of $ax+by$. – Berci Jan 28 '14 at 16:17

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.

• In "3." you've done mistake; correct is: $a(x_1-tb)\ge (ab-a-b+1)-b(a-1)=-a+1$ which doesn't complete the proof as it is wrong! – user231343 Aug 6 '17 at 0:42
• @Edi That error is not critical. See e.g. Hagen von Eitzen's answer below. – Jyrki Lahtonen Aug 6 '17 at 8:12
• @user231343 He did make a mistake but $a(x_1-tb)\ge-a+1$ is sufficient to show that $x_1-tb\ge0$. – User Apr 15 '19 at 10:17
• I've taken the liberty to both correct this mistake and also make the proof a bit more reader-friendly (some steps ended up unnecessary). – darij grinberg Aug 14 '19 at 18:22

By the extended Euklidean 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.

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.

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

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

• I don't see where you get your "Moreover" sentence from. Why must the sequence begin no later than $b(a-2)$? – darij grinberg Aug 14 '19 at 18:35
• Oh, I see -- it must begin with a multiple of $b$ (since any of your $a$ many sequences does), but $b(a-1)+m$ is not a multiple of $b$, so it must begin earlier than that. – darij grinberg Aug 14 '19 at 18:39
• But wait, if this only works for $0 < m \leq b-1$, then we are missing some numbers. I'm confused... – darij grinberg Aug 14 '19 at 18:41