Difference between revisions of "Chicken McNugget Theorem"
(see also, category) |
Chickendude (talk | contribs) (Added proof. Needs some formatting.) |
||
| Line 1: | Line 1: | ||
The '''Chicken McNugget Theorem''' states that for any two [[relatively prime]] [[positive integer]]s <math>m,n</math>, the greatest integer that cannot be written in the form <math>am + bn</math> for [[nonnegative]] integers <math>a, b</math> is <math>mn-m-n</math>. | The '''Chicken McNugget Theorem''' states that for any two [[relatively prime]] [[positive integer]]s <math>m,n</math>, the greatest integer that cannot be written in the form <math>am + bn</math> for [[nonnegative]] integers <math>a, b</math> is <math>mn-m-n</math>. | ||
| + | |||
| + | ==Proof== | ||
| + | Consider the integers <math>\pmod{m}</math>. Let <math>R = \{0, n, 2n, 3n, 4n ... (m-1)n\}</math>. Note that since <math>m</math> and <math>n</math> are relatively prime, <math>R</math> is a [[Complete residue system]] in modulo <math>m</math>. | ||
| + | |||
| + | 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>. | ||
| + | |||
| + | Proof: | ||
| + | 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 + br</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. | ||
| + | |||
| + | The largest member of <math>R</math> is <math>(m-1)n</math>, so the largest unattainable score <math>p</math> is in the same residue class as <math>(m-1)n</math>. | ||
| + | |||
| + | The largest member of this residue class less than <math>(m-1)n</math> is <math>(m-1)n - m = mn - m - n</math> and the proof is complete. | ||
==See Also== | ==See Also== | ||
Revision as of 18:07, 27 April 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.
