I was trying to solve some particular PE problem these days. It is easy to verify that for any prime power p^k(except 2), there exist two solutions to the equation x^2=1(mod p^k), namely 1 and p^k-1.

However, when dealing with the equation x^3=1(mod p^k), the result appeared to differ. For some primes, such as 7,13 and 19, there exists three solutions(1,2,4 for 7, 1,3,9 for 13, 1,7,11 for 19); but for some other primes such as 11 and 17, there is only one solution 1, which is somewhat confusing.

Is there any theorem/efficient algorithm, which can compute the number of unit cube roots(modulo p) without brute force? In fact, this problem can help me work out at least PE problem.

## Unit cube roots in number theory

### Re: Unit cube roots in number theory

if $p\mod 3=1$ there are three solutions, if $p\mod3 =2$ there is one solution to the equation $a^3=1 \mod p$

(See also https://math.stackexchange.com/question ... od-p-for-x)

(See also https://math.stackexchange.com/question ... od-p-for-x)

### Re: Unit cube roots in number theory

Solutions to $x^3 = 1$ are roots of $x^3 - 1$ which factors as $(x-1)(x^2+x+1)$. For $p \neq 2$ you can complete the square as over the reals, giving $x = 2^{-1}(-1 \pm \sqrt{-3})$. Square roots modulo a prime can be computed by the Tonelli-Shanks algorithm. Solutions modulo a prime power can be obtained by finding solutions modulo the prime and Hensel lifting.