Solution set to exponential in congruence

Question

For which $n>0$ does $x^{2^n} \equiv 7 (mod \ 9)$ have a solution?

It might be useful to start $x^{2^n} \equiv 16 (mod \ 9)$ but how should one proceed?

Any hints would be appreciated. Thanks!

Answer 1

In general, if $x^2\equiv a\pmod 9$ has a solution (with $a\not\equiv 0\pmod 3$) then $x^2\equiv -a\pmod 9$ has no solution. Therefore we need only follow one "successful" branch:

• $x^2\equiv 7\pmod 9\iff x\equiv \pm4\pmod 9$
• $x^2\equiv 4\pmod 9\iff x\equiv \pm2\pmod 9$
• Now we're back at the beginning: $x^2\equiv -2\pmod 9\iff x\equiv \pm4\pmod 9$

Alternatively, if we repeatedly square $7$, we obtain $$ 7, 4, 7, 4, 7, \ldots$$ In other words, $$ 7^{2^n}\equiv 7\pmod 9\qquad\text{if }2\mid n$$ $$ 4^{2^n}\equiv 7\pmod 9\qquad\text{if }2\not\mid n$$