08-10-2026, 11:33 AM
Chicken McNugget Theorem explained
Summary
The Codeforces article explains the Chicken McNugget Theorem, a useful result in number theory for determining which integers can be expressed as nonnegative combinations of two relatively prime positive integers $m$ and $n$. It states that the largest integer that cannot be written as $am+bn$ is $mn-m-n=(m-1)(n-1)-1$, where $a,b\ge0$, and that every larger integer can be represented in this way. It also gives the number of positive integers that cannot be represented as exactly $\frac{(m-1)(n-1)}{2}$.
For example, using $m=2$ and $n=5$, the impossible values are $1$ and $3$, while every integer greater than $3$ can be formed. The theorem is particularly useful in competitive programming problems such as Codeforces 1526B – I Hate 1111, where recognizing this mathematical structure can replace a more complicated approach.
ARTICLE
Summary
The Codeforces article explains the Chicken McNugget Theorem, a useful result in number theory for determining which integers can be expressed as nonnegative combinations of two relatively prime positive integers $m$ and $n$. It states that the largest integer that cannot be written as $am+bn$ is $mn-m-n=(m-1)(n-1)-1$, where $a,b\ge0$, and that every larger integer can be represented in this way. It also gives the number of positive integers that cannot be represented as exactly $\frac{(m-1)(n-1)}{2}$.
For example, using $m=2$ and $n=5$, the impossible values are $1$ and $3$, while every integer greater than $3$ can be formed. The theorem is particularly useful in competitive programming problems such as Codeforces 1526B – I Hate 1111, where recognizing this mathematical structure can replace a more complicated approach.
ARTICLE
┌────────────────────────────────┐
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘
│ KONSTANTINOS MICHAILIDIS │
└────────────────────────────────┘