0

I'm reading this pdf about finite fields.

In the first page it's said:

Let $α$ be a root of $f(x)$. Then $f(x)|x^{n}-1 \Rightarrow ord(a)|n $

However, what is the order of a root in this case ? And what is the meaning of the implication ? I didn't find anything useful on the web...

Community
  • 1
AleWolf
  • 185

2 Answers2

1

The order of an element $\alpha$ in a finite field is the smallest positive integer $k$ such that $\alpha ^ k = 1$.

The polynomial $f(x)$ divides the polynomial $x^n -1$ when there is some polynomial $q(x)$ (the quotient) such that $$ f(x)q(x) = x^n -1 . $$ If $\alpha$ is a root of $f(x)$ then that means it's root of $x^n -1$ so $\alpha^n = 1$.

It follows that the smallest $k$ such that $\alpha^k = 1$ must divide the integer $n$.

Ethan Bolker
  • 95,224
  • 7
  • 108
  • 199
1

The order of $a$ is defined as the smallest number $ord(a)$ such that $a^{ord(a)} = 1$. Since $f(x) \mid x^n-1$, we must have that every root of $f(x)$ is a root of $x^n-1$. So this implies that $\alpha^n = 1$. From here, it is not too hard to prove that $ord(\alpha) \mid n$; try proving it by first proving that for any two integers $b, c$ such that $\alpha ^b = \alpha ^c = 1$, you must have $\alpha ^{\gcd (b, c)} = 1$.

auscrypt
  • 8,186