0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Bill Dubuque, The Count, YiFan, Daniele Tampieri, José Carlos Santos linear-algebra Jul 23 at 14:06

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Yeah, I don't seem to understand how the equation ab - (a+b) is giving the maximum number which can not be formed using a and b. I tried to understand the Wiki article but I am not getting the formal proof of it. Is their any informal proof of it that shows why the equation is working? $\endgroup$ – darshan Jul 22 at 0:19
  • 2
    $\begingroup$ @darshan There are quite a few posts here related to the coin problem, as you can see from here. One in particular you might find useful is coin problem with two coins, inductive proof. It's also a formal proof, but you may perhaps find it easier to understand when induction is used. $\endgroup$ – John Omielan Jul 22 at 0:23
0
$\begingroup$

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.

$\endgroup$

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