Order of elements modulo p

Solution 1:

Naively, we "know" there are two primitive 6-th roots of unity, and they are

$$ \frac{1}{2} \pm i \frac{\sqrt{3}}{2} $$

and so

$$ 1 - \left(\frac{1}{2} \pm i \frac{\sqrt{3}}{2} \right) = \frac{1}{2} \mp i \frac{\sqrt{3}}{2}$$

Done! But does this make sense in the ring $\mathbb{Z} / p \mathbb{Z}$?

Well first, observe that, since $p \neq 2,3$ it makes sense in the algebraic closure of the field $\mathbb{Z} / p \mathbb{Z}$, since such a thing does have a square root of $-1$ as well as a square root of $3$, and so it's true there. And if the primitive sixth root of unity happens to be a member of $\mathbb{Z} / p \mathbb{Z}$, then this relationship holds there too.

But maybe we don't want to go that far. Can we stick within $\mathbb{Z} / p \mathbb{Z}$? Well, it turns out we don't need square roots of $3$ and of $-1$: we just need a square root of $-3$, since the primitive 6th roots of unity are

$$ \frac{1}{2} \pm \frac{\sqrt{-3}}{2} $$

Does this make sense in $\mathbb{Z} / p \mathbb{Z}$ if it has a primitive 6-th root of unity $x$? Well, we just need to check that $-3$ has a square root (and that $2 \neq 0$). If it does, then the sixth roots of unity have the same form as they do in the complexes, and the original argument applies.

There are a number of ways to do this. We know that $p \equiv 1 \pmod 6$ (because $\varphi(p)$ is divisible by 6). By quadratic reciprocity,

$$ \left( \frac{-3}{p} \right) = \left( \frac{p}{-3} \right) = \left( \frac{6k+1}{-3} \right) = \left( \frac{1}{-3} \right) = 1 $$

Or, we could compute the square root of -3: if the equation

$$ x = \frac{1}{2} \pm \frac{\sqrt{-3}}{2} $$

really does make sense, then

$$ 2\left(x - \frac{1}{2} \right) = \pm \sqrt{-3} $$

If we check

$$ (2x - 1)^2 + 3 = 0 $$

then we know the previous formula computes a square root of 3. We can check this with polynomial arithmetic. Because we know $x^6 = 1$, we know that $x$ is a root of

$$ t^6 - 1 = (t-1) (t+1) (t^2 + t + 1) (t^2 - t + 1) $$

The factors are polynomials whose roots are 1, square roots of unity, cube roots of unity, and sixth roots of unity, respectively. $x$ must be a root of the last factor then, so we know

$$ x^2 - x + 1 = 0$$

The equation we need to check, then, is

$$(2x-1)^2 + 3 = 4x^2 - 4x + 4 = 4(x^2 - x + 1) = 0$$

The four factors of $t^6 - 1$ listed above are cyclotomic polynomials. If you were very familiar with such things, then the very first idea that popped into your head might have been the fact $x$ has to be a root of $t^2 - t + 1$. The problem is actually fairly simple starting from this fact, since the two roots of this polynomial must add to 1.

Solution 2:

If $ord_px=6\implies p\mid(x^6-1)$ ,i.e, $p\mid(x^3-1)(x^3+1)$

If $p\mid(x^3-1), x^3\equiv 1\pmod p\implies ord_px=3\ne 6$

So, $p\mid(x^3+1)\implies p\mid (x+1)(x^2-x+1)$ and $x^3\equiv -1\pmod p$

If $p\mid(x+1), x\equiv -1\pmod p\implies x^2\equiv 1\pmod p\implies ord_px=2\ne 6$

So, $p\mid(x^2-x+1)$

(i) $ x^2\equiv x-1\pmod p$

So, $1-x=(-1)(x-1)\equiv x^3\cdot x^2\pmod p$ as $x^3\equiv -1\pmod p$

So, $1-x\equiv x^5\implies ord_p(1-x)=ord_p(x^5)$

We know, $ord_ma=d, ord_m(a^k)=\frac{d}{(d,k)}$ (Proof @Page#95)

So, $ord_m(x^5)=\frac{6}{(6,5)}=6$

(ii) $x-x^2\equiv1\pmod p$

$\implies 1-x\equiv x^{-1}$ dividing either side by $x$ as $(x,p)=1$

So, $ord_p(1-x)=ord_p(x^{-1})$

So, $ord_m(x^{-1})=\frac{6}{(6,-1)}=6$

Observation :

If $x^5\equiv x\pmod p, x^4\equiv 1\implies ord_px\mid 4$, but $ord_px=6$

If $x\equiv x^{-1}\pmod p,x^2\equiv 1\implies ord_px\mid 2$

In fact, $x^{-1}\equiv x^5\pmod p$ as $x^6\equiv1$

We also know, that are exactly $\phi(6)=2$ in-congruent elements that belong to order $6\pmod p$ if $6\mid \phi(p)\implies p\equiv 1\pmod 6$.

In that case, we can conclude $x,x^{-1}\equiv x^5\equiv(1-x)$ are those two.

Solution 3:

Let $a \in \mathbb{Z}/p\mathbb{Z}$ be an element of order 6. Since $a^6 = 1, a^3 = -1$. Hence $a$ is a root of $X^3 + 1 = 0$. Since $X^3 + 1 = (X + 1)(X^2 - X + 1)$, $a$ is a root of the polynomial $X^2 - X + 1$. Hence there exists $b \in \mathbb{Z}/p\mathbb{Z}$ such that $X^2 - X + 1 = (X - a)(X - b)$. Since $a + b = 1$, $b = 1 - a$. Since $b$ is a root of $X^3 + 1$, $b^3 = -1$. Hence $b^6 = 1$. Since $p \neq 3$, $-1$ is not a root of $X^2 - X + 1$. Hence $b^2 \neq 1$. Hence the order of $b$ is 6.