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 23: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.