How to solve $x^3 \equiv 1 \pmod{37}$

Question

We are asked to solve $x^3 \equiv 1 \pmod{37}$. I know that the answer is $10$ since $27\cdot37 = 999$ and $10^3 = 1000$ but how do I show this rigorously? If it helps, we are given the primitive roots of $37$ which are $2, 5, 13, 15, 17, 18, 19, 20, 22, 24, 32$, and $35$. But I am not sure how this is useful.

Answer 1

You know that $2^{36}\equiv 1$, since $2$ is a primitive root. Hence you may conclude that $(2^{12})^3\equiv 1$, and also $(2^{24})^3\equiv (2^{36})^2\equiv 1^2$. These correspond to $26$ and $10$ respectively. Of course $2^{36}=1$.

Now, suppose that $(2^a)^3\equiv 1$. Then $2^{3a}\equiv 1$, so $36|3a$, or $12|a$. That doesn't leave many choices for $a$, since $1\le a\le 36$...

Answer 2

Like Find all solutions to $y^2 \equiv 5x^3 \pmod {7}$,

as $2$ is a primitive root $\pmod{37}$ as

$2^5\equiv-5\pmod{37}\implies2^{10}\equiv(-5)^2\equiv-12\implies2^{12}\equiv-12\cdot2^2\equiv26\not\equiv1$

and $2^{18}\equiv(-10)^3\equiv-1$

using Discrete Logarithm , $3$ind$_2x\equiv0\pmod{36}\iff$ind$_2x\equiv0\pmod{12}$

$\implies x\equiv2^{12k}\pmod{37}$ where $k\equiv0,1,2\pmod3$

Answer 3

The mutiplicative group $\mathbf F^*_{37}$ of the finite field $\mathbf F_{37}$ is cyclic of order $36$. Since $3$ divides $36$, $\mathbf F^*_{37}$ admits a unique subgroup of order $3$ which is no other than $({\mathbf F^*_{37}})^{12}$ ( = the $12$-th powers in $\mathbf F^*_{37}$). For any generator $g$ of $\mathbf F^*_{37}$, i.e. a primitive $36$-th root of $1$ in $\mathbf F^*_{37}$, $g^{12}$ will generate the group of solutions you look for. For example, $g$ = the class of $2$ mod $37$ will do.

Answer 4

If $p$ is a prime of the form $3k+1$, $\mathbb{F}_p^*=\{g,g^2,\ldots,g^{3k}\}$ for some $g\in\mathbb{F}_p^*$ and the map $x\mapsto x^3$ is a $3$-to-$1$ map on $\mathbb{F}_p^*$, having as range the subgroup of cubic residues in $\mathbb{F}_p^*$. The kernel of such map is given by the roots of $z^3-1=(z-1)(z^2+z+1)$ in $\mathbb{F}_p$, so in order to find the solutions of $a^3\equiv 1\pmod{37}$ it is enough to find the solutions of $b^2+3\equiv 0\pmod{37}$. These are $b\equiv \pm 16\pmod{37}$, hence

$$ a^3\equiv 1\pmod{37}\quad\Longleftrightarrow\quad a\pmod{37}\in\{1,10,26\}. $$ In your case there was a shortcut: you found the solutions $1$ and $10$, and the third solution $s$ has to be such that $1+10+s\equiv 0\pmod{37}$, since Vieta's theorem ensures that the sum of the roots of $z^3-1$ is zero.

Answer 5

Just for fun another way.

Because of $\mathbb F_{37}$ is a field the equation in $\mathbb F_{37}[x]$ $$x^3=1\iff (x-1)(x^2+x+1)=0$$

must have three roots so, since $1$ is clearly root, one can find out the other two ones solving $$x^2+x+1=0$$ We have $$x+y=-1=36\\xy=1$$ Exploring $$35+1\\34+2\\33+3\\32+4\\31+5\\30+6\\29+7\\28+8\\27+9\\26+10$$ We stop because $26\cdot10=260\equiv 1\pmod{37}$, thus the roots are $1,10$ and $26$.