0
$\begingroup$

On ring $\mathbb{Z}_{128}$, solve each of the following equations: $$(i)~x^2= x,~~~~~~(ii)~x^2=1,~~~~~~(iii)~x^{32}=1.$$

Attempt. Some thoughts.

(i) Clearly $x=0,1$ are solutions. Let $x \in \mathbb{Z}_{128}$ be such that $x^2=x$. Then $128=2^7$ divides $x^2-x=x(x-1)$.

(ii) Clearly $x=1,-1$ are solutions. Let $x \in \mathbb{Z}_{128}$ be such that $x^2=1$. So $xx=1$ and $x$ is invertible in $\mathbb{Z}_{128}$. So $\gcd(x,2^7)=1$ and $x$ is odd. Also, the order of $x$ is $2$ (unless, of course, the case $x=1$, which clearly satisfies the equation).

(iii) Clearly $x=1,-1$ are solutions. Let $x \in \mathbb{Z}_{128}$ be such that $x^{32}=1$, meaning that $x$ is invertible in $\mathbb{Z}_{128}$ and $x$ is odd and also the order of $x$ divides $32$.

Thanks for the help.

$\endgroup$
  • $\begingroup$ $x=\pm 63$ also solves (ii) $\endgroup$ – J. W. Tanner Feb 10 at 16:17
1
$\begingroup$

(i) You're almost there! What can you tell about $x$ given that $2^7$ divides $x(x-1)$? Note that it is impossible for both $x$ and $x-1$ to be even.

(ii) This time observe $x^2-1=(x+1)(x-1)$. Continue as you do in (i).

(iii) If $x^{32}=1$, then $x^{16}$ satisfies (ii). We can use this to find what $x^8$ must be, what $x^4$ must be, what $x^2$ must be, and then what $x$ must be; it might look like this would require an exponential amount of calculation, but much computation is saved by observing $x^2\equiv 1\pmod{4}$ if $x$ is odd.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.