$a,b,c$ are natural numbers whose greatest common divisor is $1$.

$a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$

Try to write down the expression using $a,b,c$ of the biggest natural number $M$ that cannot be write down in following forms: $M=xa+yb+zc$, $x,y,z\in\mathbb{N}$

Or say it in this way, $3$ kinds of weights which respectively weigh $a,b,c$, $a,b,c\in\mathbb{N}^*$, $(a,b,c)=1$. They only can be put on one side of the balance. What's the biggest weigh $M\in\mathbb{N}$ that cannot be weighed using these $3$ kinds of weights
What's more, if possible, when there are $a,b,c,\dots,n$ ($n$ kinds of weights in all), what's the largest weigh $M$?
To give some referrings, when there are only two kinds of weights, $M=(a-1)(b-1)$

I think it might be possible to use the linear combinations of primes to solve it but up to now I have no idea.

I'm trying to write a programme that can generate $M$ and put them into coordinate systems and probably I can find the regulation....

Can you help?


3 Answers 3


This is known as the Frobenius coin problem. As you state, the solution for one and two numbers is known. For three (or more) only partial results are available.


In a 2004 paper by Fel titled "Frobenius Problem for Semigroups $S(d_1,d_2,d_3)$ a complete answer to the 3-generator case is given.

We need to define some notation first. $S(d_1,d_2,d_3)$ is the semigroup of all natural numbers that can be obtained using $d_1,d_2,d_3$. $S(d_1,d_2)$ is defined similarly, but only using $d_1, d_2$. Set $c_1$ to be the minimal positive integer such that $c_1d_1\in S(d_2,d_3)$. Similarly, set $c_2$ to be minimal so that $c_2d_2\in S(d_1,d_3)$ and $c_3$ minimal so that $c_3d_3\in S(d_1,d_2)$. Set $w=c_1d_1+c_2d_2+c_3d_3$.

Now, the desired Frobenius number is $\frac{1}{2}\left( w+\sqrt{w^2+4d_1d_2d_3-4(c_3c_2d_3d_2+c_3c_1d_3d_1+c_2c_1d_2d_1)}\right)-d_1-d_2-d_3$.

As a programming matter, however, it's simpler to generate $S(d_1,d_2,d_3[,d_4,\ldots])$ with the knowledge that its frobenius number is no larger than the (known) frobenius number for $S(d_1,d_2)$.


Just wanted to say that there are two versions of what it means for a set of integers to be all relatively prime, each leading to a slightly different version of this Question:

a) The greatest common divisor of all numbers is 1,


b) All pairs of numbers are relatively prime.

The set {6, 10, 15} would be relatively prime under definition a), but not under b). Of course a set satisfying b) would also satisfy a).

Obviously a) is the definition used in this Question. But using definition b) might also be interesting.


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.