Irreducible factors of $x^8 - x$ in $Z/2Z[x]$












1












$begingroup$


I must find the irreducible factors of $f(x) = x^8 - x$ in $Z/2Z[x]$ and that's what I did:



$f(x) = x(x-1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)$



but of course the correct solution is:



$f(x) = x(x-1)(x^3 + x^2 + 1)(x^3 + x + 1)$



I do not understand how I can reach the correct solution by logical reasoning (without going on attempts). The solution of the exercise says:



1) "The irreducible factors are all the irreducible polynomials of degree 1 and 3 alone" Why?



2) "You find exactly $6/3 = 2$ irreducible polynomials of degree 3". Does this happens because the 6th degree polynomial I found is not reducible (since the only ones have degree 1 or 3) and it has no zeros?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Welcome to Maths SX! What do you call the grade of a polynomial?
    $endgroup$
    – Bernard
    Jan 13 at 18:21










  • $begingroup$
    I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
    $endgroup$
    – MattP9
    Jan 13 at 18:40










  • $begingroup$
    Very close to being a duplicate of this. Or this. Or this.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 19:09












  • $begingroup$
    I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
    $endgroup$
    – MattP9
    Jan 13 at 21:55












  • $begingroup$
    We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 22:33


















1












$begingroup$


I must find the irreducible factors of $f(x) = x^8 - x$ in $Z/2Z[x]$ and that's what I did:



$f(x) = x(x-1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)$



but of course the correct solution is:



$f(x) = x(x-1)(x^3 + x^2 + 1)(x^3 + x + 1)$



I do not understand how I can reach the correct solution by logical reasoning (without going on attempts). The solution of the exercise says:



1) "The irreducible factors are all the irreducible polynomials of degree 1 and 3 alone" Why?



2) "You find exactly $6/3 = 2$ irreducible polynomials of degree 3". Does this happens because the 6th degree polynomial I found is not reducible (since the only ones have degree 1 or 3) and it has no zeros?










share|cite|improve this question











$endgroup$












  • $begingroup$
    Welcome to Maths SX! What do you call the grade of a polynomial?
    $endgroup$
    – Bernard
    Jan 13 at 18:21










  • $begingroup$
    I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
    $endgroup$
    – MattP9
    Jan 13 at 18:40










  • $begingroup$
    Very close to being a duplicate of this. Or this. Or this.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 19:09












  • $begingroup$
    I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
    $endgroup$
    – MattP9
    Jan 13 at 21:55












  • $begingroup$
    We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 22:33
















1












1








1


3



$begingroup$


I must find the irreducible factors of $f(x) = x^8 - x$ in $Z/2Z[x]$ and that's what I did:



$f(x) = x(x-1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)$



but of course the correct solution is:



$f(x) = x(x-1)(x^3 + x^2 + 1)(x^3 + x + 1)$



I do not understand how I can reach the correct solution by logical reasoning (without going on attempts). The solution of the exercise says:



1) "The irreducible factors are all the irreducible polynomials of degree 1 and 3 alone" Why?



2) "You find exactly $6/3 = 2$ irreducible polynomials of degree 3". Does this happens because the 6th degree polynomial I found is not reducible (since the only ones have degree 1 or 3) and it has no zeros?










share|cite|improve this question











$endgroup$




I must find the irreducible factors of $f(x) = x^8 - x$ in $Z/2Z[x]$ and that's what I did:



$f(x) = x(x-1)(x^6 + x^5 + x^4 + x^3 + x^2 + x + 1)$



but of course the correct solution is:



$f(x) = x(x-1)(x^3 + x^2 + 1)(x^3 + x + 1)$



I do not understand how I can reach the correct solution by logical reasoning (without going on attempts). The solution of the exercise says:



1) "The irreducible factors are all the irreducible polynomials of degree 1 and 3 alone" Why?



2) "You find exactly $6/3 = 2$ irreducible polynomials of degree 3". Does this happens because the 6th degree polynomial I found is not reducible (since the only ones have degree 1 or 3) and it has no zeros?







abstract-algebra polynomials ring-theory galois-theory finite-fields






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited Jan 13 at 18:42







MattP9

















asked Jan 13 at 18:05









MattP9MattP9

304




304












  • $begingroup$
    Welcome to Maths SX! What do you call the grade of a polynomial?
    $endgroup$
    – Bernard
    Jan 13 at 18:21










  • $begingroup$
    I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
    $endgroup$
    – MattP9
    Jan 13 at 18:40










  • $begingroup$
    Very close to being a duplicate of this. Or this. Or this.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 19:09












  • $begingroup$
    I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
    $endgroup$
    – MattP9
    Jan 13 at 21:55












  • $begingroup$
    We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 22:33




















  • $begingroup$
    Welcome to Maths SX! What do you call the grade of a polynomial?
    $endgroup$
    – Bernard
    Jan 13 at 18:21










  • $begingroup$
    I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
    $endgroup$
    – MattP9
    Jan 13 at 18:40










  • $begingroup$
    Very close to being a duplicate of this. Or this. Or this.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 19:09












  • $begingroup$
    I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
    $endgroup$
    – MattP9
    Jan 13 at 21:55












  • $begingroup$
    We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
    $endgroup$
    – Jyrki Lahtonen
    Jan 13 at 22:33


















