125 and 512; 256 and 625

I claim that the following three statements are equivalent for a positive integer $n$ :

1. There exist integers $a,b,c,d$ with $(c,d) = 1$ such that $100a + b = c^n$ and $10b + a = d^n$ .

2. There exists an integer $u$ such that $u^n \,\equiv \, 10$ modulo $999$ .

3. There exists an integer $v$ such that $v^n \,\equiv \, 100$ modulo $999$ .

If Condition (1) is true, then $10c^n - d^n = 999a \,\equiv\, 0$ modulo $999$ . If $(c,999) > 1$ , let $p$ be a common prime factor of $c$ and $999$ (either $3$ or $37$ ). Then $p$ also divides $d^n$ , and hence $p$ divides $d$ , so that $c$ and $d$ are not coprime. Thus we deduce that $c$ and $999$ are coprime, so there exists an integer $e$ such that $ce \, \equiv\, 1$ modulo $999$ , and then $(de)^n \,\equiv\,10$ modulo $999$ . Hence Condition (2) is true.

If Condition (2) is true, so that $u^n \equiv 10$ modulo $999$ for some $u$ , then $(u^2)^n \,=\, (u^n)^2 \,\equiv\, 100$ modulo $999$ , and hence Condition (3) is true.

If Condition (3) is true, so that $v^n \equiv 100$ modulo $999$ for some $v$ , put $c=v$ and $d=1$ . Certainly $c$ and $d$ are coprime. Then $\begin{array}{rcl} 10c^n - d^n & = & 10v^n - 1 \; \equiv \; 10\times100 - 1 \; \equiv \; 0 \\ 100d^n - c^n & = & 100 - v^n \; \equiv \; 0 \end{array}$ modulo $999$ , and hence we can find integers $a,b$ such that $10c^n - d^n \; = \; 999a \qquad 100d^n - c^n \; = \; 999b$ Thus $\begin{array}{rcl} 999(100a + b) & = & 100(10c^n - d^n) + (100d^n - c^n) \; = \; 999c^n \\ 999(10b + a) & = & 10(100d^n - c^n) + 10c^n - d^n \; = \; 999d^n \end{array}$ so that $100a+b = c^n$ and $10b+a = d^n$ , and Condition (1) is satisfied.

Since $10^3 \,=\, 1000 \,\equiv\, 1$ modulo $999$ , we see that $10^{3a+1} \,\equiv\,10$ for all $a \ge 0$ , and hence Condition (2) is satisfied for all integers $n \equiv 1$ modulo $3$ . Also $10^{3a+2} \,\equiv\, 100$ for all $a \ge 0$ , and hence Condition (3) is satisfied for all integers $n \equiv 2$ modulo $3$ .

Since $625^3 \,\equiv\, 10$ modulo $999$ (thank you, Excel!), we deduce that $625^{9a+3} \,\equiv\, 10$ and $625^{9a+6} \,\equiv\, 100$ modulo $999$ , and so Conditions (2) and (3) are satisfied for all integers $n \equiv 3$ and $n \equiv 6$ modulo $9$ respectively.

So far, we have shown that Condition (1) holds for all integers $n$ except multiples of $9$ . I claim that Condition (1) does not hold if $n$ is a multiple of $9$ . Suppose that Condition (1) held for some $n = 9a$ . Then we can find an integer $u$ such that $u^{9a} \equiv 10$ modulo $999$ . This would imply that $(u^a)^9 \equiv 10$ modulo $999$ , and hence that $v^9 \equiv 10$ modulo $999$ for some integer $v$ . But (thank you, Excel, again) we can easily check that $10$ is not a ninth power modulo $999$ .

Thus we deduce that Condition (1) holds precisely for those integers which are not multiples of $9$ . There are $111$ multiples of $9$ between $1$ and $999$ , and hence there are $888$ integers $n$ between $1$ and $999$ inclusive for which Condition (1) holds.