Chicken McNugget Theorem – Bezout’s Identity

May 18, 2021 Shreyas Comments 1 comment

Given an unlimited number of 2 and 5 dollar bills, what all dollar values can be created? Clearly all multiples of 2 and 5 can be created, but they can also be combined to form many other values such as 7 (2 + 5), 13 (5 + 4 * 2) and so on. In fact, there are only a finite number of values that cannot be created in such a way by combining 2 and 5 dollar bills, and in general there are only finitely many values that cannot be created by combining hypothetical $m$ dollar bills and $n$ dollar bills where $m$ and $n$ are relatively prime. Equivalently, there are only finitely many values of $x$ such that the equation

(1) $\begin{equation*} a*m + b*n = x \end{equation*}$

has no solution for non-negative integers $a$ and $b$ . In this post I’ll characterize these values and prove the Chicken McNugget theorem for the largest such value.

Consider an arbitrary positive integer $x_0$ . To construct a solution to the equation

$\begin{equation*} a*m + b*n = x_0 \end{equation*}$

we consider both sides $\mod m$ and see that

$\begin{equation*} b*n = x_0 \mod m \end{equation*}$

Now we need to find a value such that $b*n$ and $x_0$ leave the same reminder when divided by $n$ , or alternatively their difference is a multiple of $m$ . Consider the set of numbers {0, n, 2n, 3n, …, (m – 1)n}. Since $m$ and $n$ are relatively prime, this set is identical to {0, 1, 2, 3, …, (m – 1)} $\mod m$ , so the first $(m - 1)$ multiples of $n$ together with 0 cover all possible congruences $\mod m$ . This means that no matter what $x_0$ is, we will always find exactly one $b$ in in the set {0, 1, 2, 3, …, (m – 1)} such that

$\begin{equation*} b*n = x \mod m \end{equation*}$

Let’s call this specific value $b_0$ . Then we want to find some value of $a$ such that

$\begin{equation*} a*m + b_0*n = x_0 \end{equation*}$

$\begin{equation*} a*m = x_0 - b_0*n \end{equation*}$

Since the right hand side is a multiple of $m$ by our construction, it can be written as $k*m$ for some integer $k$ . The equation is reduced to

$\begin{equation*} a*m = k*m \end{equation*}$

$\begin{equation*} a = k \end{equation*}$

This shows that we can always find an integer $a$ that will constitute a solution to our equation along with $b_0$ . However, there is no guarantee that this value of $a$ will be non-negative, as was required for valid solutions. This means that any value of $x_0$ such that

$\begin{equation*} k*m = x_0 - b_0 * n \end{equation*}$

is negative will not yield a valid solution to our original problem.

Rearranging and going back to our definition of $b_0$ , we see that the values of $x_0$ that yield no solution can be written as $b_0*n + k*m$ , where $k$ is negative and $b_0$ is in the set {1, 2, 3, …, {m – 1)} ( $b_0$ cannot be 0 because then we’d be left with $x_0 = k * m$ which is negative). Using different variables, we can state that our original equation has no solution if and only if $x$ can be written as $i*n - j*m$ , where $i$ and $j$ are positive integers and $i < m$ . The maximum such value will be obtained by maximizing $i$ and minimizing $j$ . So $i = m - 1$ and $j = 1$ , yielding

(2) $\begin{equation*} (m - 1)n - m = mn - m - n \end{equation*}$

which is the statement of the Chicken McNugget theorem.

Going back to our original example, we see that the largest value that cannot be attained using 2 and 5 dollar bills is $2 * 5 - 2 - 5 = 3$ .

Using another example, suppose you are at a store buying bananas, and bananas come in bunches of 3 or 5. To find the number of bananas that are impossible to obtain, we let $m = 5$ and $n = 3$ and apply the result above, considering multiples of 3 from 1 * 3 to (5 – 1) * 3, subtracting multiples of 5 from them and stopping before we reach a negative value. We cannot subtract any multiple of 5 from 1 * 3 without reaching a negative value so we move on. 2 * 3 yields one value, $2 * 3 - 5 = 1$ . 3 * 3 also yields one value, $3 * 3 - 5 = 4$ . 4 * 3 yields two values, $4 * 3 - 5 = 7$ and $4 * 3 - 10 = 2$ . Thus, the only numbers of bananas that are impossible to obtain are 1, 2, 4 and 7, and every number larger than 7 is possible to obtain (at least until the store runs out of them!)

While deriving the solution, we also noted that the only thing that is stopping a solution from existing for the equation (1) for all integers $x$ is our restriction that $a$ and $b$ have to be non-negative. Otherwise we could simply plug our value for $k$ into the equation for $a$ without worring about it being negative. This means that if we allow $a$ and $b$ to be negative, our original equation has solutions for every integer $x$ (not just every non-negative integer $x$ , as we can find solutions for negative $x$ by finding solutions for positive $x$ and simply replacing $a$ and $b$ with $-a$ and $-b$ ). We can also extend this to pairs $m$ and $n$ that are not relatively prime.

We now go back to the equation (1), but this time allowing $a$ and $b$ to be any integers, $x$ to be any integer and $m$ and $n$ to share common factor(s). Clearly, the left hand side is divisible by $gcd(m, n)$ so the $x$ must also be. Then we can write $x$ as $gcd(m, n) * y$ for some integer $y$ . Dividing both sides by $gcd(m, n)$ , we get

(3) $\begin{equation*} a * (\frac{m}{gcd(m, n)}) + b * (\frac{n}{gcd(m, n)}) = y \end{equation*}$

Since $\frac{m}{gcd(m, n)}$ and $\frac{n}{gcd(m, n)}$ are relatively prime (we have removed any of their common prime factors when dividing by their gcd), this new equation has solution for all y. This means that our original x can be written as $gdc(m, n) * y$ for any integer $y$ , or that our original equation has solutions for any $x$ that is a multiple of $gcd(m, n)$ , a result known as Bezout’s Identity.

Shreyas' blog – Ignited Minds

I love math and science. This is a blog about things I think of, or work on, in my spare time.

Chicken McNugget Theorem – Bezout’s Identity

May 18, 2021 Shreyas Comments 1 comment

One thought on “Chicken McNugget Theorem – Bezout’s Identity”

Leave a Reply Cancel reply