Macedonian Junior Mathematical Olympiad

We will use the following well-known results: Property. 1. Every natural number, when divided by $3$ or $9$ gives the same remainder as the sum of its digits. Property. 2. A square of a natural number, when divided by $3$ gives the remainder $0$ or $1$. And we will show this property. Property. 3. After any step, the remainder by division by $9$ is invariant. Proof. Let, after some step, the number $A=\overline{a_n{a}_{n-1}\dots a_1{a}_0}$ be obtained. According to Property. 1, we have $$A=\overline{a_n{a}_{n-1}\dots a_1{a}_0}\equiv a_n+a_{n-1}+\cdots +a_1+a_0(\mathrm{mod}9).$$ After deleting the first and last digit we get the number $\overline{a_{n-1}\dots a_1}$. Hence, after one step, the number $B=\overline{a_{n-1}\dots a_1}+a_n+a_0$ is obtained. Now we have $$B=\overline{a_{n-1}\dots a_1}+a_n+a_0\equiv a_{n-1}+\cdots +a_1+a_n+a_0(\mathrm{mod}9)\text{ i.e. }A\equiv B(\mathrm{mod}9).$$ This finishes the proof of Property. 3.

a) If after a finite number of steps we get the number $A$, then according to Property. 3, $A$ will give the same remainder when divided by $3$ as the number $2009^{2009^{2009}}$. We get $2009\equiv 2\equiv -1(\mathrm{mod}3)$, which implies $$2009^{2009^{2009}}\equiv (-1{)}^{2009^{2009}}\equiv -1\equiv 2(\mathrm{mod}3).$$ ---

According to Property. 3 and the above-said we get that $A\equiv 2(\mathrm{mod}3)$, so according to Property. 2, it cannot be a perfect square.

b) If, after a finite number of steps, the one-digit number $a$ is obtained, then according to Property. 3, we get that $a\equiv 2009^{2009^{2009}}(\mathrm{mod}9)$. We have $2009\equiv 2(\mathrm{mod}9)$ so $$2009^{2009^{2009}}\equiv 2^{2009^{2009}}(\mathrm{mod}9)\text{ and clearly }{2}^3\equiv -1(\mathrm{mod}9).$$ Then $$2009^{2009}\equiv 2^{2009}\equiv (-1{)}^{2009}\equiv -1\equiv 2(\mathrm{mod}3)$$ i.e. $2009^{2009}=3k+2$, where $k$ is an odd natural number. Now we have $$2009^{2009^{2009}}\equiv 2^{3k+2}=(2^3{)}^k\cdot 4\equiv (-1)\cdot 4\equiv 5(\mathrm{mod}9)$$ from where it is clear that $a=5$.