How to find the root of the polynomial $x^2+x+1$ over $mathbb{Z}_2$ in this field?
$begingroup$
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 Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
$endgroup$
|
show 1 more comment
$begingroup$
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 Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
$endgroup$
1
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
1
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
1
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46
|
show 1 more comment
$begingroup$
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 Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
$endgroup$
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 Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
asked Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
edited Dec 26 '18 at 13:01
Jamie Carr
asked Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
asked Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
asked Dec 25 '18 at 17:27
Jamie CarrJamie Carr
495
495
1
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
1
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
1
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46
|
show 1 more comment
1
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
1
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
1
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46
1
1
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
1
1
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
1
1
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46
|
show 1 more comment
1 Answer
1
active
oldest
votes
$begingroup$
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 Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
$endgroup$
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
$begingroup$
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 Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
$endgroup$
add a comment |
$begingroup$
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 Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
$endgroup$
add a comment |
$begingroup$
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 Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
$endgroup$
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 Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
answered Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
answered Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
answered Dec 25 '18 at 19:54
C MonsourC Monsour
6,2641325
6,2641325
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.
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
$begingroup$
The element $x+I$ is not a root of $x^2+x+1=0$. Try $x^5+I$.
$endgroup$
– Lord Shark the Unknown
Dec 25 '18 at 17:32
$begingroup$
I think $F$ only contains cosets $I+p(x)$ where the degree of p(x) is less than 4.
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:39
1
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:42
$begingroup$
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.
$endgroup$
– Jyrki Lahtonen
Dec 25 '18 at 17:44
1
$begingroup$
@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?
$endgroup$
– Jamie Carr
Dec 25 '18 at 17:46