Chicken McNugget Theorem

In 1987, mathematicians Henri Picciotto and Wah Keung Chan asked students to find the largest number of McDonald’s chicken nuggets you could NOT buy. At the time, McDonald's only sold nuggets in packs of 9 and 20.

They found that the largest number of nuggets was 151:

The Chicken McNugget Theorem states that for any two coprime, positive integers m and n, the largest number that cannot be made by adding combinations of m and n is mn - m - n. This value is called the largest “purchasable” value. Any number larger than this value can always be made.

(9×20)-9-20=151

Here is an interesting visual proof. It is done by eliminating integers that are non-purchasable through a modulo table (sometimes called a residue table). Repeating this method using actual numbers instead of variables can be used to find the largest unpurchasable number manually for small integers. (Image via Art of Problem Solving):

Several other comprehensive proofs, which I will not bother to regurgitate, can be found here: https://artofproblemsolving.com/wiki/index.php/Chicken_McNugget_Theorem

This problem is a modern version of a classical number theory problem, which is more historically known as ”The Postage Stamp Problem" or “The Coin Problem". See http://en.wikipedia.org/wiki/Coin_problem. These problems are known as Frobenius problems, named after the number theorist Ferdinand Frobenius. The solutions create what is called a numerical semigroup, which also has applications in a field of mathematics known as algebraic geometry.