<s>[INST] How to find cube roots of 1 modulo power of two (if they exist)? 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}$?
 [/INST] 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}}$ 
</s>