Thread: Roots

1. Roots

Find the roots of x^3 - 1 in F (sub 7)

Find the roots of x^3 - 1 in F (sub 5)

(There is a bar over the 1's in the above problems)

2. Originally Posted by jzellt
Find the roots of x^3 - 1 in F (sub 7)

Find the roots of x^3 - 1 in F (sub 5)

(There is a bar over the 1's in the above problems)
Hi jzellt.

5 and 7 are pretty small numbers. You can simply take the cubes of all the small numbers and note which ones are congruent to 1 modulo 5 / 7.

3. Can you be a little more specific?

Maybe work out the first one...I'm really lost with this topic.

4. A polynomial of degree n has at most n roots.

There are only n elements in $\displaystyle \mathbb{Z}_n$. Try them is what he is saying.

$\displaystyle 0^3-1=0-1=-1 \equiv 4$ (mod 5)
$\displaystyle 1^3-1=1-1=0 \equiv 0$ (mod 5)
$\displaystyle 2^3-1=8-1=7 \equiv 2$ (mod 5)
$\displaystyle 3^3-1=27-1=26 \equiv 1$ (mod 5)
$\displaystyle 4^3-1=64-1=63 \equiv 3$ (mod 5)

Thus the only root is 1.

I think you can do it for the other one.

5. So, from what you did...How do I know that the only root is 1?

6. Do you know what a root of a polynomial is?

It is an element of the field for which the polynomial evaluated at that element yields 0.

I just checked every element of the field (all 5 of them) to see if the polynomial was 0 in the field or not. Only 1 was a root. That is how I knew.

7. Originally Posted by jzellt
So, from what you did...How do I know that the only root is 1?
What else could it be?

$\displaystyle 0^3-1=0-1=-1 \equiv 4 (mod 5)$ so it's not 0.
$\displaystyle 1^3-1=1-1= 0 (mod 5)$ so 1 is a root.
$\displaystyle 2^3-1=8-1= 7 \equiv 2 (mod 5)$ so it's not 2.
$\displaystyle 3^3-1=27-1= 26 \equiv 1 (mod 5)$ so it's not 3.
$\displaystyle 4^3-1=64-1= 63 \equiv 3 (mod 5)$ so it's not 4.

There are no other possibilities.

8. Okay, here is some group-theory analysis (although this particular problem is so simple that it hardly needs this kind of thing).

Now, if $\displaystyle p$ is a prime, $\displaystyle \mathbb Z_p^\times=\{1,\ldots,p-1\}$ is a group under multiplication modulo $\displaystyle p.$ Now, $\displaystyle x^3-1$ is a root in $\displaystyle \mathbb Z_p^\times=\{1,\ldots,p-1\}$ if and only if the subgroup generated by $\displaystyle x,$ namely $\displaystyle \left<x\right>$ has order dividing 3. Since 3 is a prime, this means that either (i) $\displaystyle \left<x\right>$ is trivial or (ii) a cyclic group of order 3. If $\displaystyle p=5$ then $\displaystyle p-1=4$ and so by Lagrange there is no subgroup of order 3 and so the only solution to the equation is $\displaystyle x=1.$ But for $\displaystyle p=7$ it is possible to have to have a subgroup of order 3 and so it turns out that there are two solutions modul0 7.

The conclusion is: $\displaystyle x^3-1$ has one root in $\displaystyle \mathbb F_5$ (namely 1) and three roots in $\displaystyle \mathbb F_7$ (nanely 1, 2 and $\displaystyle 2^2=4.)$

If there is anything not clear, please ask.

9. So after working both problems out...

The only root is 1 regardless if im working in F7 or F5

Is this correct?

10. Originally Posted by TheAbstractionist
Okay, here is some group-theory analysis (although this particular problem is so simple that it hardly needs this kind of thing).

Now, if $\displaystyle p$ is a prime, $\displaystyle \mathbb Z_p^\times=\{1,\ldots,p-1\}$ is a group under multiplication modulo $\displaystyle p.$ Now, $\displaystyle x^3-1$ is a root in $\displaystyle \mathbb Z_p^\times=\{1,\ldots,p-1\}$ if and only if the subgroup generated by $\displaystyle x,$ namely $\displaystyle \left<x\right>$ has order dividing 3. Since 3 is a prime, this means that either (i) $\displaystyle \left<x\right>$ is trivial or (ii) a cyclic group of order 3. If $\displaystyle p=5$ then $\displaystyle p-1=4$ and so by Lagrange there is no subgroup of order 3 and so the only solution to the equation is $\displaystyle x=1.$ But for $\displaystyle p=7$ it is possible to have to have a subgroup of order 3 and so it turns out that there are two solutions modul0 7.

The conclusion is: $\displaystyle x^3-1$ has one root in $\displaystyle \mathbb F_5$ (namely 1) and three roots in $\displaystyle \mathbb F_7$ (nanely 1, 2 and $\displaystyle 2^2=4.)$

If there is anything not clear, please ask.
For $\displaystyle \mathbb{Z}_5$ as the abstractionist and I have both shown you already 1 is indeed the only root to that polynomial.

However, this is not the case for $\displaystyle \mathbb{Z}_7$ as theabstractionist was so kind to point out, both 2 and 4 are roots as well.

Please take the time to read people's responses carefully, they are not answering your questions for their own health.

$\displaystyle 1^3-1=0 \equiv 0$ (mod 7) so 1 is a root

$\displaystyle 2^3-1=7 \equiv 0$ (mod 7) so 2 is a root

$\displaystyle 4^3-1=64-1=63=7*9 \equiv 0$ (mod 7) so 4 is a root.

A polynomial of degree n can have at most n roots, so this is all of them as $\displaystyle x^3-1$ has degree 3 and we have listed 3 roots.

Clear?