CEMC 2025 Gauss 8 Problem 23

2025 CEMC Gauss 8 Problem 23

What is the sum of the digits of the smallest positive integer that ends in $2025$ and is divisible by $2013$?

Theoretical Solution

The CEMC Gauss 8 has historically been a very easy 8th grade test. For example, Problem 5 on the 2017 exam was ”$44\times 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:

$$\begin{align*} 10000k + 2025 &\equiv 0 \pmod{2013}\\ \Rightarrow\quad 10000k &\equiv -2025 \pmod{2013} \end{align*}$$

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:

$$\begin{align*} 10000 &= 4 \times 2013 + 1948 \\ 2013 &= 1 \times 1948 + 65 \\ 1948 &= 29 \times 65 + 63 \\ 65 &= 1 \times 63 + 2 \\ 63 &= 31 \times 2 + 1 \\ 2 &= 2 \times 1 + 0 \end{align*}$$

Back substitution gives:

$$\begin{align*} 1 &= 63 - 31 \cdot 2 \\ &= 63 - 31 \cdot (65 - 1 \cdot 63) = 32 \cdot 63 - 31 \cdot 65 \\ &= 32 \cdot (1948 - 29 \cdot 65) - 31 \cdot 65 = 32 \cdot 1948 - 959 \cdot 65 \\ &= 32 \cdot 1948 - 959 \cdot (2013 - 1 \cdot 1948) = 991 \cdot 1948 - 959 \cdot 2013 \\ &= 991 \cdot (10000 - 4 \cdot 2013) - 959 \cdot 2013 = 991 \cdot 10000 - 4923 \cdot 2013 \end{align*}$$

Since $1 = 991 \cdot 10000 - 4923 \cdot 2013$, the modular inverse of $10000$ mod $2013$ is $991$. Putting this back into our original congruence gives:

$$\begin{align*} \quad 10000k &\equiv -2025 \pmod{2013} \\ \quad k &\equiv 991 \cdot (-12) \pmod{2013} \\ \quad k &\equiv -11892 \pmod{2013} \\ \quad k &\equiv 186 \pmod{2013} \end{align*}$$

So $k=186$ and our number final number is $1862025$, the sum of the digits being $\boxed{24}$.

Contest Solution

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\cdot11\cdot61$$

$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\cdot61=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\equiv12\pmod{61}$, 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\equiv0\pmod{3\cdot61}$$

Finally, we could note that $32025\equiv4\pmod{11}$ and $1830000\equiv7\pmod{11}$ 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.

Alternative Idea

I almost like my second solution, but I don’t like how we had to stumble upon the magic piece of information $164\cdot61=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 $\overline{x}2025$. We’ll apply the rule step by step:

$$\begin{align*} \overline{x}2025 &\rightarrow \overline{x}202 - 6 \cdot 5 = \overline{x}172 \\ &\rightarrow \overline{x}17 - 6 \cdot 2 = \overline{x}05 \\ &\rightarrow \overline{x}0 - 6 \cdot 5 = \overline{x}0 - 30 \\ &\Rightarrow x - 3 \equiv 0 \pmod{61} \\ &\rightarrow x \equiv 3 \pmod{61} \end{align*}$$

Thus $32025$ is the smallest number divisible by $61$ and we proceed as before.

Conclusion

I’m still unsatisfied with this and I feel like I’m missing a better way to approach this problem as an 8th grader in a time-sensitive situation.