# Order of elements modulo p

Let $p$ be prime. Suppose that $x\in Z$ has order 6 mod p. Prove that $(1-x)$ has order 6 mod p as well.

I know that I need to show that the order can't be 2 or 3 (4 and 5 are trivial cases), but I'm even having difficulty showing that $(1-x)^6$ is 1. I've expanded $x^{6}-1$ to get a nice congruence that might be useful...but I can't seem to apply it.

-
As a warm-up, try considering $\mathbb{C}$ instead of $\mathbb{Z} / p \mathbb{Z}$. – Hurkyl Oct 25 '12 at 1:22
I'm slightly confused by your question, because every nonidentity element of $Z/pZ$ for $p$ prime has order $p$. How could you have an element of $Z/pZ$ with order $6$? – Benjamin Dickman Oct 25 '12 at 1:26
@B: He is surely referring to multiplicative order in the group of units of the ring $\mathbb{Z} / p \mathbb{Z}$; iow he's talking about primitive 6-th roots of unity. – Hurkyl Oct 25 '12 at 1:27
Ah, I had a typo and reworded it a bit. Certainly we can consider an integer mod 7 which is a primitive root. That has order 6. – Mike M. Oct 25 '12 at 1:29
Your original statement of the thing to prove remains true if you replace the ring $\mathbb{Z} / p \mathbb{Z}$ with $\mathbb{C}$. Many of the proofs ideas that would work for the latter case work unchanged in the former case. (but the actual proof would need a little bit more work to show they actually work) – Hurkyl Oct 25 '12 at 1:35

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.

-

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.

-
Thank you for the beautiful write up, but I am a bit confused. If we are considering "primitive" 6th roots of unity, wouldn't this only apply for p=7? How does this generalize for all $p\equiv 1\mod{6}$ – Mike M. Oct 25 '12 at 2:33
Er...perhaps quadratic reciprocity? – DonAntonio Oct 25 '12 at 2:44
@Don: thanks. Quadratic reciprocity is the technique used to solve the quadratic residuosity problem, and I really wanted to say the former but the word wasn't springing to mind. :( – Hurkyl Oct 25 '12 at 2:45
@Mike: "Primitive sixth root of unity" doesn't mean "primitive element modulo $p$". "Primitive sixth root of unity" means that it has full (multiplicative) order: it is a sixth root of unity, but not a square root or a cube root. – Hurkyl Oct 25 '12 at 2:47
I really loved the term "residuosity" which, as far as I know, is inexistent in modern mathematical english...but who knows? – DonAntonio Oct 25 '12 at 2:48

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.

-
How does being a root of this polynomial imply it has order 6? – Mike M. Oct 25 '12 at 2:01
@MikeM. Let $y$ be a root of $X^2 - X + 1$. Since $X^3 + 1 = (X + 1)(X^2 - X + 1)$, $y^3 + 1 = 0$. Hence $y^6 = 1$. – Makoto Kato Oct 25 '12 at 2:10
This does not show that 6 is the smallest possible integer $k$ for which $(1-x)^k = 1$, does it? – Mike M. Oct 25 '12 at 2:19
@MikeM. I edited the answer. Please feel free to ask me if you still have a question. – Makoto Kato Oct 25 '12 at 5:31