Exercise 2.9.8* (Cubic roots modulo $p$)

Proof.

(a)

Suppose that $p-1=m{3}^k$ with $k>0$ and $3\nmid m$.

Let ${𝔽}_p$ be the field $\mathbb{Z}∕\mathit{p\mathbb{Z}}$ with $p$ elements. Then ${𝔽}_p^{\text{∗}}$ is an abelian group, and

$$\phi \{\begin{array}{ccc}\hfill {𝔽}_p^{\text{∗}}\hfill & \hfill \text{→}\hfill & {𝔽}_p^{\text{∗}}\hfill \\ \hfill x\hfill & \hfill \mapsto \hfill & x^{3^k},\hfill \end{array}\psi \{\begin{array}{ccc}\hfill {𝔽}_p^{\text{∗}}\hfill & \hfill \text{→}\hfill & {𝔽}_p^{\text{∗}}\hfill \\ \hfill x\hfill & \hfill \mapsto \hfill & x^m,\hfill \end{array}$$

are group homomorphisms. We show first that $\mathrm{im}\psi =\ker <!--\; FUNCTION\; APPLICATION\; -->\phi .$

We estimate the orders of the subgroups $\ker <!--\; FUNCTION\; APPLICATION\; -->\psi$ and $\ker <!--\; FUNCTION\; APPLICATION\; -->\phi$. Let $\gamma$ a generator of ${𝔽}_p^{\text{∗}}$. For any $x\in {𝔽}_p^{\text{∗}}$, $x={\gamma }^t$ for some integer $t$, where $0\le t<m{3}^k$, and

$$\begin{array}{llll}\hfill x\in \ker <!--\; FUNCTION\; APPLICATION\; -->\psi & ⟺{\gamma }^{\mathit{tm}}=1& \hfill & \\ \hfill & ⟺p-1\mid \mathit{tm}& \hfill & \\ \hfill & ⟺3^k\mid t.& \hfill & \end{array}$$

Since the order of $\gamma$ is $m{3}^k$,

$$\ker <!--\; FUNCTION\; APPLICATION\; -->\psi =\{1,{\gamma }^{3^k},{\gamma }^{2\cdot 3^k},\dots <!--\; FUNCTION\; APPLICATION\; -->,{\gamma }^{(m-1)3^k}\},$$

where the elements ${\gamma }^{j\cdot 3^k}(0\le j\le m-1)$ are distinct, thus $|\ker <!--\; FUNCTION\; APPLICATION\; -->\psi |=m$.

Similarly,

$$\begin{array}{llll}\hfill x\in \ker <!--\; FUNCTION\; APPLICATION\; -->\psi & ⟺{\gamma }^{t{3}^k}=1& \hfill & \\ \hfill & ⟺p-1\mid t{3}^k& \hfill & \\ \hfill & ⟺m\mid t.& \hfill & \end{array}$$

Therefore

$$\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )=\{1,{\gamma }^m,{\gamma }^{2m},\dots <!--\; FUNCTION\; APPLICATION\; -->,{\gamma }^{(3^k-1)m}\},$$

and $|\ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )|=3^k$.

By the first isomorphism theorem, $\mathrm{im}\psi \simeq {𝔽}_p^{\text{∗}}∕\ker <!--\; FUNCTION\; APPLICATION\; -->\psi$, thus

$$|\mathrm{im}\psi |=(p-1)∕m=3^k=|\ker <!--\; FUNCTION\; APPLICATION\; -->\phi |.$$

Moreover, if $y\in \mathrm{im}\psi$, then $y=x^m$ for some $x\in {𝔽}_p^{\text{∗}}$. Therefore

$$y^{3^k}=x^{m{3}^k}=x^{p-1}=1,$$

thus $y\in \ker <!--\; FUNCTION\; APPLICATION\; -->\phi$. This shows that

$$\mathrm{im}\psi \subseteq \ker <!--\; FUNCTION\; APPLICATION\; -->\phi ,$$

where $|\mathrm{im}\psi |=|\ker <!--\; FUNCTION\; APPLICATION\; -->\phi |$, hence

$$\mathrm{im}\psi =\ker <!--\; FUNCTION\; APPLICATION\; -->\phi .$$

