# Math Help - x^6 congruent to 1 (mod 19)

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

How do solve $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 $x^6 \equiv 1 \pmod{19}$ is equivalent to $x^6 - 1 \equiv 0 \pmod{19}$. Doesn't this remind you of some algebraïc structure learnt while studying factorization ?

How do solve $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 $\omega$ is such a primitive root , and look at $\omega^3$ ...

Tonio

4. Thanks for the hint but I probably should have asked about equations of the form $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 $\omega$ is such a primitive root , and look at $\omega^3$ ...

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

Thanks for the hint but I probably should have asked about equations of the form $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?? $x^6-1=(x-1)(x^2+x+1)(x+1)(x^2-x+1)$ $
$
. The roots $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!:

$\Delta=1-4=-3$ , and the questions of questions now is whether $-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 $-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 $\omega$ is a cubic residue?

"Just"? I think that's exactly equivalent to ask whether the original equaion has a solution. There are $\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) $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 )

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

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

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

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

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

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

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