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

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?

• It might help to consider $$\operatorname{Aut}(\Bbb Z_{31})\cong (\Bbb Z/31\Bbb Z)^*.$$ Just as another perspective . . . – Shaun Apr 21 at 22:10
• Could you please expand on that? I tried myself and it wasn't particularly fruitful for me, but anything involving morphisms looks promising and elegant! – 0xd34df00d Apr 22 at 0:04
• The idea wasn't fully fledged, @0xd34df00d, I'm afraid; it would just have been the first place I'd look. Perhaps if you examine a proof of the isomorphism, something'd pop out. Sorry :) – Shaun Apr 22 at 5:39

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$$.

• Since $9=3^2$ and since $3$ must have one of the orders you listed, $9$ must have order $3$ or $5$ or $15$. So you only need to do half of the checking in this answer. – Andreas Blass Apr 21 at 23:08
• Sure, but anyway, most of these computations are useful steps to compute the other powers. – Bernard Apr 21 at 23:18
• Agreed, but there are other ways to do the computations. Here's how I did them (I'm not claiming it's better, just different). Modulo 31, we have $3^3=27\equiv-4$, so $9^3\equiv(-4)^2=16$. And $3^5=243\equiv-5$ so $9^5\equiv(-5)^2=25\equiv-6$. In other words, I just kept taking advantage of the facts that $9=3^2$ and that I know some powers of $3$. (And I got lucky in that $3^5=243$ is very close to an obvious multiple $248$ of $31$.) – Andreas Blass Apr 21 at 23:29

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$$.

• @OP "...it suffices to rule out $3,5$" is a special case of the Order Test. – Bill Dubuque Apr 22 at 2:23