2
$\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$
  • $\begingroup$ I don’t know how to do the notation correctly. Can anyone help me with that? $\endgroup$ – Lieutenant Zipp Apr 25 '19 at 21:22
  • 1
    $\begingroup$ For starters, put dollar signs at each end of each attempted MathJax expression. $\endgroup$ – J.G. Apr 25 '19 at 21:23
  • 1
    $\begingroup$ Out of curiousity...why do they call it the Chicken Nugget Theorem? $\endgroup$ – Mike Apr 25 '19 at 21:27
  • 3
    $\begingroup$ @Mike youtube.com/watch?v=vNTSugyS038 $\endgroup$ – bounceback Apr 25 '19 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 Apr 25 '19 at 21:30
5
$\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$
  • $\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 Apr 25 '19 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$

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.