Numbers that add to generate any other number

Question

Here I would like to state about the numbers $3$ and $5$,which by the help of addition(any number of times) can generate any number from $8(=5+3)$ on-wards.

For example:
$9 = 3 + 3 +3$
$10 = 5+5$
$11=5+3+3$ and so on.Further we know that if we can generate any nine consecutive numbers then we can generate further numbers from the ninth number onward by addition.Hence this pair (3,5) has this ability. My Question :
Is there any name for these kind of pairs?Further is there any method to find such pairs?

Answer 1

Consider how you would generate some natural numbers with this method. I'll simplify your notation by your sums as multiples of $3$ and $5$.

$$\begin{aligned}\color{red}{1}\times3+\color{blue}{1}\times5&=8\\ \color{red}{3}\times3+\color{blue}{0}\times5&=9\\ \color{red}{0}\times3+\color{blue}{2}\times5&=10\\ \color{red}{2}\times3+\color{blue}{1}\times5&=11\\ \ldots \end{aligned}$$

Can you notice any patterns appearing? Consider how you change the red and blue multiples of $3$ and $5$, if you wanted to increase the right-hand-side by $1$.

$$\begin{aligned}&\color{red}{1}&&\color{blue}{1}&&8\\ &\color{red}{\downarrow(+2)}&&\color{blue}{\downarrow(-1)}&&\downarrow(+1)\\ &\color{red}{3}&&\color{blue}{0}&&9\\ &\color{red}{\downarrow(-3)}&&\color{blue}{\downarrow(+2)}&&\downarrow(+1)\\ &\color{red}{0}&&\color{blue}{2}&&10\\ &\color{red}{\downarrow(+2)}&&\color{blue}{\downarrow(-1)}&&\downarrow(+1)\\ &\color{red}{2}&&\color{blue}{1}&&11\\ \end{aligned}$$

You should be able to see that we can increase the right-hand-side by $1$ by either:

• adding $\color{red}{2}$ more $3$'s but $\color{blue}{1}$ fewer $5$

• or by adding $\color{red}{3}$ fewer $3$'s and $\color{blue}{2}$ more $5$'s.

We can continue in this regard to generate more integers, using whichever of these two rules that lets us keep a nonzero number of $3$'s and $5$'s. But why does this work? Fundamentally, it is because $\color{red}{2}\times3+\color{blue}{(-1)}\times5=1$. But also, $\color{red}{(-3)}\times3+\color{blue}{2}\times5=1$. Hence, we can raise our right-hand-side by $1$ by changing the number of $3$'s and $5$'s on left-hand-side.

If there are integers $x,y$, such that the integers $a,b$ satisfy $xa-yb=1$, then $a$ and $b$ are coprime. Hence, coprime natural numbers are the numbers you're looking for. An easy way to generate an integer $b$, that is coprime to an integer $a$ is to pick a $b$ that shares no factors with $a$. For example if $a=3$, you could pick $4,5,7,8,10,\ldots$.

However I'm not quite sure how to prove that you will always have enough $3$'s and $5$'s to allow you to generate arbitrarily large numbers.

Answer 2

Such pair is called co-prime and a special case of an additive base $\mathcal{B}$ of the natural numbers. Every subset of the natural numbers is called an additive base $\mathcal{B}$ if there is a natural number $h$ such that every sufficiently large natural number $n$ can be constructed as sum of at most $h$ numbers from $\mathcal{B}$.

The largest number that cannot be constructed using this set given $h$ is called Frobenius number.

Answering your question, any pair of co-prime numbers will possess this property. Let $a, b$ be co-prime, then given their Frobenius number $ab -a - b$ all subsequent integers $n > ab -a - b$ can be represented as linear combination $n = ax + by$ of $a$ and $b$ with non-negative integer coefficients $x$ and $y$.