4
$\begingroup$

I have a conjecture that any two positive coprime integers $a$ and $b$ can be added to form any integer greater than or equal to $(a-1)(b-1)$.

This is true for $3$ and $5$, which can form any integer greater than or equal to $8$, where $8=3+5, 9=3+3+3, 10=5+5; k=3n+8$ or $3n+9$ or $3n+10$.

It is true for $4$ and $7$, which can form any integer greater than or equal to $18$, where $18=4+7+7, 19=4+4+4+7, 20=4+4+4+4+4, 21=7+7+7$, etc. How can it be proven that this will work for any two coprime numbers?

$\endgroup$
1
  • $\begingroup$ It is mentioned here that $ab-a-b$ can't be achieved as sum of positive multiple of $a$ and $b$. $\endgroup$
    – Watson
    Nov 4, 2016 at 13:20

1 Answer 1

3
$\begingroup$

You're interested in the set of numbers that can be written as $ax+by$ with $x,y \in \mathbb{N}$. So let $n \ge (a-1)(b-1)$ be an integer, we're interested in solving the equation $ax+by = n$ in $\mathbb{N}^2$.

Since $a$ and $b$ are coprime, you may find $u,v \in \mathbb{Z}$ such that

$$au + bv = 1$$

Multiplying the above equation by $n$, we get

$$aun + bvn = n$$

And for all $k \in \mathbb{Z}$ we have

$$a (un+kb) + b (vn-ka) = n$$

So the couples $(un+kb,vn-ka)$ are solutions in $\mathbb{Z}^2$ of our equation (and you may check that those are the only solutions in $\mathbb{Z}^2$, but we won't need that result). Let us prove that we can chose a value of $k$ such that $(un+kb,vn-ka)$ lies in $\mathbb{N}^2$ : Assume $a\ge 2$ (at least one of them is $\ge 2$, we just assume it's $a$), chose the smallest possible $k$ such that $un+kb \ge 0$, so its value is between $0$ and $b-1$ and we get

$$b(vn-ka) = n - (un+kb) \ge (a-1)(b-1)-(b-1) = (a-2)(b-1) \ge 0$$

which concludes. For more information you may want to look at the Coin problem.

$\endgroup$
2
  • $\begingroup$ What does $n-(un+kb, vn-ka)$ mean? $\endgroup$
    – Waffle
    Oct 19, 2015 at 19:35
  • $\begingroup$ @Waffle : sorry, that was a typo, I meant $n-(un+kb)$ :) $\endgroup$
    – Joel Cohen
    Oct 19, 2015 at 19:46

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