3
$\begingroup$

Given that $a,b,c\ $ are pairwise relatively prime, what is the largest number not expressible as a linear combination of $a,b,c\ $?

What if $a$ and $b$ have common factor $m$?

What if $a$ and $b$ have common factor $m$, and $b$ and $c$ have common factor $n$?

$\endgroup$
5
  • $\begingroup$ I don’t know how to do the notation correctly. Can anyone help me with that? $\endgroup$
    – Lieutenant Zipp
    Commented Apr 25, 2019 at 21:22
  • 1
    $\begingroup$ For starters, put dollar signs at each end of each attempted MathJax expression. $\endgroup$
    – J.G.
    Commented Apr 25, 2019 at 21:23
  • 1
    $\begingroup$ Out of curiousity...why do they call it the Chicken Nugget Theorem? $\endgroup$
    – Mike
    Commented Apr 25, 2019 at 21:27
  • 3
    $\begingroup$ @Mike youtube.com/watch?v=vNTSugyS038 $\endgroup$
    – DanLewis3264
    Commented Apr 25, 2019 at 21:29
  • 2
    $\begingroup$ There was a Numberphile video on it a while back. I think it originally comes from people trying to order McDonald’s nuggets which came in boxes of 9 and 20. Or something. $\endgroup$
    – Lieutenant Zipp
    Commented Apr 25, 2019 at 21:30

2 Answers 2

Reset to default
8
$\begingroup$

This is more of an extended comment than an answer to your specific questions.

This is called the Frobenius number of the semigroup generated by $a,b$ and $c$. The case for two generators, say $a$ and $b$ with $a$ and $b$ rel. prime, has a closed formula given by $$ g(a,b)=ab-a-b.$$

However, in general for 3 generators it is known that there is no polynomial formula expressing the Frobenius number in terms of $a,b$ and $c$. The reference is F. Curtis (1990). "On formulas for the Frobenius number of a numerical semigroup". Mathematica Scandinavica. 67 (2): 190–192. You can find the paper here: https://www.mscand.dk/article/view/12330/10346

You can read more about this in: https://en.wikipedia.org/wiki/Coin_problem#Statement or https://en.wikipedia.org/wiki/Numerical_semigroup

$\endgroup$
1
  • $\begingroup$ Well, from what I’m reading, there is only no Frobenius Number when gcd(a,b,c)=1, which is a different (and weaker) condition than I had, which allowed only pairwise common factors. $\endgroup$
    – Lieutenant Zipp
    Commented Apr 25, 2019 at 21:43
2
$\begingroup$

Your not all relatively prime cases, are restricted cases of the 2 number cases: $$a=md\land b=me \implies m(dx+ey)+cz=f$$

aka what are the values that can't be made by combinations of d and e, multiply them by m and ask what numbers they can't reach by adding an integer multiple of c to them.

Your all relatively prime case, I'm not sure about except by looking at the other answer.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .