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.

| cite | improve this question | | | | |

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

| cite | improve this answer | | | | |

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.

| cite | improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.