The Chicken McNugget Theorem, Explained
The BTS Chicken McNugget Meal, Why you can’t buy 43 McNuggets at McDonald’s, and a math problem from the 1800s.
Throughout the past month, the BTS Chicken McNugget meal has been everywhere.
The collab between McDonald’s and K-Pop group BTS launched in the U.S. on May 26, 2021, and for a brief moment it felt like BTS and McNuggets were inseparable from each other. The BTS meal was sold out at nearly every McDonald’s. Artist Josiah Chua turned the packaging into these fire sneakers. And of course, there was that McNugget from the BTS meal that sold for nearly $100,000 on eBay because it looked like an Among Us character, which really makes me think McDonald’s should’ve shaped the BTS McNuggets to look like BTS. Can you imagine how much someone would pay for a McNugget that looks like Jungkook? Never underestimate how much people will pay for 1) food that looks like pop culture and 2) anything BTS-related.
The promotion is over now (at least in the U.S.), but there is still lots to learn about Chicken McNuggets. For example, it used to be mathematically impossible to order 43 McNuggets at any McDonald’s in the United Kingdom. Why? Because of a math theorem appropriately called the Chicken McNugget Theorem.
In honor of the BTS Chicken McNugget meal, I’m going to explain the Chicken McNugget Theorem and its proof. We’re going to go over:
- Where the Chicken McNugget Theorem Came From (hint: the 1800s)
- How to Prove the Chicken McNugget Theorem
- How to Apply the Chicken McNugget Theorem to the BTS Meal
Origin Story of the McNugget Theorem
In the United Kingdom, McDonald’s used to only sell Chicken McNuggets in packs of 6, 9 and 20 (and unfortunately, none of them looked like Jungkook). So of course, if you want 12 McNuggets, you can buy two packs of 6. On the other hand, you can’t buy 11 nuggets at a time if your only options are 6, 9 and 20: it’s impossible.
Mathematicians wanted to answer this question:
What is the largest number of McNuggets that you can’t buy with packs of 6, 9 and 20?
After putting in their blood, sweat, and tears, the mathematicians found that the answer is 43. You cannot buy 43 nuggets with packs of 6, 9 and 20, but you can buy any amount larger than 43.
The Chicken McNugget version of the problem probably originated in 1990 on the online newsgroup rec.puzzles, and it was printed in 1991 in Ilan Vardi’s book Computational Recreations in Mathematica. But the original version of the problem goes all the way back to the late 1800s, long before McDonald’s even existed.
The problem is often called the “Frobenius Problem,” after German mathematician Ferdinand Frobenius. He sometimes mentioned the problem in his lectures. It’s generally believed that the problem was first solved by the dope mathematician Joseph John Sylvester, who knew about the problem at least as early as 1882.
People studied the Frobenius Problem for almost a hundred years before the McNugget version came into existence, writing theorems and formulas around the problem. But now the McNugget version is upon us, so let’s get to McProving the Chicken McNugget Theorem.
An Overview of Some Modular Arithmetic Stuff
Before we prove the McNugget theorem, we’re going to need a few concepts from a part of math called modular arithmetic. This sounds big and complicated, but we’ll only need to understand modular arithmetic’s notation, as well as 3 concepts: greatest common divisor, relatively prime numbers, and multiplicative inverses.
Notation: If you divide 20 by 3, you get 6 with a remainder of 2. Modular arithmetic is a way of expressing that remainder. If I write this:
20≡2 (mod 3)
What that really means is that 20 has a remainder of 2 if you divide it by 3 (We also say that 20 is congruent to 2 mod 3).
Another way to say this is that if 20≡2 (mod 3), that means 20 = 3k+2 for some integer k. 20 is a multiple of 3 plus a remainder of 2. In this case, k=6 makes the equation true. In general:
a≡r(mod b) → a=kb+r for some integer k.
Greatest Common Divisor: You probably remember the greatest common divisor (sometimes called greatest common factor). The greatest common divisor of a and b is the largest number that divides both a and b. We will write this as gcd(a,b). For example, gcd(4,6)=2.
Relatively prime numbers: For many pairs of numbers, the gcd is 1. For example, 3 and 7 don’t have any common divisors except 1, so gcd(3,7)=1. When two numbers have a gcd of 1 we call those numbers relatively prime or coprime.
Multiplicative Inverses: So let’s say that ab≡1(mod m) for some numbers a, b, and m. When the product ab is congruent to 1 mod m, we say that a and b are multiplicative inverses of each other (mod m). For example, 10≡3(mod 7) and 5≡5(mod 7). 10*5 equals 50, and 50≡1(mod 7) so 10 and 5 are multiplicative inverses mod 7.
This will be important because, without going into too much detail, we know that a multiplicative inverse of a must exist (mod m) if a and m are relatively prime. For example, 9 and 5 are relatively prime. Therefore, we know that there is some number b such that 9b≡1 (mod 5). We know that 9 must have a multiplicative inverse mod 5 (in this case 9’s inverse is 4).
Proof of the Chicken McNugget Theorem
Let’s say McDonald’s sells two sizes of the nuggies. Call these sizes a and b. Also, assume a and b are relatively prime, meaning gcd(a,b)=1. The Chicken McNugget Theorem states the following:
Chicken McNugget Theorem: For relatively prime positive integers a and b, the number M=ab-a-b cannot be expressed as ax+by for any nonnegative integers x and y. Furthermore, any integer n>M can be represented as ax+by for some nonnegative integers x and y.
In other words, you can’t combine packs of a-sized and b-sized McNuggets to purchase (ab-a-b) McNuggets, but you can purchase any amount of McNuggets larger than (ab-a-b). If there exist nonnegative integers x,y so that ax+by=d, we’ll say that d is purchasable. If they don’t exist, we’ll say d is unpurchaseable.
There are two parts to proving the Chicken McNugget Theorem:
- Prove that ab-a-b is unpurchaseable.
- Prove that any n>ab-a-b is purchasable, meaning that there exist x,y≥0 such that xa+by=n.
Claim 1: ab-a-b is unpurchaseable.
We’re going to use a proof by contradiction. We start by assuming the opposite of the claim: assume that ab-a-b is purchasable. If ab-a-b is purchasable, that means there exist nonnegative numbers x and y such that ax+by=ab-a-b.
If we divide (ax+by) by a, we get a remainder of by. So (ax+by)≡by(mod a). Similarly, (ab-a-b)≡ -b(mod a). In turn, since ax+by=ab-a-b, this implies that by≡ -b(mod a).
Since b and a are relatively prime, b must have a multiplicative inverse mod a. Let’s call this inverse b’. If we multiply both sides of by≡ -b(mod a) by the inverse b’, this happens:
b’by≡ b’-b(mod a)
(b’b)y≡ -1(b’b)(mod a)
y≡ -1(mod a)
Similarly, if we divide both sides of the original equation (ax+by=ab-a-b) by b, we can reason that x≡-1 (mod b).
We know that x and y cannot be equal to -1, because we specified that they’re nonnegative (You can’t buy “-1 packs” of chicken nuggets). So the smallest possible value of x is b-1, and the smallest possible value of y is a-1. In other words, x≥b-1 and y≥a-1.
But if x≥b-1 and y≥a-1, it leads us to the following:
ab-a-b=ax+by ≥ a(b-1)+b(a-1)= ab-a+ab-b= 2ab-a-b > ab-a-b.
This would mean that ab-a-b > ab-a-b, which is clearly a contradiction. Since ab-a-b being purchasable leads to a contradiction, we know that ab-a-b must be unpurchasable.
Claim 2: Any n > ab-a-b is purchasable.
We now know that ab-a-b is unpurchaseable, but we also want to show that ab-a-b is the largest unpurchaseable number.
This proof is going to get more complicated than claim 1. To start, we have to invoke the name of a dead French guy. That’s right, it’s time for Bézout’s Identity:
Bézout’s Identity: If a and b are integers, then there exist integers x,y such that ax+by=gcd(a,b).
In this case, gcd(a,b)=1, so there exist some integers (x,y) such that ax+by=1. Multiplying both sides of the equation by n gives us nax+nby=n.
Let’s define x’=nx and y’=ny to make our formula a little cleaner: ax’+by’=n. Now I’m going to throw another claim at you:
Lemma: If (x’,y’) is a solution to ax’+by’=n, then (x’-kb, y’+ka) is also a solution for any integer k.
Proof: a(x’-kb)+b(y’+ka) = ax’-akb+by’+akb = ax’+by’=n.
Looking at the number x’-kb, k refers to the number of multiples of b that we add or subtract from x’. Note that we’re able to pick a specific value of k so that x’-kb is between 0 and b-1 (0≤ x’-kb ≤b-1). Let’s call this specific value k’, and we’ll define x”=x’-k’b and y”=y’+k’a. From the lemma, we know that (x”,y”) is a solution to ax+by=n. But we’re not quite done. We still have to prove that x” and y” are nonnegative.
x” is nonnegative by definition: we defined it as 0≤ x” ≤b-1. Now we need to show that y” is nonnegative. We know that n=ax”+by”, and n>ab-a-b. Putting those together, this happens:
ax”+by” > ab-a-b →
by”+b > ab-a-ax” →
b(y”+1) > a(b-1-x”)
We know that x”≤b-1, which means that b-1-x”≥0. The number a is positive, so this also means a(b-1-x”)≥0, which means b(y”+1)>0. Since b is positive, (y”+1)>0 and thus y”≥0. We’ve now shown that x” and y” are nonnegative, which means that the number n is purchasable. QED.
Applying the Chicken McNugget Theorem to the BTS Chicken McNugget Meal
McDonald’s only sold the BTS Chicken McNugget meal in packs of 10. But let’s say that McDonald’s decides to run the promotion again, and also starts selling a 7-piece meal, because, you know, BTS has 7 members.
If the BTS Chicken McNugget meal comes in packs of 7 and 10, you can’t buy 12 nuggets at a time, or 15 nuggets. On the other hand, you can buy 17 or 21 nuggets using packs of 7 and 10. What’s the largest number of BTS nuggets you can’t buy?
To answer that, we have the Chicken McNugget Theorem. The largest un-purchasable number is:
ab-a-b = (7*10)–7–10 = 53.
In other words, you can’t buy 53 nuggets at a time, but you can purchase any number larger than 53.
Other Nuggets About McNuggets
Here are some other things we know about the Chicken McNugget Theorem.
Why do a and b have to be relatively prime? Because otherwise there would be an infinite number of unpurchaseable amounts of McNuggets. As a simple example, in the United States, chicken McNuggets are sold in sizes of 4 and 6 (and 10 and 20). The numbers 4 and 6 are not coprime, as gcd(4,6)=2. It’s easy to see that you can’t buy any odd number of McNuggets with packs of 4 and 6. There is no largest unpurchaseable amount.
In general, if gcd(a,b)=d, then you can only buy n McNuggets if n≡0(mod d). In other words, you can only buy n McNuggets if n is divisible by d. For example, if gcd(a,b)=5, then you can’t buy any amount that has a remainder of 1,2,3, or 4 when you divide it by 5 (so a number like 31 would be unpurchaseable since 31≡1(mod 5)).
Basically, the Chicken McNugget Theorem is only interesting if a and b are coprime.
What about 3 McNugget sizes instead of 2? We went over the proof for 2 different McNugget sizes, but what about 3 sizes? Basically, there’s no explicit formula (and on a spring day in 1990, Frank J. Curtis published a proof that there’s no explicit formula).
But there are many algorithms to find the largest unpurchaseable amount for 3 McNugget sizes, the most notable being Rødseth’s algorithm (1978), Davison’s algorithm (1994), and Killingbergtrø’s algorithm (2000) (described here since Killingbergtrø’s original paper was only in Norwegian).
Is the Chicken McNugget Theorem useful? In short, yes! If you read my explanation of sexy primes, I mention that “sexy prime” is just a funny term without a lot of actual applications or consequences in math. The Chicken McNugget Theorem, however, is actually very useful.
In The Diophantine Frobenius Problem by Jorge L. Ramírez Alfonsin, the author explains that the problem has connections to algebraic geometry, error-correcting codes, vector spaces, and monomial curves (in short, it’s related to a lot of topics important to mathematicians).
Also, the problem can help us understand the time complexity of Shellsort. Basically, there’s a sorting algorithm called Shellsort, but we don’t know how long it takes the algorithm to run, at least not today. The exact time is still an unsolved problem. The Chicken McNugget Theorem helps us get a better sense of how long the algorithm takes.
Conclusion
The BTS Chicken McNugget meal is no longer with us, for now. But even though now we can only buy regularly-packaged Chicken McNuggets, streaming “Butter” and longing for a time past, we know from the Chicken McNugget Theorem that some amounts of McNuggets were always unpurchaseable. Some amounts of Chicken McNuggets were always out of our McGrasp.
If there’s a lesson here, other than how to prove the Chicken McNugget Theorem, it’s that math can show how complicated anything truly is deep down. Even something as small and simple as a Chicken McNugget.
