3
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ I would at least consider the GCD of the numbers, it should be one! For example, you certainly cannot make a linear combination of 4 and 8 to make 9, that's for sure ... $\endgroup$ – Matti P. Jul 19 '18 at 10:42
  • 1
    $\begingroup$ Such numbers are called coprime. $\endgroup$ – Lord Shark the Unknown Jul 19 '18 at 10:42
  • 1
    $\begingroup$ Yes I want the coefficients to be positive and allow only addition. $\endgroup$ – Sourajit Jul 19 '18 at 11:01
  • 1
    $\begingroup$ Note that it's not $8 = 5+3$ which is the limit, it's $8 = 5\cdot 3 - 5 - 3+1$. In general, given two natural numbers $a, b$ with no common factors, the largest number you cannot make is $ab-a-b$. You can see this clearer if you use, say, $10$ and $11$, as you still can't make $22$. This is known as the (two) coin problem. $\endgroup$ – Arthur Jul 19 '18 at 11:05
  • 1
    $\begingroup$ @polko14 you're right. I goofed. $23$ is a better number. $\endgroup$ – Arthur Jul 19 '18 at 12:16
4
$\begingroup$

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$.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ It appears that the OP might want the coefficients of $a$ and $b$ to be positive (which is not what happens in your case by simply multiplying by $n$). $\endgroup$ – Michael Burr Jul 19 '18 at 10:51
  • $\begingroup$ @MichaelBurr fixed $\endgroup$ – Jam Jul 19 '18 at 13:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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