How to find the root of the polynomial $x^2+x+1$ over $mathbb{Z}_2$ in this field?












1














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.










share|cite|improve this question




















  • 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














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.










share|cite|improve this question




















  • 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








1







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.










share|cite|improve this question















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






share|cite|improve this question















share|cite|improve this question













share|cite|improve this question




share|cite|improve this question








edited yesterday

























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
















  • 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












1 Answer
1






active

oldest

votes


















0














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$






share|cite|improve this answer





















    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%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









    0














    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$






    share|cite|improve this answer


























      0














      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$






      share|cite|improve this answer
























        0












        0








        0






        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$






        share|cite|improve this answer












        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$







        share|cite|improve this answer












        share|cite|improve this answer



        share|cite|improve this answer










        answered 2 days ago









        C Monsour

        5,7721224




        5,7721224






























            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.





            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.




            draft saved


            draft discarded














            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





















































            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?

            張江高科駅