I've tried so much to prove the following problem but it was waste of time. I wonder if anyone could help me.

Any irreducible polynomial over $GF(2)$ of degree $m$ divides $X^{2^m−1}\ +\ \ 1$

  • $\begingroup$ Welcome to math.SE: you may find it useful to know a few things about the site. In order to get the best possible answers, it is helpful if you say in what context you encountered the problem, and what your thoughts on it are; this will prevent people from telling you things you already know, and help them give their answers at the right level. $\endgroup$ – mlc Mar 29 '17 at 13:53
  • $\begingroup$ This has been covered many times on our site. Do search within the tag finite-fields. I am not aware of a textbook on finite fields that does not explain that the field $GF(2^m)$ consists of the zeros of $x^{2^m}+x=x(x^{2^m-1}+1)$. Together with the uniqueness of $GF(2^m)$ this implies the result rather easily. So my recommendation is that you A) search the site, B) if the answers you find leave some gaps in your understanding you then edit this question and describe the unclear steps. $\endgroup$ – Jyrki Lahtonen Mar 29 '17 at 14:01
  • $\begingroup$ As it is the question is a bit poor, because we don't know how much you know about this topic, and what kind of an answer would help you. $\endgroup$ – Jyrki Lahtonen Mar 29 '17 at 14:03
  • $\begingroup$ @JyrkiLahtonen Thanks, but I've already searched this site but there was no such a question. And also, I can't understand when $x^{2^m}+x$ has all of the members as its roots what has to do with this question? could you explain it more? $\endgroup$ – Alireza Aliyan Mar 29 '17 at 14:15
  • 1
    $\begingroup$ See for example this old question and the other questions linked to it. $\endgroup$ – Jyrki Lahtonen Mar 29 '17 at 14:34

If $f$ is an irreducible polynomial of degree $m$, then $F=GF(2)[X]/(f)$ is a field with $2^m$ elements. Let $F=GF(2)(\alpha)$. Apply Lagrange's theorem to the multiplicative group $F^\times$ to conclude that $\alpha^{2^m-1}=1$. Since $f$ is the minimal polynomial of $\alpha$, the result follows. (Note that $-1=1$ in $F$.)

Indeed, all polynomials $g$ such that $g(\alpha)=0$ are multiples of $f$. In other words, $f$ generates the ideal of polynomials that have $\alpha$ as a zero.

  • $\begingroup$ I don't understand the notation that you've used "F=GF(2)[X]/(f)" please enlighten me.@lhf $\endgroup$ – Alireza Aliyan Mar 29 '17 at 14:26
  • $\begingroup$ @AlirezaAliyan, polynomial quotient ring. $\endgroup$ – lhf Mar 29 '17 at 14:26
  • $\begingroup$ Thanks, it is clear up to $\alpha^{2^m-1} = 1$ but, why the result follows? @lhf $\endgroup$ – Alireza Aliyan Mar 29 '17 at 14:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.