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...

Printable View

- Mar 2nd 2010, 02:38 AMDeadstarx^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... - Mar 2nd 2010, 03:05 AMBacterius
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 ? :) - Mar 2nd 2010, 03:54 AMtonio
- Mar 2nd 2010, 07:10 AMDeadstar
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. - Mar 2nd 2010, 08:24 AMchiph588@
- Mar 2nd 2010, 09:00 AMtonio
- Mar 2nd 2010, 09:46 AMtonio

"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 - Mar 2nd 2010, 12:37 PMDeadstar
EDIT. Solving is happening...

- Mar 2nd 2010, 12:52 PMDeadstar
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?

- Mar 2nd 2010, 06:04 PMBacterius
I think you already worked out what I'm about to say, but this is just to increase my post count (joking :D)

$\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 ;) - Mar 2nd 2010, 06:54 PMtonio

What "same result" are you talking about? That they have the same discriminant doesn't mean their roots are the same...(Wondering).

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