HMMT February

Solution 1. It suffices to consider the remainder $\bmod 100$. We start with the four numbers that have the same last two digits when squared: $0,1,25,76$. We can now go backwards, repeatedly solving equations of the form $x^{2} \equiv n(\bmod 100)$ where $n$ is a number that already satisfies the condition. 0 and 25 together gives all multiples of 5, for 20 numbers in total. 1 gives $1,49,51,99$, and 49 then gives $7,43,57,93$. Similarly 76 gives $24,26,74,76$, and 24 then gives $18,32,68,82$, for 16 numbers in total. Hence there are $20+16=36$ such numbers in total. Solution 2. An equivalent formulation of the problem is to ask for how many elements of $\mathbb{Z}_{100}$ the map $x \mapsto x^{2}$ reaches a fixed point. We may separately solve this modulo 4 and modulo 25. Modulo 4, it is easy to see that all four elements work. Modulo 25, all multiples of 5 will work, of which there are 5. For the remaining 25 elements that are coprime to 5, we may use the existence of a primitive root to equivalently ask for how many elements of $\mathbb{Z}_{20}$ the map $y \mapsto 2 y$ reaches a fixed point. The only fixed point is 0, so the only valid choices are the multiples of 5 again. There are $5+4=9$ solutions here. Finally, the number of solutions modulo 100 is $4 \times 9=36$.