# Given any two co-prime numbers x and y are there only finitely many integers that cannot be expressed as Ax + By?

If we have any two co-prime positive integers x and y, does there always exist a positive integer C such that all integers greater than C can be expressed as Ax+By where A and B are also non-negative integers?

Do we have a formula to calculate the largest non-expressable integer (i.e. C-1) in such a case?

EDIT: A and B are non-negative, not necessarily positive. Either one of them can be 0.

• Yes, if by integers you mean positive integers. See en.wikipedia.org/wiki/Coin_problem. Jan 22, 2016 at 4:46
• This Q has appeared in more than a few contests. Jan 22, 2016 at 8:24

This is sometimes called the coin problem, and the answer for two coins of relatively prime denominations $a$ and $b$ is $ab-a-b$, when we are allowed to use zero of either coin.

To find the answer when the coefficients are required to be positive, we simply subtract one coin of each type, giving an answer of $(xy-x-y)+(x+y)=xy$ for the largest number that cannot be so expressed.

For example, if $x=3$, $y=4$, then we can verify that $12$ has no expression as the sum of positive multiples of $3$ and $4$, but $13=3\cdot 3 + 1\cdot 4$, $14=2\cdot 3 + 2\cdot 4$, $15=1\cdot 3 + 3\cdot 4$. Since $13,14,15$ can be expressed in this form, we can get any positive integer $> 12$ by adding multiples of $3$.

I'm going to use more conventional notation otherwise my head will explode ;-)

Theorem. Let $a,b$ be coprime positive integers, let $c$ be an integer, and consider the equation $$ax+by=c\ .$$

• If $c=ab$ then the equation has no solutions in positive integers $x,y$.
• If $c>ab$ then the equation has solutions in positive integers $x,y$.

Proof. For the first result we consider $$ax+by=ab\ ,$$ and suppose that $x,y$ are positive integers. From this equation we have $$b\mid ax\quad\hbox{and}\quad a\mid by\ ,$$ and since $a,b$ are coprime this gives $$b\mid x\quad\hbox{and}\quad a\mid y\ .$$ Since $x,y$ are positive we have $x\ge b$, $y\ge a$ and so $ax+by\ge2ab$, which contradicts the given equation.

For the second, consider $$ax+by=c\ ,$$ where $c>ab$. The general integer solution of this is $$x=x_0+bt\ ,\quad y=y_0-at\ ,\quad t\in{\Bbb Z}\ ,$$ where $(x_0,y_0)$ is a specific solution, that is, $ax_0+by_0=c$. There will be a positive solution if we can find an integer $t$ such that $$-\frac{x_0}b<t<\frac{y_0}a\ .$$ But the interval from $-x_0/b$ to $y_0/a$ has length $$\frac{y_0}a-\Bigl(-\frac{x_0}b\Bigr)=\frac{ax_0+by_0}{ab}=\frac{c}{ab}>1\ ,$$ so it must contain an integer. This completes the proof.