We now limit the values of to all integers, which limits the values of to. Again, because is the least number congruent to itself that is purchasable, and because and, is not purchasable. This implies that is purchasable, and that.
Therefore, and, so is purchasable.Ĭase 2. is a permuted residue, and a result of the lemma in Proof 2 was that a permuted residue is the least number congruent to itself that is purchasable. This implies that is not purchasable, and that. Proof: Because every number is congruent to some residue of permuted by, we can set for some. Lemma: For any integer, exactly one of the integers, is not purchasable. This corollary is based off of Proof 2, so it is necessary to read that proof before this corollary. Putting it all together, we can say that for any coprime and, is the greatest number not representable in the form for nonnegative integers. All numbers are congruent to some, and thus all numbers greater than are purchasable. Any number greater than this and congruent to some is purchasable, because that number is greater than. , so, which shows that is the greatest number in the form. Another result of this Lemma is that is the greatest number that is not purchasable. This means that because is purchasable, every number that is greater than and congruent to it is also purchasable (because these numbers are in the form where ). Therefore, we have a contradiction, and is the least purchasable number congruent to. However, we defined to be a positive integer, and all positive integers are greater than or equal to. We can say that for some positive integer, and substitute to get. This can be rearranged into, which implies that is a multiple of (since ). If this is purchasable, we can say for some nonnegative integers. Proof: Any number that is less than and congruent to it can be represented in the form, where is a positive integer. Lemma: For any nonnegative integer, is the least purchasable number. Each of these permuted residues is purchasable (using the definition from Proof 1), because, in the form, is and is the original residue. Since, by the cancellation rule, that reduces to, which is a contradiction."īecause and are coprime, we know that multiplying the residues of by simply permutes these residues. In other words,Ĭlearly none of the for are divisible by, so it suffices to show that all of the elements in are distinct. Then, we claim that the set, consisting of the product of the elements of with, taken modulo, is simply a permutation of. We start with this statement taken from Proof 2 of Fermat's Little Theorem: Since both are positive, the maximum is achieved when and so that. We would like to find the maximum of this set. Thus the set of non-purchasable integers is. If, then if and if, hence at least one coordinate of is negative for all. Proof: If, then we may simply pick so is purchasable. Proof: By the division algorithm, there exists one and only one such that. For any integer, there exists unique such that. Since and are coprime and divides, divides and. Proof: By Bezout's Lemma, there exist integers such that.
Note that all purchasable integers are nonnegative, thus the set of non-purchasable integers is nonempty. We would like to prove that is the largest non-purchasable integer. An integer will be called purchasable if there exist nonnegative integers such that. The Chicken McNugget Theorem has also been called the Frobenius Coin Problem or the Frobenius Problem, after German mathematician Ferdinand Frobenius inquired about the largest amount of currency that could not have been made with certain types of coins.ĭefinition. Math enthusiasts were curious to find the largest number of nuggets that could not have been bought with these packs, thus creating the Chicken McNugget Theorem (the answer worked out to be 151 nuggets). Originally, McDonald's sold its nuggets in packs of 9 and 20. However, the most popular by far remains that of the Chicken McNugget. There are many stories surrounding the origin of the Chicken McNugget theorem.
0 kommentar(er)
