Problem 8
When asked to make cupcakes for a local bake sale, you lost track of the number you've currently made.
Instead of counting every cupcake one by one, you decide to put the cupcakes into groups and look at the remainders.
When doing so you notice that you have remainders of 1, 2, 3, 4, and 5 when dividing into groups of 11, 3, 7, 5, and 13 respectively.
Determine how many cupcakes you actually have.
Solution
Note that many approaches to this problem are possible. Here is one particular approach.
In the study of number theory, we say that "a divides b" if there exists an integer c such that b = ca. The common
symbol used for this is "a | b".
Let x be the number of cupcakes.
Thus by the problem statement, we know that x must satisfy the following system of equations.
x = 11a + 1
x = 3b + 2
x = 7c + 3
x = 5d + 4
x = 13e + 5
where a, b, c, d, and e are integers. If we subtract the remainder over to the left hand side, we can now use the divide statement mentioned above.
Thus we have the following:
x - 1 = 11a implies that 11 | x - 1
x - 2 = 3b implies that 3 | x - 2
x - 3 = 7c implies that 7 | x - 3
x - 4 = 5d implies that 5 | x - 4
x - 5 = 13e implies that 13 | x - 5
However, we can add the divisor to the right hand side and the divide statement still holds. Thus
11 | x + 10
3 | x + 1
7 | x + 4
5 | x + 1
13 | x + 8
If we look at the 2nd and 4th divide statements, we have that both 3 and 5 divide x + 1. But as the greatest common divisor of 3 and 5 is 1,
it must be the case that 15 divides x + 1.
Now looking at the 1st and 5th divide statement, we see that we can add 11 and 13 respectively to the right hand sides (thus not changing the overall divide statement) and we get that both 11 and 13 divide x + 21. Again as the greatest common divisor of 11 and 13 is 1, we can replace the two statements with a stronger one, namely that 143 | x + 21.
Thus our original set of 5 divide statements is now cut down to the following:
15 | x + 1
143 | x + 21
7 | x + 4
Using a similar approach, we can combine the 1st and 3rd by adding 45 and 42 respectively to get that both 15 and 7 divide x + 46.
Thus with only two statements left, we can convert them to the linear form as
x + 21 = 143a OR x = 143a - 21
x + 46 = 105b OR x = 105b - 46
With the linear forms, we can choose different values of a and use that given x value to see if a remainder of 46 occurs when divided by 105.
Luckily using the original 4th statement, "a remainder of 4 when grouped into 5s", we know that x has to either end in a 4 or 9.
So the smallest value of a is 5 and x = 694. But this does not leave a remainder of 46 when divided by 105,
so we continue by adding 715 to x until the desired outcome is achieved. The reason we can add by 715 is by adding 143 one, two, three, or four
times will not have a ones digit as being either a 4 or 9.
A couple additions of 715 yields the following list:
694, 1409, 2124, 2839, 3554, 4269, 4984, 5699, 6414, 7129, 7844, 8559, 9274, 9989, 10704, 12134, ...
As the first number listed above that leaves a remainder of 46 upon division of 105 is x = 12134, that is the minimum number of cupcakes made.
Also any number of the following form will also work x = 15015y + 12134, as 11, 3, 7, 5, and 13 are all primes and 15015 = 11*3*7*5*13.
An easier solution can be achieved by using modular arithmetic and the Chinese Remainder Theorem.
For those interested in the CRT, visit
Chinese Remainder Theorem on Wolfram
