Hello there,

my book is asking to do the following problem :

Isn't there a typo in the last word, because I know about ways to take roots over $\displaystyle \mathbb{Z}/p\mathbb{Z}$ when $\displaystyle p$ is a prime, which is not the case here, and as I looked over the internet, it seems a "hard" problem to take roots if $\displaystyle p$ is a composite ?Given $\displaystyle x^a \equiv x \pmod{n}$, design an algorithm to find $\displaystyle x$ in polynomial time know $\displaystyle a$ and $\displaystyle n$, and given that the modulus $\displaystyle n$ is composite.

And also, if I know that $\displaystyle x^a \equiv x \pmod{n}$, then the following must be true : $\displaystyle x^{a - 1} \equiv 1 \pmod{n}$, by dividing both sides by $\displaystyle x$. However, if I take an example, say $\displaystyle n = 21$, $\displaystyle x = 7$ and $\displaystyle a = 3$, we have $\displaystyle 7^3 \equiv 7 \pmod{21}$ alright, but $\displaystyle 7^2 \equiv 7 \pmod{21}$ and is not equal to one, however $\displaystyle 2 = 3 - 1$. Anyone know what I messed up here ?