So, for every $y\in {𝔽}_p^{\text{∗}}$,

$$\begin{array}{lll}\hfill \exists <!--\; FUNCTION\; APPLICATION\; -->x\in {𝔽}_p^{\text{∗}},y=x^m⟺y^{3^k}=1.& & \hfill \text{(1)}\end{array}$$

We write $o(y)$ the order of $y$ in the group ${𝔽}_p^{\text{∗}}$. It remains to shows the equivalence

$$\begin{array}{lll}\hfill y^{3^k}=1⟺\exists <!--\; FUNCTION\; APPLICATION\; -->j\in \mathbb{N},o(y)=3^j.& & \hfill \text{(2)}\end{array}$$

• If $y^{3^k}=1$, then $o(y)\mid 3^k$, thus $o(y)=3^j$ for some $j\in \mathbb{N}$.
• Conversely, if $o(y)=3^j$, since $y^{m{3}^k}=1$, then $3^j\mid m{3}^k$, where $m\wedge 3=1$, hence $3^j\mid 3^k$, thus $j\le k$, and $y^{3^k}={(y^{3^j})}^{3^{k-j}}=1$.

Combining (1) and (2), we obtain for every $y\in {𝔽}_p^{\text{∗}}$,

$$\begin{array}{lll}\hfill \exists <!--\; FUNCTION\; APPLICATION\; -->x\in {𝔽}_p^{\text{∗}},y=x^m⟺\exists <!--\; FUNCTION\; APPLICATION\; -->j\in \mathbb{N},o(y)=3^j.& & \hfill \text{(3)}\end{array}$$

If we translate (3) in $\mathbb{Z}$, we obtain, for every integer $n$ such that $n\wedge p=1$ (using $y={[n]}_p\in {𝔽}_p^{\text{∗}}$):

The congruence $x^m\equiv n(\mathit{mod}p)$ has a solution if and only if the order of $n$ modulo $p$ is a power of $3$.

Note that those integers $n$ are the integers such that $[n]={[n]}_p\in \ker <!--\; FUNCTION\; APPLICATION\; -->(\phi )$. Write $G$ the subgroup $G=\ker <!--\; FUNCTION\; APPLICATION\; -->\phi =\mathrm{im}\psi$. By part (a),

$$[n]\in G=\{1,{\gamma }^m,{\gamma }^{2m},\dots ,{\gamma }^{(3^k-1)m}\}.$$

(b)

We want to solve the congruence $x^3\equiv a(\mathit{mod}p)$, where $p\nmid a$. This congruence has a solution if and only if $a^{(p-1)∕3}\equiv 1(\mathit{mod}p)$ . Indeed, if $x^3\equiv a(\mathit{mod}p)$, then $a^{(p-1)∕3}\equiv x^{p-1}\equiv 1(\mathit{mod}p)$. Conversely, suppose that $a^{(p-1)∕3}\equiv 1(\mathit{mod}3)$. Let $g$ be a primitive root modulo $p$. Then $a\equiv g^s(\mathit{mod}p)$ for some positive integer $s$, so that $g^{s\frac{p-1}{3}}\equiv 1(\mathit{mod}p)$. The order of $g$ is $p-1$, therefore $p-1\mid s\frac{p-1}{3}$, thus $3\mid s$, so $s=3u$ for some positive integer $u$, and $a\equiv {(g^u)}^3=x^3$, with $x=g^u$.

We assume now that the condition

$$\begin{array}{lll}\hfill a^{(p-1)∕3}\equiv 1(\mathit{mod}p),& & \hfill \text{(4)}\end{array}$$

so that we know that the congruence $x^3\equiv a(\mathit{mod}p)$ has a solution.

• If $m\equiv 2(\mathit{mod}3)$, then $(m+1)∕3$ is an integer. Put

  $$r\equiv a^{(m+1)∕3},n\equiv a^m(\mathit{mod}p).$$

  Then

  $$r^3\equiv a^{m+1}=a\cdot a^m\equiv \mathit{an}(\mathit{mod}n).$$

  Moreover $n\equiv a^m(\mathit{mod}p)$ implies by part (a) that the order of $n$ modulo $p$ is a power of $3$.

  The condition (4) is equivalent to $n^{3^{k-1}}\equiv 1$.

