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?

  • $\begingroup$ It might help to consider $$\operatorname{Aut}(\Bbb Z_{31})\cong (\Bbb Z/31\Bbb Z)^*.$$ Just as another perspective . . . $\endgroup$ – Shaun Apr 21 at 22:10
  • $\begingroup$ 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! $\endgroup$ – 0xd34df00d Apr 22 at 0:04
  • $\begingroup$ 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 :) $\endgroup$ – 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$.

  • $\begingroup$ 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. $\endgroup$ – Andreas Blass Apr 21 at 23:08
  • $\begingroup$ Sure, but anyway, most of these computations are useful steps to compute the other powers. $\endgroup$ – Bernard Apr 21 at 23:18
  • $\begingroup$ 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$.) $\endgroup$ – 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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.