5
$\begingroup$

Let $\beta$ be a root of $x^8-3$ over $GF(17)$. Find all other roots in $GF(17)(\beta)$. What is the degree of $\beta$ over $GF(17)$?

My approach was to see for which $\alpha\in GF(17)$, $\alpha^8=1$ as then we have $(\alpha\beta)^8=\beta^8=3$ so $\alpha\beta$ is also a root.

This required extensive computation and the result is $\alpha=1,2,4,8,9,13,15,16$. There has to be a better way of doing this?

Similarly how can I conclude that the degree of $\beta$ over $GF(17)$ is $8$, other than by checking when $\beta^{17^n}=\beta$ for $n=1,\dots,8$.

Edit: For anybody looking, the answer to my second question is

$$\beta^{17^n}=2^{7n}\beta$$

$2^{7n}=1$ when $7n$ is a multiple of $8$. Since $7,8$ are co-prime, the smallest such $n=8$. So $x^8-3$ is the minimal polynomial of $\beta$ and hence irreducible. So the degree of $\beta$ over $GF(17)$ is $8$.

$\endgroup$
2
  • $\begingroup$ You do know the multiplicative order of $\beta$, don't you? Implying that the method in your last line A) works, B) is very fast. $\endgroup$ May 20, 2018 at 12:01
  • $\begingroup$ I do not know about multiplicative order. So I was not sure if my method works or was just by luck $\endgroup$ May 20, 2018 at 12:30

1 Answer 1

5
$\begingroup$

Note that $2^4 = -1$, so $2$ is a primitive eighth root of unity.

Therefore, if $\beta$ is one of the roots of $x^8-3$, then all the roots are $2^n \beta$.

$\endgroup$
3
  • $\begingroup$ Didn't the OP already find those eights root of unity in their third paragraph? $\endgroup$ May 20, 2018 at 12:02
  • 1
    $\begingroup$ Yes, but he asked for a better method. $\endgroup$
    – Kenny Lau
    May 20, 2018 at 12:02
  • $\begingroup$ Ah! Ok. ${}{}{}$ $\endgroup$ May 20, 2018 at 12:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .