How to find the root of the polynomial $x^2+x+1$ over $mathbb{Z}_2$ in this field?
I am having some troubles understanding the proof for a statement. The question is:
Suppose R is the polynomial ring $mathbb{Z}_2[x]$. Let $(x^4+x+1)$, I, be the principal ideal of this ring. Therefore, the quotient ring $frac{mathbb{Z}_2[x]}{I}$, F, is a field as $x^4+x+1$ is irreducible.
Then, the question asks to prove that:
every quadratic polynomial over $mathbb{Z}_2[x]$ has a root in F.
It is easy to prove for reducible quadratic polynomial because they have roots $I+0$ or $I+1$. So, what we only need to consider is the polynomial $x^2+x+1$, which is irreducible over $mathbb{Z}_2[x]$.
The proof directly says that $I+x^5 in F$ is such a root of $x^2+x+1$. It is not clear for me why $I+x^{10}+x^5+1 = I$ in this case. This is confusing for me. Please give me some help on this part, thanks!
Plus, the proof before states that ''if $alpha in F$, then $alpha^{15}=1$'', which I understand but don't know how to use.
group-theory polynomials field-theory modular-arithmetic finite-fields
asked 2 days ago
Jamie Carr
494
|
show 1 more comment
I am having some troubles understanding the proof for a statement. The question is:
Suppose R is the polynomial ring $mathbb{Z}_2[x]$. Let $(x^4+x+1)$, I, be the principal ideal of this ring. Therefore, the quotient ring $frac{mathbb{Z}_2[x]}{I}$, F, is a field as $x^4+x+1$ is irreducible.
Then, the question asks to prove that:
every quadratic polynomial over $mathbb{Z}_2[x]$ has a root in F.
It is easy to prove for reducible quadratic polynomial because they have roots $I+0$ or $I+1$. So, what we only need to consider is the polynomial $x^2+x+1$, which is irreducible over $mathbb{Z}_2[x]$.
The proof directly says that $I+x^5 in F$ is such a root of $x^2+x+1$. It is not clear for me why $I+x^{10}+x^5+1 = I$ in this case. This is confusing for me. Please give me some help on this part, thanks!
Plus, the proof before states that ''if $alpha in F$, then $alpha^{15}=1$'', which I understand but don't know how to use.
group-theory polynomials field-theory modular-arithmetic finite-fields
asked 2 days ago
Jamie Carr
494
1
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
1
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
1
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago
|
show 1 more comment
I am having some troubles understanding the proof for a statement. The question is:
Suppose R is the polynomial ring $mathbb{Z}_2[x]$. Let $(x^4+x+1)$, I, be the principal ideal of this ring. Therefore, the quotient ring $frac{mathbb{Z}_2[x]}{I}$, F, is a field as $x^4+x+1$ is irreducible.
Then, the question asks to prove that:
every quadratic polynomial over $mathbb{Z}_2[x]$ has a root in F.
It is easy to prove for reducible quadratic polynomial because they have roots $I+0$ or $I+1$. So, what we only need to consider is the polynomial $x^2+x+1$, which is irreducible over $mathbb{Z}_2[x]$.
The proof directly says that $I+x^5 in F$ is such a root of $x^2+x+1$. It is not clear for me why $I+x^{10}+x^5+1 = I$ in this case. This is confusing for me. Please give me some help on this part, thanks!
Plus, the proof before states that ''if $alpha in F$, then $alpha^{15}=1$'', which I understand but don't know how to use.
group-theory polynomials field-theory modular-arithmetic finite-fields
asked 2 days ago
Jamie Carr
494
I am having some troubles understanding the proof for a statement. The question is:
Suppose R is the polynomial ring $mathbb{Z}_2[x]$. Let $(x^4+x+1)$, I, be the principal ideal of this ring. Therefore, the quotient ring $frac{mathbb{Z}_2[x]}{I}$, F, is a field as $x^4+x+1$ is irreducible.
Then, the question asks to prove that:
every quadratic polynomial over $mathbb{Z}_2[x]$ has a root in F.
It is easy to prove for reducible quadratic polynomial because they have roots $I+0$ or $I+1$. So, what we only need to consider is the polynomial $x^2+x+1$, which is irreducible over $mathbb{Z}_2[x]$.
The proof directly says that $I+x^5 in F$ is such a root of $x^2+x+1$. It is not clear for me why $I+x^{10}+x^5+1 = I$ in this case. This is confusing for me. Please give me some help on this part, thanks!
Plus, the proof before states that ''if $alpha in F$, then $alpha^{15}=1$'', which I understand but don't know how to use.
group-theory polynomials field-theory modular-arithmetic finite-fields
group-theory polynomials field-theory modular-arithmetic finite-fields
asked 2 days ago
Jamie Carr
494
asked 2 days ago
Jamie Carr
494
edited yesterday
asked 2 days ago
Jamie Carr
494
asked 2 days ago
Jamie Carr
494
asked 2 days ago
Jamie Carr
494
494
1
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
1
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
1
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago
|
show 1 more comment
1
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
1
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
1
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago
1
1
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
1
1
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
1
1
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago
|
show 1 more comment
1 Answer
1
active
oldest
votes
In the following GF(q) indicates the unique finite field or order q.
Use degrees and the uniqueness of finite fields of a given order. Since $x^4+x+1$ is irreducible, $GF(2)[x]/I$ has degree 4 over $GF(2)$ and thus has order $2^4=16$, and so is $GF(16)$. Irreducible quadratic polynomials over $GF(2)$ split in a degree 2 extension, which has order $2^2=4$ and thus is $GF(4)$. By uniqueness of Galois fields, any degree 2 extension of $GF(4)$ must be $GF(16)$ since $4^2=16$. Thus $GF(4) subset GF(16)=F$ and any quadratic over $GF(2)$ splits over $GF(4)$, so we are done.
$a^{15}=1$ for all $ain F$ since the multiplicative group of $F$ has order $16-1=15$
answered 2 days ago
C Monsour
5,7721224
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%2f3052297%2fhow-to-find-the-root-of-the-polynomial-x2x1-over-mathbbz-2-in-this-fie%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
In the following GF(q) indicates the unique finite field or order q.
Use degrees and the uniqueness of finite fields of a given order. Since $x^4+x+1$ is irreducible, $GF(2)[x]/I$ has degree 4 over $GF(2)$ and thus has order $2^4=16$, and so is $GF(16)$. Irreducible quadratic polynomials over $GF(2)$ split in a degree 2 extension, which has order $2^2=4$ and thus is $GF(4)$. By uniqueness of Galois fields, any degree 2 extension of $GF(4)$ must be $GF(16)$ since $4^2=16$. Thus $GF(4) subset GF(16)=F$ and any quadratic over $GF(2)$ splits over $GF(4)$, so we are done.
$a^{15}=1$ for all $ain F$ since the multiplicative group of $F$ has order $16-1=15$
answered 2 days ago
C Monsour
5,7721224
add a comment |
In the following GF(q) indicates the unique finite field or order q.
Use degrees and the uniqueness of finite fields of a given order. Since $x^4+x+1$ is irreducible, $GF(2)[x]/I$ has degree 4 over $GF(2)$ and thus has order $2^4=16$, and so is $GF(16)$. Irreducible quadratic polynomials over $GF(2)$ split in a degree 2 extension, which has order $2^2=4$ and thus is $GF(4)$. By uniqueness of Galois fields, any degree 2 extension of $GF(4)$ must be $GF(16)$ since $4^2=16$. Thus $GF(4) subset GF(16)=F$ and any quadratic over $GF(2)$ splits over $GF(4)$, so we are done.
$a^{15}=1$ for all $ain F$ since the multiplicative group of $F$ has order $16-1=15$
answered 2 days ago
C Monsour
5,7721224
add a comment |
In the following GF(q) indicates the unique finite field or order q.
Use degrees and the uniqueness of finite fields of a given order. Since $x^4+x+1$ is irreducible, $GF(2)[x]/I$ has degree 4 over $GF(2)$ and thus has order $2^4=16$, and so is $GF(16)$. Irreducible quadratic polynomials over $GF(2)$ split in a degree 2 extension, which has order $2^2=4$ and thus is $GF(4)$. By uniqueness of Galois fields, any degree 2 extension of $GF(4)$ must be $GF(16)$ since $4^2=16$. Thus $GF(4) subset GF(16)=F$ and any quadratic over $GF(2)$ splits over $GF(4)$, so we are done.
$a^{15}=1$ for all $ain F$ since the multiplicative group of $F$ has order $16-1=15$
answered 2 days ago
C Monsour
5,7721224
In the following GF(q) indicates the unique finite field or order q.
Use degrees and the uniqueness of finite fields of a given order. Since $x^4+x+1$ is irreducible, $GF(2)[x]/I$ has degree 4 over $GF(2)$ and thus has order $2^4=16$, and so is $GF(16)$. Irreducible quadratic polynomials over $GF(2)$ split in a degree 2 extension, which has order $2^2=4$ and thus is $GF(4)$. By uniqueness of Galois fields, any degree 2 extension of $GF(4)$ must be $GF(16)$ since $4^2=16$. Thus $GF(4) subset GF(16)=F$ and any quadratic over $GF(2)$ splits over $GF(4)$, so we are done.
$a^{15}=1$ for all $ain F$ since the multiplicative group of $F$ has order $16-1=15$
answered 2 days ago
C Monsour
5,7721224
answered 2 days ago
C Monsour
5,7721224
answered 2 days ago
C Monsour
5,7721224
answered 2 days ago
C Monsour
5,7721224
5,7721224
add a comment |
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f3052297%2fhow-to-find-the-root-of-the-polynomial-x2x1-over-mathbbz-2-in-this-fie%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
1
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
– Lord Shark the Unknown
2 days ago
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
– Jamie Carr
2 days ago
1
Jamie, every coset of $I$ contains a unique representative of degree less than 4. Find the one in the coset of $x^5$ and you will be done.
– Jyrki Lahtonen
2 days ago
And, if you get stuck, you can take a look at this Q&A I prepared for referrals. You see, the zeros of $x^2+x+1$ are in the subfield of four elements (do you see why?), and I had to calculate those in the last example.
– Jyrki Lahtonen
2 days ago
1
@LordSharktheUnknown Thank you, if I'm not misunderstanding your point, I think $I+x^5=I+x^2+x$ in this case? Plus, how did you come up with x^5 in advance?
– Jamie Carr
2 days ago