Chicken McNugget Theorem

From AoPSWiki

The Chicken McNugget Theorem states that for any two relatively prime positive integers $m,n$ , the greatest integer that cannot be written in the form $am + bn$ for nonnegative integers $a, b$ is $mn-m-n$ .

Proof

Consider the integers $\pmod{m}$ . Let $R = \{0, n, 2n, 3n, 4n ... (m-1)n\}$ . Note that since $m$ and $n$ are relatively prime, $R$ is a Complete residue system in modulo $m$ .

Lemma: For any given residue class $S \pmod{m}$ , call $r$ the member of $R$ in this class. All members greater than or equal to $r$ can be written in the form $am+bn$ while all members less than $r$ cannot for nonnegative $a,b$ .

Proof: Each member of the residue class can be written as $am + r$ for an integer $a$ . Since $r$ is in the form $bn$ , this can be rewritten as $am + bn$ . Nonnegative values of $a$ correspond to members greater than or equal to $r$ . Negative values of $a$ correspond to members less than $r$ . Thus the lemma is proven.