x^6 congruent to 1 (mod 19)

**Deadstar** · March 2nd 2010, 02:38 AM

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

**Bacterius** · March 2nd 2010, 03:05 AM

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 ?

**tonio** · March 2nd 2010, 03:54 AM

Originally Posted by Deadstar

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

**Deadstar** · March 2nd 2010, 07:10 AM

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.

**chiph588@** · March 2nd 2010, 08:24 AM

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?

**tonio** · March 2nd 2010, 09:00 AM

Originally Posted by Deadstar

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)$ $<br />$ . 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.

.

**tonio** · March 2nd 2010, 09:46 AM

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

**Deadstar** · March 2nd 2010, 12:37 PM

EDIT. Solving is happening...

**Deadstar** · March 2nd 2010, 12:52 PM

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?

**Bacterius** · March 2nd 2010, 06:04 PM

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

**tonio** · March 2nd 2010, 06:54 PM

Originally Posted by Deadstar

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

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

LinkBack

Thread Tools

Display

x^6 congruent to 1 (mod 19)

Similar Math Help Forum Discussions

Is S_3 congruent to D_3?

Congruent Triangles

Congruent Angles

Congruent Segments

congruent mod 9

Search Tags