Unit cube roots in number theory

Arithmetic, algebra, number theory, sequence and series, analysis, ...
Post Reply
castrate
Posts: 27
Joined: Mon Aug 19, 2019 2:34 pm

Unit cube roots in number theory

Post by castrate »

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.
User avatar
hk
Administrator
Posts: 11319
Joined: Sun Mar 26, 2006 10:34 am
Location: Haren, Netherlands

Re: Unit cube roots in number theory

Post by hk »

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)
Image
pjt33
Posts: 70
Joined: Mon Oct 06, 2008 6:14 pm

Re: Unit cube roots in number theory

Post by pjt33 »

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.
Post Reply