1

We know that if $\gcd(n,p)=1$, then the polynomial $x^n-1$ can be factored to the irreducible polynomials over $GF(p)$ by cyclotomic cosets method, as follows($t$ is a number of cyclotomic cosets) $$ x^n-1=f_1(x)\, f_2(x)\, \cdots \, f_t(x) $$

Now, we want to see the question of factoring $x^n-1=0$ over $GF(p)$ with another point of view. Let $k$ be the first positive integer such that $n\mid p^k-1$, which means $GF(p^k)$ have elements of the order $n$. Suppose that $\beta$ be an element of $GF(p^k)$ with order $n$, then $x^n-1$ can be represent as
$$ x^n-1=(x-1)(x-\beta)(x-\beta^2)\cdots (x-\beta^{n-1}) $$

My question: How to prove that the following relation( without considering cyclotomic cosets method) $$ (x-1)(x-\beta)(x-\beta^2)\cdots (x-\beta^{n-1})=f_1(x)\, f_2(x)\, \cdots \, f_t(x) $$

Example: By cyclotomic cosets method, $x^{13}-1$ over $GF(3)$ is factored as follows $$ x^{13}-1=(2+x)(2+x+x^2+x^3)(2+x^2+x^3)(2+2x+2x^2+x^3)(2+2x+x^3) $$

Now, we have $13\mid 3^3-1$ which results that if $\beta$ be an element of order $13$ over $GF(3^3)$that is constructed by $x^3+2x+1$, then we have $$ x^{13}-1=(x-1)(x-\beta)(x-\beta^2)\cdots (x-\beta^{12}) $$

Thanks for any suggestions.

Amin235
  • 1,867
  • 1
    The cyclotomic coset method (if I correctly understood what you mean by it) means that those cubic factors in your example are of the form $m_\gamma(x):=(x-\gamma)(x-\gamma^3)(x-\gamma^9)$ for some 13th root of unity $\gamma$. Here $\gamma$ should range over a set of representatives of cyclotomic cosets, say $\gamma\in{\beta,\beta^2,\beta^{-2},\beta^{-1}}$. A few things we can say right away. For example the constant term of $m_\gamma(x)$ is $(-1)^3\gamma\cdot\gamma^3\cdot\gamma^9=-\gamma^{1+3+9}=-1$. – Jyrki Lahtonen Aug 29 '17 at 21:54
  • 1
    (cont'd) Another observation we can make is that the polynomials $m_\gamma(x)$ and $m_{\gamma^{-1}}(x)$ are reciprocals of each other. So if $m_\gamma(x)=x^3+a_2x^2+a_1x-1$, then $$m_{\gamma^{-1}}(x)=-x^3 m_\gamma(1/x)=x^3-a_1x^2-a_2x-1.$$ So if $\beta$ is chosen in such a way that its minimal polynomial is $x^3+2x+2$, then the minimal polynomial of $\beta^{-1}$ is $x^3+x^2+2$. – Jyrki Lahtonen Aug 29 '17 at 21:59
  • 1
    There is also a method for finding the minimal polynomial of $\beta^2$ given that of $\beta$. The idea is to observe that $p(x)=-m_\beta(x)m_\beta(-x)$ is an even polynomial. That is $p(x)=q(x^2)$ for some cubic polynomial $q(x)$. Then $q(\beta^2)=p(\beta)=0$, so $q(x)$ is the minimal polynomial of $\beta^2$. – Jyrki Lahtonen Aug 29 '17 at 22:02
  • 1
    I don't know if this is at all related to what you wanted to ask. Too late an hour here, and I may have already nearly exhausted my bag of tricks. Luckily they cover your example fully :-) At least if you start from the well known fact that $x^p-x-1$ is irreducible over $\Bbb{F}_p$. – Jyrki Lahtonen Aug 29 '17 at 22:03
  • @JyrkiLahtonen I appreciate for your comment. Just I want to ask you to introduce an reference for this subject that i study more about it. Thanks – Amin235 Aug 29 '17 at 22:05
  • This was mostly trickery and elementary Galois theory. The early chapters of Lidl & Niederreiter cover this, but then they get to heavier duty stuff. Because I learned the basics from the lecture notes (in Finnish only), I could read L&N on my own. Whether you can do the same may depend on your general background in algebra. Check it at a math library. IIRC L&N is a bit pricy, so you don't want to buy a copy without checking it out first :-) – Jyrki Lahtonen Aug 29 '17 at 22:10
  • @JyrkiLahtonen Excuse me Lidl & Niederreiter have two books. 1) Finite field 2) introduction to finite filed with application. which of them you mean? Thanks – Amin235 Aug 29 '17 at 22:14
  • 1
    This one is on my shelf. – Jyrki Lahtonen Aug 29 '17 at 22:18
  • @JyrkiLahtonen OK I do it. In past I have studied chapter 8 of this book when I was studding companion matrix over the finite field. Thanks again – Amin235 Aug 29 '17 at 22:22

0 Answers0