How to find cube roots of 1 modulo power of two (if they exist)?

Question

It would be useful for efficiently implementing an algorithm if I could find a $c > 1$ where $c^3 \equiv 1 \pmod {2^{64}}$. It's plausible that such a $c$ exists because $2^{64} \equiv 1 \pmod 3$, so all non-zero values could be partitioned into groups of three (each $x$ along with $cx \pmod {2^{64}}$ and $c^2 x \pmod {2^{64}}$).

Is there a known way to find these more efficiently than brute force (probably infeasible, no solutions for $2^{32}$)? Or is it known to have no solution? Or are there known solutions, perhaps for other powers of two between $2^{32}$ and $2^{64}$?

Answer 1

If $c^3\equiv 1\pmod{2^n}$ then $2^n | c^3-1=(c-1)(c^2+c+1)$, but since $c^2+c+1$ is odd, $2^n|c-1$, i.e. $c\equiv 1\pmod {2^n}$.

Answer 2

You can do this by induction. We begin with $1^3 \equiv 1 \pmod {2^k}$ where the start is $k=1.$ In paerticular, there are no others. Do we get any additional roots as $k$ increases? Just two choices.

This works: $1^3 \equiv 1 \pmod {2^{k+1}}$

Maybe: $$ (1+2^k)^3 = 1 + 3 \cdot 2^k + 3 \cdot 2^{2k} + 2^{3k} \equiv 1 + 3 \cdot 2^k \pmod {2^{k+1}} \; , \; $$ so that $$ (1+2^k)^3 \equiv 1 + 2^k \pmod {2^{k+1}} \; , \; $$ because $2 \cdot 2^k \equiv 0 \pmod {2^{k+1}}$ This second choice fails, as the exponent of $2$ increases, the only cube root of $1$ remains $1$

The alternatives that fail to give cube roots of one resemble this: $$ 3^3 = 27 \equiv 3 \pmod 4 $$ $$ 5^3 = 125 \equiv 5 \pmod 8 $$ $$ 9^3 = 729 \equiv 9 \pmod {16} $$ $$ 17^3 = 4913 \equiv 17 \pmod {32} $$ $$ 33^3 = 35937 \equiv 33 \pmod {64} $$ $$ 65^3 = 274625 \equiv 65 \pmod {128} $$ $$ 129^3 = 2146689 \equiv 129 \pmod {256} $$ $$and \; \; so \; \; on...$$

This procedure comes under the name of Hensel Lifting. And this gives a complete proof that there is just one cube root of one $\pmod {2^{64}}$