$begingroup$
Welcome to Maths SX! What do you call the grade of a polynomial?
$endgroup$
– Bernard
Jan 13 at 18:21




$begingroup$
Welcome to Maths SX! What do you call the grade of a polynomial?
$endgroup$
– Bernard
Jan 13 at 18:21












$begingroup$
I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
$endgroup$
– MattP9
Jan 13 at 18:40




$begingroup$
I meant the degree. In my native language you say a word that's very similar to "grade" so I got confused. I rectified the text. Thank you for welcoming :)
$endgroup$
– MattP9
Jan 13 at 18:40












$begingroup$
Very close to being a duplicate of this. Or this. Or this.
$endgroup$
– Jyrki Lahtonen
Jan 13 at 19:09






$begingroup$
Very close to being a duplicate of this. Or this. Or this.
$endgroup$
– Jyrki Lahtonen
Jan 13 at 19:09














$begingroup$
I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
$endgroup$
– MattP9
Jan 13 at 21:55






$begingroup$
I tryed searching if someone else did the same question, but I did not find those links. This is my first day on this website and I still have to get the hang of it. I'm sorry.
$endgroup$
– MattP9
Jan 13 at 21:55














$begingroup$
We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
$endgroup$
– Jyrki Lahtonen
Jan 13 at 22:33






$begingroup$
We understand, Matt! Searching here is sometimes difficult because the normal search engines cannot grok LaTeX. Approach0 is an alternative, but it has other shortcomings. Experience helps. You'll get the hang of it soon enough.
$endgroup$
– Jyrki Lahtonen
Jan 13 at 22:33












1 Answer
1






active

oldest

votes


















1












$begingroup$

I note here $GF(p^n)$ the finite field of characteristic $p$ prime having $p^n$ elements.



The elements of $GF(2^3)$ are the roots of $f$ in a splitting field. Also note that the multiplicative group of $GF(2^3)$ is of order $7$ which is a prime. Hence all elements of the multiplicative group of $GF(2^3)$ except the identity $1$ are of order $7$.



From this it follows that an irreducible factor of $g(x) = x^7-1$ can only be of degree $1$, which is the case for the identity or of degree $3$. If an irreducible polynomial of $g$ would be of degree $2$, $GF(2^3)$ would have a subfield of order $4$ and at least an element of order $3$ which is not the case as we've seen above.



So we're left to find the irreducible polynomials (over $GF(2)$) of degree $3$. This is quite easy. The only polynomials of degree $3$ are:
$$x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2+1$$



Only the two last ones are irreducible.



We're done.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
    $endgroup$
    – MattP9
    Jan 13 at 20:11












  • $begingroup$
    Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
    $endgroup$
    – mathcounterexamples.net
    Jan 13 at 20:19










  • $begingroup$
    Thank you very much!
    $endgroup$
    – MattP9
    Jan 13 at 21:52











Your Answer





StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072331%2firreducible-factors-of-x8-x-in-z-2zx%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown

























1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes









1












$begingroup$

I note here $GF(p^n)$ the finite field of characteristic $p$ prime having $p^n$ elements.



The elements of $GF(2^3)$ are the roots of $f$ in a splitting field. Also note that the multiplicative group of $GF(2^3)$ is of order $7$ which is a prime. Hence all elements of the multiplicative group of $GF(2^3)$ except the identity $1$ are of order $7$.



From this it follows that an irreducible factor of $g(x) = x^7-1$ can only be of degree $1$, which is the case for the identity or of degree $3$. If an irreducible polynomial of $g$ would be of degree $2$, $GF(2^3)$ would have a subfield of order $4$ and at least an element of order $3$ which is not the case as we've seen above.



So we're left to find the irreducible polynomials (over $GF(2)$) of degree $3$. This is quite easy. The only polynomials of degree $3$ are:
$$x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2+1$$



Only the two last ones are irreducible.



We're done.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
    $endgroup$
    – MattP9
    Jan 13 at 20:11












  • $begingroup$
    Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
    $endgroup$
    – mathcounterexamples.net
    Jan 13 at 20:19










  • $begingroup$
    Thank you very much!
    $endgroup$
    – MattP9
    Jan 13 at 21:52
















1












$begingroup$

I note here $GF(p^n)$ the finite field of characteristic $p$ prime having $p^n$ elements.



The elements of $GF(2^3)$ are the roots of $f$ in a splitting field. Also note that the multiplicative group of $GF(2^3)$ is of order $7$ which is a prime. Hence all elements of the multiplicative group of $GF(2^3)$ except the identity $1$ are of order $7$.



From this it follows that an irreducible factor of $g(x) = x^7-1$ can only be of degree $1$, which is the case for the identity or of degree $3$. If an irreducible polynomial of $g$ would be of degree $2$, $GF(2^3)$ would have a subfield of order $4$ and at least an element of order $3$ which is not the case as we've seen above.



