The Chicken McNugget Theorem
by aoum, Apr 21, 2025, 8:55 PM
The Chicken McNugget Theorem: Frobenius Numbers in Action
The Chicken McNugget Theorem, also known as the Frobenius Coin Problem in two variables, is a fun and famous result in elementary number theory. It gives a formula for the largest number that cannot be expressed as a non-negative integer combination of two relatively prime positive integers.
It gets its name from a problem involving McDonald's Chicken McNuggets, which used to be sold in packs of 6, 9, and 20. The classic version focuses on just two pack sizes.
1. Statement of the Chicken McNugget Theorem
Let
and 
be two relatively prime positive integers. Then the largest integer that cannot be expressed in the form:
is given by:
This number is known as the Frobenius number
for two variables.
2. Examples
3. Proof Sketch of the Chicken McNugget Theorem
Suppose and are positive integers with 
. Then we are considering all numbers of the form:
It turns out that all integers greater than or equal to
can be expressed this way, and 
is the largest integer that cannot.
The core idea involves:
A rigorous proof uses the Sylvester’s theorem or the concept of the semigroup generated by and .
4. Generalization: The Frobenius Problem
For more than two integers
, the Frobenius problem seeks the largest integer not representable as a non-negative integer combination of the 
. For 
, there is no known general formula. The problem is NP-hard in general.
Notation: Let
denote the Frobenius number. Then:
5. Applications
6. Related Theorems
7. Visualization
One can visualize the Chicken McNugget Theorem using lattice points
in the first quadrant such that 
. Each such point corresponds to a solution. The unreachable points fall below a certain diagonal boundary and become sparse as 
increases.
8. References
The Chicken McNugget Theorem, also known as the Frobenius Coin Problem in two variables, is a fun and famous result in elementary number theory. It gives a formula for the largest number that cannot be expressed as a non-negative integer combination of two relatively prime positive integers.
It gets its name from a problem involving McDonald's Chicken McNuggets, which used to be sold in packs of 6, 9, and 20. The classic version focuses on just two pack sizes.
1. Statement of the Chicken McNugget Theorem
Let
and 
be two relatively prime positive integers. Then the largest integer that cannot be expressed in the form:
is given by:
This number is known as the Frobenius number
for two variables.2. Examples
- For
and 
: Since 
, the theorem does not apply. - For
and 
: Since 
, they are coprime. The largest number not expressible as 
is:
Indeed, 23 cannot be expressed using non-negative integer combinations of 5 and 7, but all integers greater than 23 can.
- For and and
: With more than two numbers, no closed formula exists, but the largest number not obtainable from combinations of 6, 9, and 20 McNuggets is 
.
and 
:
,
and 
:
,
is:
:
.3. Proof Sketch of the Chicken McNugget Theorem
Suppose
and are positive integers with 
. Then we are considering all numbers of the form:
It turns out that all integers greater than or equal to
can be expressed this way, and 
is the largest integer that cannot.The core idea involves:
- The fact that because , the equation has an integer solution for all sufficiently large (by the Linear Diophantine Theorem).
- Showing that for
, one can always find a non-negative solution.
,A rigorous proof uses the Sylvester’s theorem or the concept of the semigroup generated by
and .4. Generalization: The Frobenius Problem
For more than two integers
, the Frobenius problem seeks the largest integer not representable as a non-negative integer combination of the 
. For 
, there is no known general formula. The problem is NP-hard in general.Notation: Let
denote the Frobenius number. Then:
when .- No formula exists for when .
when 5. Applications
- Number Theory: The study of semigroups and additive monoids.
- Combinatorics: Integer partition problems.
- Optimization and Operations Research: Coin change and resource allocation.
- Computer Science: Related to NP-completeness and integer programming.
6. Related Theorems
- Sylvester's Theorem: For two relatively prime positive integers and , the number of positive integers that cannot be expressed as
is:
- Erdős–Graham Theorem: On linear Diophantine equations and sums of unit fractions.
- Curtis's Algorithm: An algorithm for computing Frobenius numbers.
is:
7. Visualization
One can visualize the Chicken McNugget Theorem using lattice points
in the first quadrant such that 
. Each such point corresponds to a solution. The unreachable points fall below a certain diagonal boundary and become sparse as 
increases.8. References
- AoPS Wiki: Chicken McNugget Theorem
- Nathanson, M. B. – Elementary Methods in Number Theory
- Beck and Robins – Computing the Continuous Discretely
- Wikipedia: Coin Problem
May 2025
April 2025