# Thread: x^6 congruent to 1 (mod 19)

1. ## x^6 congruent to 1 (mod 19)

How do solve $\displaystyle x^6 \equiv 1 \textrm{ (mod 19)}$

NO SOLUTIONS PLEASE, just hints or even just which theorem/method to use.

I thought it might be something to do with primitive roots...

2. Hello !
Note that $\displaystyle x^6 \equiv 1 \pmod{19}$ is equivalent to $\displaystyle x^6 - 1 \equiv 0 \pmod{19}$. Doesn't this remind you of some algebraïc structure learnt while studying factorization ?

How do solve $\displaystyle x^6 \equiv 1 \textrm{ (mod 19)}$

NO SOLUTIONS PLEASE, just hints or even just which theorem/method to use.

I thought it might be something to do with primitive roots...

The hint Bacterius gave you wraps it all, but if you insist in using primitive roots then suppose $\displaystyle \omega$ is such a primitive root , and look at $\displaystyle \omega^3$ ...

Tonio

4. Thanks for the hint but I probably should have asked about equations of the form $\displaystyle x^n \equiv 1 mod p$ with p prime as the above hint for this one hasn't helped me.

Factorizing that I can only see two solutions, 1 and 18.

I can't find anything in our notes about this and it's stuck in the middle of a tutorial consisting of primitive root questions so I don't know how to approach it.

5. Originally Posted by tonio
The hint Bacterius gave you wraps it all, but if you insist in using primitive roots then suppose $\displaystyle \omega$ is such a primitive root , and look at $\displaystyle \omega^3$ ...

Tonio
Isn't just required that $\displaystyle \omega$ is a cubic residue?

Thanks for the hint but I probably should have asked about equations of the form $\displaystyle x^n \equiv 1 mod p$ with p prime as the above hint for this one hasn't helped me.

Factorizing that I can only see two solutions, 1 and 18.

How come?? $\displaystyle x^6-1=(x-1)(x^2+x+1)(x+1)(x^2-x+1)$$\displaystyle$ . The roots $\displaystyle 1,18=-1\!\!\!\pmod {19}$ are immediate, and we're left now with the quadratics, so let's check the discriminant which, by the way, is identical in both!:

$\displaystyle \Delta=1-4=-3$ , and the questions of questions now is whether $\displaystyle -3$ is a quadratic residue modulo 19...but this is trivial and we don't even need quadatic reciprocity, right?

The complete set of roots is $\displaystyle -1,1,7,12,8,11$

Tonio

I can't find anything in our notes about this and it's stuck in the middle of a tutorial consisting of primitive root questions so I don't know how to approach it.
.

7. Originally Posted by chiph588@
Isn't just required that $\displaystyle \omega$ is a cubic residue?

"Just"? I think that's exactly equivalent to ask whether the original equaion has a solution. There are $\displaystyle \phi(18)=6$ primitive roots of 19, which are (modulo 19, of course), if I'm not wrong (and I wouldn't bet much that I am not) $\displaystyle 2,3,10,13,14,15$ .

Tonio

8. EDIT. Solving is happening...

9. Ok I can get 7 and 11 from the quadratics but since they both give the same result how do I find 8 and 12?

10. I think you already worked out what I'm about to say, but this is just to increase my post count (joking )

$\displaystyle x^6 - 1 = (x - 1)(x + 1)(x^2 - x + 1)(x^2 + x + 1)$

So the solutions of $\displaystyle x^6 \equiv 1 \pmod{19}$ are given by :

$\displaystyle x - 1 \equiv 0 \pmod{19}$

$\displaystyle x + 1 \equiv 0 \pmod{19}$

$\displaystyle x^2 - x + 1 \equiv 0 \pmod{19}$

$\displaystyle x^2 + x + 1 \equiv 0 \pmod{19}$

Solve those for $\displaystyle x$ and you will find all the solutions of the congruence. Don't forget to include the four solutions given by the quadratics

Ok I can get 7 and 11 from the quadratics but since they both give the same result how do I find 8 and 12?

What "same result" are you talking about? That they have the same discriminant doesn't mean their roots are the same....
Just apply the well-known formula for the roots of a quadratic equation, which you can do since the characteristic of the field we're working on isn't two.

Tonio