The largest number that cannot be made using a combination of $5$ and $11$?

Question

Using just the numbers $5$ and $11$, what is the largest number that can not be made?

An example of a feasible combination: $5 \cdot 20 - 11 \cdot 9 = 1$.

An example of an unfeasible number is 13 because it is not a multiple of 5 and it is smaller than $11 + 5$, so it cannot be made.

Answer 1

This sort of question is usually framed in the form $x = ap + bq$, where $a, b > 0$ and $p, q$ are coprime. If you permit negative numbers then every number can be derived from the relation $1 = 1 \cdot 11 - 2 \cdot 5$, and hence $x = x \cdot 11 - 2x \cdot 5$, with transfers of $ 0 = 11 \cdot 5 - 5 \cdot 11$ to tidy things up.

The following supposes that $a, b$ are positive, in the standard case.

The largest number, that can not be made of the sum of a multiple of coprimes $p$ and $q$, is $pq-p-q$. Now, one simply sets $p=5, q=11$, and find that $pq-p-q = 39$.

Suppose $x = ap + bq$. Each multiple of $q$ leaves a different remainder when divided by $p$, which does not change when one adds multiplies of $p$ to it. This means that if $x$ leaves a remainder of $r$ when divided by $q$, there has been some $ap$ that leaves the same remainder. The last remainder to be taken is $q$ hapen with $p(q-1)$.

After this point, there is an $ap \le x$ that has the same remainder of $q$ as $x$ does.

The numbers not expressable in these terms is where one is looking at some $ap-bq$ or $bq-ao$. Since the highest number of this type is $p$ before $q(p-1)$, we find it to be $pq-p-q$.

Answer 2

Note that as soon as you have $1,2,3,4,5$ you can make every number - add $5$ to these, and obtain $6,7,8,9,10$ - and so on.

Let $M$ be the set of numbers which can be expressed in the form $5a+11b$. Then if $n_1=5a_1+11b_1$ and $n_2=5a_2+11b_2$ then $n_1\pm n_2=5(a_1\pm a_2)+11(b_1\pm b_2)$ whence the sum and difference of any two numbers in $M$ is also in $M$.

Now let $d$ be the smallest positive element of $M$ and $n$ an arbitrary element of $M$.

Apply the division algorithm to write $n=kd+r$ for an integer $k$ and $0\le r \lt d$

Then $r\in M$ and if $r$ is non-zero it contradicts the choice of $d$, so $r=0$ and $n$ is a multiple of $d$.

So every element of $M$ is a multiple of the smallest positive integer $d$ it contains. Also, since we chose $d\in M$ in the first place, every multiple of $d$ is in $M$.

An interesting question is to find the largest number which cannot be expressed as $5a+11b$ with both $a$ and $b$ being positive integers.

Answer 3

There is no such number, as you can get every number $n \in \mathbb{N}_0$:

$\begin{align} 5 \cdot 20 - 11 \cdot 9 &= 1 &| \cdot n\\ \Leftrightarrow (5 \cdot 20 - 11 \cdot 9) \cdot n &= 1 \cdot n\\ \Leftrightarrow 5 \cdot (20 \cdot n) - 11 \cdot (9 \cdot n) &= n \end{align}$

Even if you would not have a combination with + and $\cdot$ that is one, you could define arbitrary operators gave you this. My first thought when I read this question was something like the operator $\uparrow$ defined for Grahams number.

Answer 4

This can be expressed very simply:

If any two whole numbers $(x,y)$ are relatively prime (coprime) and if $(x,y)>1$, then:

$LCM(x,y)-(x+y)=GUcM$ (Greatest Uncommon Multiple, my own terminology)

*NOTE: Because $LCM(x,y)$ (lowest common multiple) implies $(x,y)$ are relatively prime, it is not necessary to state that $(x,y)$ must be relatively prime. Conversely, if it is stated that $(x,y)$ are relatively prime, then the formula is simply:

$$(xy)-(x+y)=GCuM$$

Now, to make it seem easier.

If the two numbers $(x,y)$ are not multiples of each other ($\frac{x}y$ and $\frac{y}x$ are not whole numbers) and are bigger than $1$, simply multiply the two numbers ($xy$) and then subtract their sum ($x+y$), which gives:

$(xy)-(x+y)=n$ where n is the solution.

With your two numbers, $5$ and $11$, $\frac5{11}$ is not whole, nor is $\frac{11}5$, so they are relatively prime and greater than $1$, so:

$$(5 \times 11)-(5+11)=39$$

I hope this makes it simple enough.