Difference between revisions of "Chicken McNugget Theorem"

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

Revision as of 23:03, 22 July 2008

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.

The largest member of $R$ is $(m-1)n$, so the largest unattainable score $p$ is in the same residue class as $(m-1)n$.

The largest member of this residue class less than $(m-1)n$ is $(m-1)n - m = mn - m - n$ and the proof is complete.

See Also

This article is a stub. Help us out by expanding it.