Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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$.
Basically, 0+5=5 and 11+5=16. Anything in the middle cannot have a remainder of 0.
Anything from 16 and 27 cannot have a remainder of 0 OR 1.
27-38: no 0,1,2
38-39: no 0,1,2,3
Thus, largest number can be 39.
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.
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.
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.
I was unsatisfied by the rigour and completeness of other answers regarding the case of conical (nonnegative coefficient) combinations so have provided an alternative proof at the expense of wordiness. For conical combinations, the problem is known as the Frobenius Coin Problem for $n=2$ or the Chicken McNugget Theorem.
Let $a,b,p,q\in\mathbb{N}_1$. If $p,q$ are not coprime, there exist arbitrarily large integers that are coprime to both and cannot be given in the form $ap+bq$, e.g., if $p=6,q=8$, then $ap+bq=2\left(3p+4q\right)$ is even and cannot express odd numbers. Therefore, let $p,q$ be coprime. We can use the ansatz that the largest number inexpressible in the form $ap+bq$ is $pq-p-q$. This can be proven by first proving that it is indeed inexpressible and then proving that every integer greater than it is expressible.
If $pq-p-q=ap+bq$ for some $a,b$, then $p\left(q-1-a\right)=q\left(1+b\right)$. Since $p,q$ are coprime but $p$ divides the RHS, it must divide $\left(1+b\right)=pk$ for some integer, $k$. Therefore, $pq-p-q=ap+\left(pk-1\right)q$, so $a=q\left(1-k\right)-1$ and $pq-p-q=p\underbrace{\left[q\left(1-k\right)-1\right]}_{a}+q\underbrace{\left[pk-1\right]}_{b}$. For $a,b$ to be positive, we would have $0<\frac{1}{p}<k<1-\frac{1}{q}<1$ and $k$ is not an integer, which is absurd. We have reached a contradiction, therefore $pq-p-q$ cannot be expressed as $ap+bq$.
We would then aim to prove that all integers $n>pq-p-q$ are expressible in the form $ap+bq$. Assume $n=ap+bq$. Since $p,q$ are coprime, by Bezout's identity, there are (not necessarily nonnegative) integers, $a', b'$, such that $a'p+b'q=1$. Therefore all integers can be expressed as $(na'+iq)p+(nb'-ip)q=n$ for all integers $i$. The set of integer pairs $a=(na'+iq),b=(nb'-ip)$ describes all possible values of $a,b$. This can be proven by letting $A,B$ be another pair of integers that satisfies $Ap+Bq=n$. Then, $[ap+bq]-[Ap+Bq]=n-n$, so $(a-A)p=(b-B)q$. But then, since $p,q$ are coprime, $(a-A)$ must be an integer multiple of $q$ and likewise $(b-B)$ an integer multiple of $p$. Therefore, any solution $A,B$ must be be offset from $k,m$ by an integer multiple of $q$ and $p$ respectively, so all solutions are of the form $a=(na'+iq),b=(nb'-ip)$.
Given an integer, $n$, since $b$ is $p$-periodic, there are thus one unique $b$ and $i$ such that $0\le b<p$. So, then $n$ can demonstrably be expressed in the form $ap+bq$ with positive $b$. If the corresponding $a$ is also nonnegative then there is nothing left to prove. However, if $a<0$ then $na'+iq<0$, which remains true when $i$ is decreased. But also, $(nb'-ip)$ would become negative if $i$ were increased, so at least one of $a,b$ would remain negative. Therefore, $n$ is expressible as $ap+bq$ if and only if $a\ge 0$. The largest integer that cannot be expressed with positive $a,b$ is therefore the maximal integer such that $a<0$ and $0\le b <p$, which is $-1\cdot p + (p-1) q=pq-p-q$. Therefore, all integers greater than $pq-p-q$ can be expressed.
Frobenius coin problem for $n=2$
Related questions
