For how many positive integers $n<1000$ , do there exist integers $a,$ $b,$ $c,$ and $d,$ that satisfy the following conditions:

$\begin{cases} 100a+b =c^n\\ 10b+a=d^n\\ gcd(c,d)=1? \end{cases}$

**
Details and assumptions
**

There are no restrictions on the values of $a$ and $b$ .

The answer is 888.

**
This section requires Javascript.
**

You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.

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

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

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

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.