1
$\begingroup$

If $m$ and $n$ are relatively prime then the set $\{xm + ny : x,y \in Z^+\}$ contains all but a finite number of the positive integers.

What I tried : We know that there exist integers $x,y$ such that $mx+ny=1$. But both can't be negative/positive. So, we need to separate the positive and negative part of each coefficient. Let $a_1 =x^+$ and $b_1=x^-$ and $a_2 =y^+$ and $b_2=y^-$. Then $ma_1 + na_2 = 1 + mb_1 + nb_2$. So, I have got two consecutive integers. Stuck after that.

$\endgroup$
3
  • $\begingroup$ This is the coin problem for two coins. $\endgroup$
    – Arthur
    Oct 22, 2013 at 14:03
  • $\begingroup$ @Arthur: I said $x,y$ are positive integers, but the theorem says that it is non-negative. $\endgroup$
    – user96000
    Oct 22, 2013 at 14:08
  • $\begingroup$ That will have an effect on the actual bound, but not on the fact that there are only a finite number of unreachables. To see this, take one of each coin, and set them aside. Now use the theorem to show that the highest unobtainable result (not counting the two you set aside) is $mn - (m + n)$. Add back the two coins you set aside, and see that the highest unreachable number is $mn$, with at least one of each coin present. $\endgroup$
    – Arthur
    Oct 22, 2013 at 14:13

1 Answer 1

1
$\begingroup$

Take a large enough number $t$ (Say, $t>mn$). Then take the set $\{t-in,0\le i< m\}$. This set contains $m$ numbers.

If two elements in this set are the same $\pmod m$, we have: $$ t-i_1n\equiv t-i_2n \pmod m\\ i_1n\equiv i_2n \pmod m\\ m|(i_1-i_2)n$$ Since $gcd(m,n)=1$, it impies $m|i_1-i_2$ Which is impossible since $m>i_1-i_2$.

So any two elements in this set are different from each other $\pmod m$. This implies one of them equal to 0 $\pmod m$, or $m|t-i_rn$ for some $r$: $$ m|t-i_rn\\ t-i_rn=km\\ t=km+i_rn $$

As needed.

There are only finitely many numbers that $<mn$.

$\endgroup$

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