Difference between revisions of "Chicken McNugget Theorem"
m |
m |
||
| Line 5: | Line 5: | ||
Lemma: | Lemma: | ||
| − | For any given residue class <math>S \pmod{ | + | 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 22:03, 22 July 2008
The Chicken McNugget Theorem states that for any two relatively prime positive integers 
, the greatest integer that cannot be written in the form 
for nonnegative integers 
is 
.
Proof
Consider the integers 
. Let 
. Note that since 
and 
are relatively prime, 
is a Complete residue system in modulo .
Lemma:
For any given residue class 
, call 
the member of in this class. All members greater than or equal to can be written in the form 
while all members less than cannot for nonnegative 
.
Proof:
Each member of the residue class can be written as
for an integer 
. Since is in the form 
, this can be rewritten as .
Nonnegative values of correspond to members greater than or equal to . Negative values of correspond to members less than . Thus the lemma is proven.
The largest member of is 
, so the largest unattainable score 
is in the same residue class as .
The largest member of this residue class less than is 
and the proof is complete.
See Also
This article is a stub. Help us out by expanding it.
