Solve equation $x^{32}=1$ in $\mathbb{Z}_{128}.$

Question

Solve equation $x^{32}=1$ in $\mathbb{Z}_{128}.$

Attempt. Let $x \in \mathbb{Z}_{128}$ be such that $x^{32}=1$. Then $x$ is invertible, so $x$ belongs in $U(\mathbb{Z}_{128})$, the set of all invertible elements of $\mathbb{Z}_{128}$ (having $\varphi(128)=64$ elements). On the other hand, if $x\in U(\mathbb{Z}_{128})$, then $\mathrm{gcd}(x,128)=1$, so $x$ is odd, i.e. $x=2k+1$. So in order to have $x^{32}=1$, we have $(2k+1)^{32}=1$, that is $(4k^2+4k+1)^5=1$. Here is where i am stuck.

A second thought was to reduce the problem like: $x^{32}=1$, i.e. $(x^{16})^2=1$, so $x^{16}=1$ or $-1$.

Thanks in advance.

Answer 1

Hint

$(2k+1)^2=8k(k+1)/2+1=8c+1$ (say)

$(2k+1)^4=(8c+1)^2=16c(4c+1)+1=16d+1$(say)

and so on

Alternatively using http://mathworld.wolfram.com/CarmichaelFunction.html to validate the exponent

we need $\lambda(128)=2^{7-2}$

So, any $x$ with $(x,2)=1$ will satisfy the given congruence

Answer 2

Hint:

If $2\mid n-1$ then $8\mid n^2-1, 2\mid n^2+1, 2\mid n^4+1, 2\mid n^8+1, $ and $2\mid n^{16}+1$.

On the other hand, if $2\mid n$ then $2\nmid n^{128}-1$.

Answer 3

The multiplicative group $(\mathbb{Z}/128\mathbb{Z})^\times$ is isomorphic to $\mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/32\mathbb{Z}$, and in this group every element has order that divides $32$. It follows that every $n \in (\mathbb{Z}/128\mathbb{Z})^\times$ (that is, every residue class of an odd integer) is a solution to $x^{32} - 1 = 0$, ,and it is clear that there cannot be any other solution.

Answer 4

It's well-known that $\Bbb Z_{128}^×$ isn't cyclic. Since it's abelian, and has order $\varphi (128)=64$, we can get that, by FTFAG, every element has order dividing $32$ (for the orders of all the cyclic summands must divide $32$) and thus satisfies the congruence.

On the other hand, $x^{32}\cong1\pmod {128}\implies x$ is a unit.