Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
3  
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
1  
@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
1  
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
show 1 more comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
add comment

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.

share|improve this answer
    
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
show 3 more comments

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.

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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