• If $m\equiv 1(\mathit{mod}3)$, then $(2m+1)∕3$ is an integer. Put

  $$r\equiv a^{(2m+1)∕3},n\equiv a^{2m}(\mathit{mod}p).$$

  Then

  $$r^3\equiv a^{2m+1}=a\cdot a^{2m}\equiv \mathit{an}(\mathit{mod}p).$$

  Moreover, $n\equiv {(a^2)}^m$ implies by part (a) that the order of $n$ modulo $p$ is a power of $3$.

  The condition (4) gives $n^{3^{k-1}}\equiv a^{2\frac{p-1}{3}}\equiv 1(\mathit{mod}p)$. Conversely, if $n^{3^{k-1}}\equiv 1(\mathit{mod}p)$, then $a^{2\frac{p-1}{3}}\equiv 1(\mathit{mod}p)$, and $a^{\frac{p-1}{3}}=a^{p-1-2\frac{p-1}{3}}\equiv 1(\mathit{mod}p)$.

In both cases, $r^3\equiv \mathit{an}(\mathit{mod}p)$, and $n^{3^{k-1}}\equiv 1(\mathit{mod}p)$, so the order of $n$ is a power of $3$, say $3^{k^{\prime }}$, where $k^{\prime }<k$. The condition $n^{3^{k-1}}\equiv 1(\mathit{mod}p)$ is a necessary and sufficient condition to the existence of a solution of the congruence $x^3\equiv a(\mathit{mod}p)$.

(c)

Choose $z$ so that $z^{(p-1)∕3}\not\equiv 1(\mathit{mod}p)$. Such an element $z$ exists: let $g$ be a primitive root modulo $p$ ( $\gamma =[g]$ is a generator of ${𝔽}_p^{\text{∗}}$). Thus $z\equiv g^t(\mathit{mod}p)$ for some integer $t$. Then $$\begin{array}{llll}\hfill z^{(p-1)∕3}\equiv 1(\mathit{mod}p)& ⟺g^{k\frac{p-1}{3}}& \hfill & \\ \hfill & ⟺p-1\mid k\frac{p-1}{3}& \hfill & \\ \hfill & ⟺3\mid k& \hfill & \end{array}$$

Take $z\equiv g^k(\mathit{mod}p)$, where $3\nmid k$ (for instance $z=g$). Then $z^{(p-1)∕3}\not\equiv 1(\mathit{mod}p)$.

(To find such a $z$, we can use a probabilistic algorithm. If we take a random $z\in [[1,p-1]]$, the probability that $z^{(p-1)∕3}\not\equiv 1(\mathit{mod}p)$ is $2∕3$, so we find quickly such a $z$, the average of the waiting time being $3∕2$. )

Now set $c\equiv z^m(\mathit{mod}p)$. Then $[c]\in \mathrm{im}\psi$, thus $[c]\in G=\ker <!--\; FUNCTION\; APPLICATION\; -->\phi$, where the order of $G$ is $3^k$. We show that the order of $c$ is $3^k$.

Since

$$c^{3^k}\equiv z^{m{3}^k}=z^{p-1}\equiv 1(\mathit{mod}p),$$

and

$$c^{3^{k-1}}\equiv z^{m{3}^{k-1}}\equiv z^{(p-1)∕3}\not\equiv 1(\mathit{mod}p),$$

the order of $c$ modulo $p$ is $3^k$. Since $[c]\in G$, and the order is $c$ is $3^k=|G|$, $[c]$ is a generator of the subgroup $G$.

Since $[n]\in G$, $[n]={[c]}^u$ for some $u$, $0\le u<3^k$, thus

$$n\equiv c^u(\mathit{mod}p),0\le u<3^k.$$

(d)

Suppose that $k^{\prime }\ne 0$. Since the order of $c$ is $3^k$, the order of $b=c^{3^{k-k^{\prime }}}$ is $3^{k^{\prime }}$ ( $b^{3^{k^{\prime }}}=c^{3^k}\equiv 1(\mathit{mod}p)$, and $b^{3^{k^{\prime }-1}}=c^{3^{k-1}}\not\equiv 1(\mathit{mod}p)$). Since the order $3^{k^{\prime }}>1$ of $b$ is equal to the order of $n$, by Problem 6, one of the numbers $\mathit{nb}=n{c}^{3^{k-k^{\prime }}},n{b}^2=n{c}^{2\cdot 3^{k-k^{\prime }}}$ has order $3^{k^{\prime }}$, and the order of the other one is a smaller power of $3$, say $3^{k^{″}}$.

