CMI sub-question

This is just an application of the Chinese Remainder Theorem. We have $2^4 \cdot 5^4 | a(a-1),$ and since $a$ and $a-1$ are relatively prime, there are four cases: $2^4$ and $5^4$ divide $a$ , $2^4$ and $5^4$ divide $a-1$ , $2^4 | a$ and $5^4 | a-1$ , and $2^4 | a-1$ and $5^4 | a$ .

The first two cases give $a \equiv 0$ and $a \equiv 1$ mod $10000$ , so there are no solutions in the given set, and the second two cases give $a \equiv 9376$ and $a \equiv 625$ respectively via the Chinese Remainder Theorem (e.g. $a \equiv 0$ mod $16$ and $a \equiv 1$ mod $625$ if and only if $a \equiv 9376$ mod $10000$ ).

For a general $n$ the answer will depend on the number of primes dividing $n$ . If there are $k$ distinct primes dividing $n$ , there will be $2^k - 2$ such values of $a$ (we subtract 2 because we are always excluding the solutions $0$ and $1$ ). The easiest way to see this is probably to ape the above argument in the case when $n$ is divisible by three primes, and see how many possibilities there are. One can write out a proof, but it would be more illuminating to play with a couple of examples to see why this statement is true.

For $10000|(a^2-a)\quad \Rightarrow 2^45^4|[a(a-1)]$ .

We note that $a(a-1)$ is a product of two consecutive integers, one odd and the other even. The smallest possible odd integer would be $5^4=625$ , and we note that $2^4|(625-1)=16|624$ . Therefore, the first $a_1 = 625$ .

The following $a$ s must be around odd multiple of $625$ . Since $624 \equiv 0 \pmod{16}$ , $a_2$ is around $15\times 625$ because $15\times 625 = 15(624+1) \equiv 15 \pmod{16}$ $\Rightarrow a_2 = 15(625)+ 1= 9376$ .

$\Rightarrow a_2-a_1 = 9376 - 625 = \boxed{8751}$

We note that $a_3$ is around $17(625) = 17(624+1) \equiv 1 \pmod{16}$ $\Rightarrow a_3 = 17(625)$ .

Therefore,

$\begin{array} {rl} a_1 = & 1 \times 625 \\ a_2 = & 15 \times 625 + 1 \\ a_3 = & 17 \times 625 \\ a_4 = & 31 \times 625 + 1 \\ a_5 = & 33 \times 625 \\ ... \end{array} \Rightarrow a_k = \begin{cases} [16(k-1)+1]\times 625 & \text{ if k is odd} \\ \\ [16(k-1)+1]\times 625 + 1 &\text{ if k is even} \end{cases}$

Therefore, for $n \ge 9375$ the number $k$ of such $a$ is given by:

$k = \left \lceil \dfrac{\left \lfloor \dfrac {n}{625} \right \rfloor}{16} \right \rceil + 1$

Here's how I did it:

Through some reasoning, you can arrive at the conclusion that $a$ has to end in either 5 or 6.

If a ends in 5, then a-1 ends in 4 and the factor of 16 lies entirely with a-1 and the factor of 625 lies entirely with a. And vice versa for the case when a ends in 6.

So we only need to hunt for odd multiples of 625. We find that 625 and 9376 are the two values of a by trial and error. So the difference is 8751.

There's an easier way to solve it and I know that. But this is how I did it in the exam hall. So please post a solution to this with the general case.