Irreducible factors of $x^8 - x$ in $Z/2Z[x]$
$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?
abstract-algebra polynomials ring-theory galois-theory finite-fields
$endgroup$
add a comment |
$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?
abstract-algebra polynomials ring-theory galois-theory finite-fields
$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
add a comment |
$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?
abstract-algebra polynomials ring-theory galois-theory finite-fields
$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
abstract-algebra polynomials ring-theory galois-theory finite-fields
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
add a comment |
$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
add a comment |
1 Answer
1
active
oldest
votes
$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.
$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
add a comment |
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
$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.
$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
add a comment |
$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.
$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
add a comment |
$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.
$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.
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
add a comment |
$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
add a comment |
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
$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