So we're left to find the irreducible polynomials (over $GF(2)$) of degree $3$. This is quite easy. The only polynomials of degree $3$ are:
$$x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2+1$$



Only the two last ones are irreducible.



We're done.






share|cite|improve this answer









$endgroup$













  • $begingroup$
    Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
    $endgroup$
    – MattP9
    Jan 13 at 20:11












  • $begingroup$
    Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
    $endgroup$
    – mathcounterexamples.net
    Jan 13 at 20:19










  • $begingroup$
    Thank you very much!
    $endgroup$
    – MattP9
    Jan 13 at 21:52














1












1








1





$begingroup$

I note here $GF(p^n)$ the finite field of characteristic $p$ prime having $p^n$ elements.



The elements of $GF(2^3)$ are the roots of $f$ in a splitting field. Also note that the multiplicative group of $GF(2^3)$ is of order $7$ which is a prime. Hence all elements of the multiplicative group of $GF(2^3)$ except the identity $1$ are of order $7$.



From this it follows that an irreducible factor of $g(x) = x^7-1$ can only be of degree $1$, which is the case for the identity or of degree $3$. If an irreducible polynomial of $g$ would be of degree $2$, $GF(2^3)$ would have a subfield of order $4$ and at least an element of order $3$ which is not the case as we've seen above.



So we're left to find the irreducible polynomials (over $GF(2)$) of degree $3$. This is quite easy. The only polynomials of degree $3$ are:
$$x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2+1$$



Only the two last ones are irreducible.



We're done.






share|cite|improve this answer









$endgroup$



I note here $GF(p^n)$ the finite field of characteristic $p$ prime having $p^n$ elements.



The elements of $GF(2^3)$ are the roots of $f$ in a splitting field. Also note that the multiplicative group of $GF(2^3)$ is of order $7$ which is a prime. Hence all elements of the multiplicative group of $GF(2^3)$ except the identity $1$ are of order $7$.



From this it follows that an irreducible factor of $g(x) = x^7-1$ can only be of degree $1$, which is the case for the identity or of degree $3$. If an irreducible polynomial of $g$ would be of degree $2$, $GF(2^3)$ would have a subfield of order $4$ and at least an element of order $3$ which is not the case as we've seen above.



So we're left to find the irreducible polynomials (over $GF(2)$) of degree $3$. This is quite easy. The only polynomials of degree $3$ are:
$$x^3, x^3+1, x^3+x, x^3+x+1, x^3+x^2+1$$



Only the two last ones are irreducible.



We're done.







share|cite|improve this answer












share|cite|improve this answer



share|cite|improve this answer










answered Jan 13 at 18:41









mathcounterexamples.netmathcounterexamples.net

27k22158




27k22158












  • $begingroup$
    Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
    $endgroup$
    – MattP9
    Jan 13 at 20:11












  • $begingroup$
    Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
    $endgroup$
    – mathcounterexamples.net
    Jan 13 at 20:19










  • $begingroup$
    Thank you very much!
    $endgroup$
    – MattP9
    Jan 13 at 21:52


















  • $begingroup$
    Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
    $endgroup$
    – MattP9
    Jan 13 at 20:11












  • $begingroup$
    Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
    $endgroup$
    – mathcounterexamples.net
    Jan 13 at 20:19










  • $begingroup$
    Thank you very much!
    $endgroup$
    – MattP9
    Jan 13 at 21:52
















$begingroup$
Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
$endgroup$
– MattP9
Jan 13 at 20:11






$begingroup$
Thank you for answering. If it is not a problem, I would like to have some clarification. I do not understand the following implication: Let's suppose that $g(x)=x^7−1$ has an irriducible factor of degree $2$ => $GF(2^3)$ would have a subfield of order $4$. Maybe you used the following statement: If $h(x)$ is an irriducibile factor of $g(x)=x^7−1$ of degree m then $(Z/2Z)/(h)≅GL(2^m)$. How can I prove this statement?
$endgroup$
– MattP9
Jan 13 at 20:11














$begingroup$
Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
$endgroup$
– mathcounterexamples.net
Jan 13 at 20:19




$begingroup$
Correcting your isomorphism, it is in fact $GF(2)[x]/(h) simeq GF(2^m)$. This is a standard result. See for example Finite field construction.
$endgroup$
– mathcounterexamples.net
Jan 13 at 20:19












$begingroup$
Thank you very much!
$endgroup$
– MattP9
Jan 13 at 21:52




$begingroup$
Thank you very much!
$endgroup$
– MattP9
Jan 13 at 21:52


















draft saved

draft discarded




















































Thanks for contributing an answer to Mathematics Stack Exchange!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


Use MathJax to format equations. MathJax reference.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3072331%2firreducible-factors-of-x8-x-in-z-2zx%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







Popular posts from this blog

Human spaceflight

Can not write log (Is /dev/pts mounted?) - openpty in Ubuntu-on-Windows?

張江高科駅