This is my first time "solving an equation" in a group so I feel like that may be the source of my troubles. Here's what I have so far, although I'm not sure how to progress:
Assume $c$ is a solution to $x^3-9=0$ in $(\mathbb{Z}/31 \mathbb{Z})$. We then have $$c^3-9=0\implies c^3=9 \implies |c^3|=|9|$$ and since on the LHS we're multiplying elements in $(\mathbb{Z}/31 \mathbb{Z})$, we consider the order of $[9]_{31}$ in $(\mathbb{Z}/31 \mathbb{Z})^*$ which is $15$ since $$9^{15} \equiv 1 \ \text{mod} \ 31.$$ Thus $|c^3|=15$.
I feel like I should be able to deduce $|c|$ from $|c^3|$ but it doesn't seem to be clear to me. Could someone assist me in figuring out how to get $|c|$?
From there, my next steps would be to ensure it divides $31$. Since $(\mathbb{Z}/31 \mathbb{Z})^*$ is abelian and cyclic thus has an element of maximal finite order of $31$, and if $|c| \leq 31$ then $|c|$ must divide $31.$
$\endgroup$ 36 Answers
$\begingroup$There is no solution as
$$c^{30} = 9^{10} = 5$$
but $$c^{30} = 1 \ \ \forall c \not =0$$
$\endgroup$ 4 $\begingroup$If $x^3=9$ then $x^{15}=9^5$. So $9^5\equiv 1\pmod{31}$. (Since $9^5\not\equiv -1$ , or $9^{15}\equiv -1$ and hence $9$ would not be a square modulo $31$.)
So you only need to check if $9^5\equiv 1\pmod{31}$.
$\endgroup$ 2 $\begingroup$Another approach uses a pigeonhole argument.
We have $\bmod 31$:
$2^3\equiv 8, (-3)^3\equiv 4=8/2$
Then $2$ is a cubic residue and so are all powers of $2$ and their negatives, thus:
$\pm 1, \pm 2, \pm 4, \pm 8, \pm 16$
That is $10$ nonzero residues, whereas the total number of cubic nonzero residues must be $(31-1)/3=10$. Perforce there is no possibility left for $9$ or any other nonzero residue to be a cubic one.
As a corrollary, $3$ shall be a primitive root since this cannot be cubic (above), quadratic (QR), or fifth power ($3^3 \not \equiv \pm 1$).
$\endgroup$ $\begingroup$Ummm $3$ is a cube $\pmod p$ for prime $p \equiv 1 \pmod 3$ if and only if we can express $$ p = x^2 + xy + 61 y^2 $$ in integers. Theorem due to Jacobi. A version in Ireland and Rosen.
Let's see, if $3$ is a cube so is $9.$ If $9$ is a cube so are $81$ and $3$
Primes 1 mod 3 up to 1000 that do not work
7, 13, 19, 31, 37, 43, 79, 97, 109, 127,
139, 157, 163, 181, 199, 211, 223, 229, 241, 277,
283, 313, 331, 337, 349, 373, 379, 397, 409, 421,
433, 457, 463, 487, 541, 571, 601, 607, 631, 673,
691, 709, 733, 739, 751, 769, 811, 823, 829, 859,
877, 883, 907, 937,primes 1 mod 3 up to 1000 that do work
1, 61, 67, 73, 103, 151, 193, 271, 307, 367,
439, 499, 523, 547, 577, 613, 619, 643, 661, 727,
757, 787, 853, 919, 967, 991, 997,All numbers $a$ coprime to $31$ satisfy $a^{30}\equiv 1 \bmod 31$. There is a primitive root $g$ such that $k=30$ is the smallest positive value such that $g^k\equiv 1 \bmod 31$, so any number coprime to $31$ can be expressed as equivalent to a power of $g$. This means that for $a^6$, in particular, there are only $5$ distinct values possible, since $a^6\in\equiv \{g^6,g^{12},g^{18},g^{24},g^{30}\equiv 1\}$
We can also see that $2^5\equiv 1 \bmod 31$, so also $\{4^5, 8^5, 16^5\}\equiv 1 \bmod 31$. $30/6 = 5$ and thus $e=\{1,2,4, 8, 16\} $ are the $5$ possible values that can have $a^6\equiv e \bmod 31$.
Obviously $9$ is a square, so if $9$ is also a cube $(c^3\equiv 9 \bmod 31)$ then it must also be a sixth power $(d^6\equiv 9 \bmod 31)$ . Thus $(c^3\equiv 9 \bmod 31)$ has no solutions $c$.
$\endgroup$ $\begingroup$Slightly more efficiently, we get that if $c^3\equiv 9\equiv 3^2\pmod{31}$, then $c^{15}\equiv 3^{10}\pmod{31}$.
$$3^{10}\equiv (27)^3\cdot 3$$
$$\equiv (-4)^3\cdot 3\equiv -64\cdot 3$$
$$\equiv -2\cdot 3\equiv -6\pmod{31},$$
Since $\left(c^{15}\right)^2\equiv 1\pmod{31}$ for all $c\in\mathbb Z$ such that $31\not\mid c$ by Fermat's little theorem,
we get $31\mid \left(c^{15}+1\right)\left(c^{15}-1\right)$,
so $31\mid c^{15}+1$ or $31\mid c^{15}-1$ by Euclid's lemma,
so $c^{15}\equiv \pm 1\pmod{31}$, contradiction.
((In fact, $a^{\frac{p-1}{2}}\equiv \left(\frac{a}{p}\right)\pmod{p}$ for all $a\in\mathbb Z$, odd primes $p$ by Euler's criterion))
((and also, in this case, $c^{15}\equiv 1\pmod{31}$, because
if $c^{15}\equiv -1\pmod{31}$,
then $\left(3^5\right)^2\equiv -1\pmod{31}$,
contradiction, because $-1$ isn't a quadratic residue mod $31=4\cdot 7+3$ by Quadratic Reciprocity))
$\endgroup$
