Difference between revisions of "Chicken McNugget Theorem"
Chickendude (talk | contribs) (Added proof. Needs some formatting.) |
m |
||
| Line 9: | Line 9: | ||
Proof: | Proof: | ||
Each member of the residue class can be written as | Each member of the residue class can be written as | ||
| − | <math>am + r</math> for an integer <math>a</math>. Since <math>r</math> is in the form <math>bn</math>, this can be rewritten as <math>am + | + | <math>am + r</math> for an integer <math>a</math>. Since <math>r</math> is in the form <math>bn</math>, this can be rewritten as <math>am + bn</math>. |
Nonnegative values of <math>a</math> correspond to members greater than or equal to <math>r</math>. Negative values of <math>a</math> correspond to members less than <math>r</math>. Thus the lemma is proven. | Nonnegative values of <math>a</math> correspond to members greater than or equal to <math>r</math>. Negative values of <math>a</math> correspond to members less than <math>r</math>. Thus the lemma is proven. | ||
Revision as of 21:11, 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.
