Chicken McNugget (Frobenius) Theorem

Largest unreachable total for two coprime coins: ab - a - b.

The idea

The Chicken McNugget theorem (the Frobenius theorem for two denominations) names the largest total that two fixed pack sizes cannot pay. Reach for it whenever a problem gives two denominations and asks for the largest amount that cannot be made exactly, or for how many amounts are missed.

Suppose items come in pack sizes $a$ and $b$, and we may buy any whole number of each. Buying $m$ packs of the first and $n$ of the second gives $am + bn$, so a total is representable when it equals $am + bn$ for some integers $m, n \ge 0$. Small totals are skipped — with packs of $4$ and $7$ no purchase gives exactly $5$ — but large totals are not, because a large total can trade packs of one size against the other in many ways.

Theorem (Chicken McNugget theorem).

Let $a$ and $b$ be coprime positive integers. The largest total not representable as $am + bn$ with integers $m, n \ge 0$ is $g(a, b) = ab - a - b,$ and exactly $\tfrac{(a-1)(b-1)}{2}$ nonnegative totals are non-representable.

The coprimality hypothesis is essential. If $a$ and $b$ share a factor $d > 1$, every $am + bn$ is a multiple of $d$, so infinitely many totals are unreachable and no largest one exists.

Ways to work on it

• Walkthrough. The Frobenius number ab - a - b, why coprimality matters, and the gap count.
• Proof. Prove the Frobenius number ab - a - b via residue classes mod a.
• Practice. Apply ab - a - b to a coprime pair of denominations.
• Hardest. Recover a denomination from the Frobenius number, then count the gaps.

Not sure where to start? Take the ten-question placement test.