Is $x^3-9$ irreducible over the integers mod 31?

Solution 1:

The multiplicative group of the finite field $F_{31}=\mathbf{Z}/31\mathbf{Z}$ is cyclic of order 30. Therefore the non-zero cubes form a cyclic subgroup of order 10. That subgroup consists of all the elements of order dividing ten, so all you need to do is to check, whether $9^{10}\equiv 1\pmod{31}$ or not. Leaving that to you.

Solution 2:

consider G = Z/31Z ,the group of nonzero elements of Z/31Z under multiplication. This is a cyclic group of order 30. The map $\Phi: G \to G$ defined by $\Phi(x) = x^3$ is a homomorphism. So we need to know if 9 is contained in the image of Φ. Note that the kernel of $\Phi$ is the unique subgroup of order 3 in G. So the image has order 30/3 = 10. So we need to know if 9 is in the subgroup of order 10. Now computing the order of 9 in G. Note $9^2 \equiv 81 \equiv 19 \equiv -12 \pmod {31}$. So $9^3 \equiv 9(-12)=108 \equiv -15 \pmod {31}$. Then 9 does not have order 3. Also $9^5 = 9^2 * 9^3 \equiv (-12)(-15)=180 \equiv -6 \pmod {31}$. So 9 does not have order 5. Also $9^10 = 9^5 * 9^5 \equiv (-6)^2 =36 \equiv 5 \pmod {31}$. Then 9 does not have order 10. Therefore it cannot be in the subgroup of of order 10.

Solution 3:

To work modulo a small prime like $31$ is not at all tedious. Just start with some positive integer and write down its powers successively, reducing modulo $31$ each time. With luck, you will have chosen a primitive residue, and you get all $30$ nonzero residues. This gives you a log table for multiplication modulo $31$. You see immediately that $2$ is not a good choice, since $2^5\equiv1\pmod{31}$. Try $3$: the powers are $1$, $3$, $9$, $27$, $19$, $26$, $16$, etc. With the full list, you will see that $9$ is not a cube, so that the polynomial is indeed irreducible (cubic polynomial without a root). With your list in front of you, you can do all sorts of multiplicative computations with hardly a thought, for instance finding a high power of any residue at all.