1
$\begingroup$

I need to know what the lowest consecutive number would be that is possible by simply adding 2 numbers any times necessary.

I came up with a simple formula for numbers with greatest common divisor 1: $a$ and $b$ are the input numbers and are bigger then 0.

$$\text{result} = (a * b) - a - b + 1.$$

But I can only prove it by running the numbers trough it and knowing that you can get any number by simply proving that numbers are consecutive if they have a sequence of a length of the smallest number.

I also deduced that there is a formula for 2 numbers with a GCD > 1 but these are only consecutive in steps of the GCD.

$$\text{result} = \frac{a * b}{\text{GCD}(a,b)} - a - b + \text{GCD}(a,b).$$

Now my question is: is there some prove for this or is this wrong? And does there already exist a formula for a bigger set of number instead of just 2 numbers?

PS: I tried my best to explain it clearly, but I am not that well versed in math.

$\endgroup$
2
  • 1
    $\begingroup$ Thanks @Rory-Daulton for editing the post. $\endgroup$
    – Gero3
    Dec 27, 2014 at 13:02
  • 1
    $\begingroup$ Thanks @MattAllegro for editing the post. $\endgroup$
    – Gero3
    Dec 27, 2014 at 13:03

1 Answer 1

2
$\begingroup$

It is true that for positive co-prime integers $a,b$ you can write every natural number starting from $ab - a - b + 1$ as the sum (repetitions allowed) of $a$ and $b$ and this is the smallest number with this property; this quantity, or rather the number one less, is called the Frobenius number of $a$ and $b$.

If you have non-coprime numbers $a,b$ let there GCD be $d$ and write $a'=a/d$ and $b'=a/d$. Then $a'$ and $b'$ are co-prime and by the result above you can write every natural number starting from $a'b' - a' - b' + 1$ as the sum (repetitions allowed) of $a'$ and $b'$. Multiplying an expression of the form $k= x a' + y b'$ by $d$ you get that $dk= x a + y b$. This shows that, as you suspected, every number of size at least $$\frac{ab}{\gcd(a,b)} - a - b + \gcd(a,b)$$ can be written as a sum of $a$ and $b$ if that number is a multiple of $\gcd(a,b)$. This additional condition is also necessary as every number of the form $xa+yb$ is divisible by the GCD of $a$ and $b$.

The problem for more than two numbers is a lot more complicated. There is a lot of research on it, and in a certain sense one can even show that there cannot exist a convenient formula for the Frobenius number in general; there are however various bounds known.

$\endgroup$
2
  • $\begingroup$ Thanks, I really couldn't find anything about it. Thanks for that. Now I at least can use it further. $\endgroup$
    – Gero3
    Dec 27, 2014 at 12:58
  • $\begingroup$ You ware welcome. I understand without the right key-word it is hard to find this. For a book see: The Diophantine Frobenius Problem, J.L. Ramírez Alfonsín, Oxford Lectures Series in Mathematics and its Applications 30, Oxford University Press, (2005) $\endgroup$
    – quid
    Dec 27, 2014 at 13:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .