The Chicken McNugget theorem (Frobenius coin problem)
ProvedFamousTheorems.chicken_mcnugget_theoremThe Chicken McNugget theorem. Let be coprime natural numbers. Then is the Frobenius number of : it is the largest natural number that cannot be written as with .
This is Sylvester's 1882 solution of the two-coin case of the Frobenius coin problem. With coins of , and the problem was popularised with boxes of chicken nuggets. For three or more coin values no closed formula of this kind exists.
Formalization note. Mathlib's frobeniusNumber_pair. FrobeniusNumber k s says that is the greatest natural number not in the additive submonoid generated by . The subtraction m * n - m - n is truncated natural subtraction, but it is exact under the hypotheses.
Preamble
import Mathlib
Formal statement
namespace FamousTheorems
theorem chicken_mcnugget_theorem {m n : ℕ} (hmn : m.Coprime n) (hm : 1 < m) (hn : 1 < n) : FrobeniusNumber (m * n - m - n) ({m, n} : Set ℕ) := by sorry
end FamousTheoremsSource
Listed in Mathlib's curated theorem manifests (docs/1000.yaml); formalized in Mathlib as `frobeniusNumber_pair`. Proof here reduces to that Mathlib result.