Computing the order of $[9]_{31}$ in $(\mathbb{Z}/31\mathbb{Z})^*$

Question

A part of Aluffi's "Algebra: Chapter 0" exercise II.4.12 suggests computing the order of $[9]_{31}$ in $(\mathbb{Z}/31\mathbb{Z})^*$. Sure, I could just multiply $9$ a few times until I get $1$ as a remainder (and thus derive that the order in question is 15), but is there a better way?

A few thoughts of mine:

• Firstly, $[9] = [3]^2$, so it'd be sufficient to prove that $[3]$ is a generator (and indeed it is). But I was unable to do this efficiently.
• Another attack direction is that, since $31$ is prime, one might note that $(\mathbb{Z}/31\mathbb{Z})^*$ is cyclic and, having $30$ elements, is isomorphic to $\mathbb{Z}/30\mathbb{Z}$. Maybe we could derive something meaningful by inspecting some isomorphism $\varphi$ between the two? I tried deriving what should it do to the elements of $(\mathbb{Z}/31\mathbb{Z})^*$, and I was able to figure out how it behaves on the powers of $[2]$, but it didn't bring me closer to understanding what it does to $[3]$ or $[9]$.

So shall I just accept my fate and consider this to be an exercise in multiplication and division with remainder?

Answer 1

By lil' Fermat and Lagrange's theorem, all non-zero elements in $\mathbf Z/31\mathbf Z$ have order a divisor of $30$. So the order of $9$ is among $\;\{2, 3,5,6,10,15,30\}$.

It is not very long to check that, $\bmod 31$, \begin{gather}9^2\equiv -12, \quad 9^3\equiv -12\cdot 9=-108\equiv 16,\quad 9^5\equiv -12\cdot 16=-192\equiv -6,\\ 9^6\equiv-6\cdot 9=-54\equiv8, \quad 9^{10}\equiv 36\equiv 5,\quad 9^{15}\equiv 5\cdot -6=-30\equiv 1, \end{gather} so $9$ has order $15$.

Answer 2

This is a variant on Bernard's answer, mainly to show one way to reduce the amount of computation (which isn't a lot to begin with) needed to identify the order.

As noted in Bernard's answer, the only possible orders for the nonzero elements of $\mathbb{Z}/31\mathbb{Z}$ are the divisors of $30$, i.e., $1$, $2$, $3$, $5$, $6$, $10$, $15$, and $30$. Since $31\equiv3$ mod $4$, $-1$ is not a square mod $31$. Therefore, since $9$ is a square, its order cannot be even. (If $9^{2n}\equiv1$ mod $31$, then $9^n\equiv\pm1$ mod $31$.) So in order to conclude that its order is $15$, it suffices to rule out $3$ and $5$ as orders. (The only element of order $1$ is $1$.)

Note that $9\cdot7=63\equiv1$ mod $31$. Now $9^2=81\equiv-12$ mod $31$, so $9^4\equiv144\equiv20$. Since $20$ is neither $9$ nor $7$ mod $31$, we can conclude that neither $9^3$ nor $9^5$ is $1$ mod $31$.

Answer 3

This is a solution inspired by the hint given in the book by Aluffi and does not necessarily invoke Lagrange's Theorem since it has not yet been mentioned at this point of the book where this exercise is given.

Since $31$ is prime, $(\mathbb{Z}/31\mathbb{Z})^*$ is cyclic of order $30$, so we can use the result in Chapter II, Proposition 2.3 where the order or every element in a cyclic group divides the order of the group (otherwise, ignore this and just apply Lagrange's Theorem) so that the possible orders of the elements in $(\mathbb{Z}/31\mathbb{Z})^*$ are $\{1,2,3,5,6,10,15,30\}$. But the order of $9$ cannot be even for otherwise the order of $3$ would be a multiple of $4$ which is not possible since $30=2\times3\times 5$. Thus $\lvert 9 \rvert = 3,5,15$ (as noted in the other answers).

Now consider the equation $x^7-9=0$ in $\mathbb{Z}/31\mathbb{Z}$. If $c$ is a solution then

$$\lvert 9 \rvert =\lvert c^7 \rvert = \frac{\lvert c \rvert}{\text{gcd}(7,\lvert c \rvert)} = \lvert c \rvert$$

If $\lvert 9 \rvert = 3$ then $9^3\equiv (3^3)^2 \equiv (-4)^2 = 16 \not\equiv 1$.

If $\lvert 9 \rvert = 5$ then $c^5=1$ and $c^7=9$ implies $c^2=9$. Since $9\times 7\equiv 1$ then $c^3=7$. By considering $c^6$ we have

$$ 18 \equiv 49 \equiv 7^2 = (c^3)^2 = c^6 = (c^2)^3 = 9^3 \equiv 16$$

Thus the order of $9$ cannot be $3$ or $5$ so $\lvert 9 \rvert=15$.