1

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}$?

Peter Dillinger
  • 113
  • How about $c \equiv 1 (\bmod 2^{64})$ or you are looking for all possible solutions? – Daniyar Aubekerov Jan 27 '20 at 20:03
  • $\Bbb{Z}/2^n \Bbb{Z}^\times$ has $2^{n-1}$ elements, its group structure is $\pm 1 \times \langle 5\rangle$ where $5$ has order $2^{n-2}$, you won't find any element of order $3$ in there. Now there is the ring extension $\Bbb{Z}/2^n \Bbb{Z}[x]/(x^2+x+1)$ where $x$ is a cube root of unity. – reuns Jan 27 '20 at 20:04
  • The unit group modulo $2^n$ has order $2^{n-1}$, so it has no nontrivial $3$-torsion. – David E Speyer Jan 27 '20 at 20:05
  • @DavidESpeyer: If you are going to use terms like "3-torsion" when answering a question at this level, you might at least provide a link for the OP. (But even that link is heavy going.) – TonyK Jan 27 '20 at 20:09
  • Fair enough. reuns comment (30 second sooner) is better. – David E Speyer Jan 27 '20 at 20:20

2 Answers2

2

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}$.

0

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}}$

Will Jagy
  • 139,541