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.