The CEMC Gauss 8 has historically been a very easy 8th grade test. For example, Problem 5 on the 2017 exam was ”44×22 is equal to…”. So this question sort of came as a surprise when I heard it.
The brute-force solution might look something like this: We need to figure out how many multiples of 10,000 we can add on to 2025 so our number is still divisible by 2013. This is equivalent to solving the following congruence relation:
10000k+2025⇒10000k≡0(mod2013)≡−2025(mod2013)
So this is equivalent to finding the modular inverse of 10000 mod 2013. Note that you’re allowed to use a calculator on this exam, so this isn’t as hard as you might think. Euclidean Algorithm gives us:
This struck me as a tall ask for a test where just a few problems earlier asks basic multiplication facts. How many 8th graders know how to compute large modular inverses using Extended Euclidean Algorithm? So what’s going on here? My first inclination was to note the prime factorization of 2013:
2013=3⋅11⋅61
61 is clearly the most difficult of the three factors to work with, so let’s focus on that. Since we’re sort of trying to see how many multiples of 10000 we can add to 2025, I looked at how close 61 was to dividing 10000. Interestingly, 164⋅61=10004, which is a really cool piece of information. If we start with any number and instead of adding 10004 we add 10000, this will have the effect of reducing whatever remainder mod 61 we started with by 4. Since 2025≡12(mod61), we can add exactly 30000 to this to end up with a number that’s exactly divisible by 61.
Cool, so 32025 is divisible by 61. It’s also coincidentally divisible by 3. It is not, however, divisible by 11. How do we solve this? Well if we continue to add multiples of 610000 our number will continue to be divisible by 61 and eventually be divisible by both 3 and 11. We can be more precise though: adding one multiple of 610000 breaks our divisibility by 3 unless we add three multiples of 610000, or 1830000. In other words all numbers of the following form are divisible by 3 and 61:
1830000k+32025≡0(mod3⋅61)
Finally, we could note that 32025≡4(mod11) and 1830000≡7(mod11) and realize we only need to add one instance of 1830000 to arrive at our answer. Or since, you know, we’re allowed to use a calculator we can just try incrementing our 32025 by 1830000 until we get something that works. And guess what: we only need to try once! 1862025 is indeed divisible by 2013.
I almost like my second solution, but I don’t like how we had to stumble upon the magic piece of information 164⋅61=10004. Here’s another way to proceed using only elementary ideas. As before, we want to find the smallest number ending in 2025 that is divisible by 61. To do this, we can use a lesser-known divisibility rule for 61:
Let’s denote the unknown leading digits by x, so our number is of the form x2025. We’ll apply the rule step by step:
Update: After shopping this problem around to a couple people, my friend Jeff came up with the best idea. Turn the problem into a multiplication cryptarithm:
