How co prime numbers can be used to form any number beyond a number

Question

Suppose we have two co prime numbers a and b. Then it is always possible to form any number greater than or equal to a*b - a - b +1 by using the given co primes only that is ax + by where x and y will be non negative integers. I can't seem to find the logic behind it? How it is happening and why?

Answer 1

This is the coin problem with two coins. In fact, you can form any number that is greater than $ab-a-b$. For example, let $a=7,b=4$. We should be able to express any number greater than $17$. In fact, $18=2\cdot 7+4, 19=7+3\cdot 4, 20=5\cdot 4, 21=3\cdot 7$ and now we can just add enough $4$s to get any higher number.

Answer 2

Here's a somewhat intuitive explanation, though not the most elegant formally:

We group all formable numbers based on how many copies of $a$ we need (i.e., the value of $x$). Note that if $x > b$, we can replace $b$ copies of $a$ by $a$ copies of $b$, so we can assume $1 \leq x \leq b$. Then the formable numbers are:

$$0, b, 2b, 3b, \dots$$ $$a, a+b, a+2b, a+3b, \dots$$ $$2a, 2a+b, 2a+2b, 2a+3b, \dots$$ $$\dots$$ $$(b-1)a, (b-1)a+b, (b-1)a+2b, (b-1)a+3b, \dots$$

Since $a$ and $b$ are coprime, no two groups overlap. Now consider some interval $[n-b+1,n]$ where $n \geq (b-1)a$. Since the interval is exactly $b$ integers long, and each group contains members spaced exactly $b$ apart, it must contain a member of each group. Since there are $b$ groups, and no two groups overlap, every integer in the interval must belong to some group, i.e., every integer in the interval is formable.

Thus every integer greater than or equal to $(b-1)a-b+1 = ab-(a+b)+1$ is formable.