From $r^3\equiv \mathit{an}(\mathit{mod}p)$, we deduce

$$\begin{array}{llll}\hfill & {\left(r{c}^{3^{k-k^{\prime }-1}}\right)}^3\equiv a(n{c}^{3^{k-k^{\prime }}})=a(\mathit{nb}),& \hfill & \\ \hfill & {\left(r{c}^{2\cdot 3^{k-k^{\prime }-1}}\right)}^3\equiv a(n{c}^{2\cdot 3^{k-k^{\prime }}})=a(n{b}^2).& \hfill & \end{array}$$

Put

$$\begin{array}{lllllll}\hfill & n^{\prime }\equiv \mathit{nb},r^{\prime }=r{c}^{3^{k-k^{\prime }-1}},& \hfill \text{if }o(\mathit{nb})<o(n),& & \hfill & & \hfill \\ \hfill & n^{\prime }\equiv n{b}^2,r^{\prime }=r{c}^{2\cdot 3^{k-k^{\prime }-1}},& \hfill \text{if }o(n{b}^2)<o(n),& & \hfill & & \hfill \end{array}$$

so that in both cases ${r{}^{\prime }}^3\equiv a{n}^{\prime }$, where $o(n^{\prime })<o(n).$

We continue until one of the number $n_0=n,n_1=n^{\prime },n_2=n^{″},\dots$ is congruent to $1$ modulo $p$, say $n_d$. Then $r_d^3\equiv a{n}_d\equiv a(\mathit{mod}p)$, so that $r_d$ is a solution $x_0$ of the congruence $x^3\equiv a(\mathit{mod}p)$.

To obtain the other roots, we note that $x^3\equiv a(\mathit{mod}p)$ is equivalent to ${(x∕x_0)}^3\equiv 1(\mathit{mod}p)$, where $x_0$ is a particular solution. Therefore the solutions are $x_0\omega$, where $\omega$ is a solution of $x^3\equiv 1(\mathit{mod}p)$.

To solve $x^3=1$ in ${𝔽}_p$, we use $x^3-1=(x-1)(x^2+x+1)$. Moreover, for all $x\in {𝔽}_p$,

$$\begin{array}{llll}\hfill x^2+x+1=0& ⟺4x^2+4x+4\equiv 0(\mathit{mod}p)& \hfill & \\ \hfill & ⟺{(2x+1)}^2=-3.& \hfill & \end{array}$$

If $\xi$ is a square root of $-3$ in ${𝔽}_p$, obtained with the RESSOL algorithm (if such a root exists, that is if $p\equiv 1(\mathit{mod}3)$), we obtain

$$2x+1=\pm \xi .$$

The inverse of $[2]\in {𝔽}_p$ is ${[2]}^{-1}=\frac{p+1}{2}$, thus a root of $x^2+x+1$ if $p\equiv 1(\mathit{mod}3)$ is

$$\omega =\left(\frac{p+1}{2}\right)(\xi -1).$$

Since $x^3-1=(x-1)(x-\omega )(x-{\omega }^2)$, the roots are $1,\omega ,{\omega }^2$. So, for all $x\in {𝔽}_p$,

$$\begin{array}{lllllll}\hfill & \bullet \text{if }p\equiv 2(\mathit{mod}3),x^3=1(modp)⟺x=1& \hfill \text{,}& & \hfill & & \hfill \\ \hfill & \bullet \text{if }p\equiv 1(\mathit{mod}3),x^3=1(modp)⟺x\in \{1,\omega ,{\omega }^2\},& \hfill & & \hfill & \\ \hfill & \text{where }\omega =\left(\frac{p+1}{2}\right)(\xi -1),{\xi }^2=-3,\xi \in {𝔽}_p.& \hfill & & \hfill & \end{array}$$

(See the algorith below.)