Mixing
Is $x^4 + 2x^2 - x + 1$ irreducible in $mathbb Z_7[x]$?
$begingroup$
How would one do this?
I know since it doesn't have roots it can only be divisible by irreducible polynomials of degree 2.
How would I prove that it is or it isn't?
There are a lot of polynomials with this conditions.
polynomials finite-fields irreducible-polynomials
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
$endgroup$
add a comment |
$begingroup$
How would one do this?
I know since it doesn't have roots it can only be divisible by irreducible polynomials of degree 2.
How would I prove that it is or it isn't?
There are a lot of polynomials with this conditions.
polynomials finite-fields irreducible-polynomials
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
$endgroup$
3
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12
add a comment |
$begingroup$
How would one do this?
I know since it doesn't have roots it can only be divisible by irreducible polynomials of degree 2.
How would I prove that it is or it isn't?
There are a lot of polynomials with this conditions.
polynomials finite-fields irreducible-polynomials
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
$endgroup$
How would one do this?
I know since it doesn't have roots it can only be divisible by irreducible polynomials of degree 2.
How would I prove that it is or it isn't?
There are a lot of polynomials with this conditions.
polynomials finite-fields irreducible-polynomials
polynomials finite-fields irreducible-polynomials
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
edited Jan 2 at 22:18
A. Pongrácz
5,9731929
5,9731929
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
asked Jan 2 at 22:10
J. DionisioJ. Dionisio
9411
9411
3
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12
add a comment |
3
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12
3
3
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The product of all the monic, irreducible polynomials over $mathbb{F}_7$ wih degree $leq 2$ is given by $x^{49}-x$, so if we prove that $f(x)=(x^2+1)^2-x$ and $x^{48}-1$ are coprime over $mathbb{F}_7[x]$ we are done. Let us compute $x^{48}-1pmod{f(x)}$, for instance through the Brauer chain $x^4to x^8to x^{16}to x^{32}to x^{48}$.
$$ x^4 equiv -2x^2+x-1pmod{f(x)} $$
$$ x^8 equiv 3x^3-3x^2+2x-3pmod{f(x)} $$
$$ x^{16} equiv x^3+3x^2+2x-1pmod{f(x)} $$
$$ x^{32} equiv -x^3+2x^2+x-3pmod{f(x)} $$
$$ x^{48}-1 equiv -x^3-2x^2+x+2 pmod{f(x)}$$
give
$$gcd(x^{48}-1,x^4+2x^2-x+1)=gcd(x^3+2x^2-x-2,x^4+2x^2-x+1) $$
$$ = gcd(x^3+2x^2-x-2,-x-3) $$
but $x=4$ is not a root of $x^3+2x^2-x-2$ since $7nmid 90$ and we have finished.
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
$endgroup$
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
add a comment |
$begingroup$
You can also try to factor it as a product of two polynomials of degree $2$. Such a factorization must have the form
begin{align}x^4 + 2x^2 - x + 1 & = (x^2+ax+b)(x^2-ax+b^{-1})\
& =x^4+(b+b^{-1}-a^2)x^2+(ab^{-1}-ab)x+1end{align}
Hence the relations
$$b+b^{-1}-a^2=2, ab^{-1}-ab=-1,$$
which can be easily seen to have no solution in $mathbb{Z}_7$.
answered Jan 2 at 22:57
moutheticsmouthetics
50127
$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%2f3060034%2fis-x4-2x2-x-1-irreducible-in-mathbb-z-7x%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The product of all the monic, irreducible polynomials over $mathbb{F}_7$ wih degree $leq 2$ is given by $x^{49}-x$, so if we prove that $f(x)=(x^2+1)^2-x$ and $x^{48}-1$ are coprime over $mathbb{F}_7[x]$ we are done. Let us compute $x^{48}-1pmod{f(x)}$, for instance through the Brauer chain $x^4to x^8to x^{16}to x^{32}to x^{48}$.
$$ x^4 equiv -2x^2+x-1pmod{f(x)} $$
$$ x^8 equiv 3x^3-3x^2+2x-3pmod{f(x)} $$
$$ x^{16} equiv x^3+3x^2+2x-1pmod{f(x)} $$
$$ x^{32} equiv -x^3+2x^2+x-3pmod{f(x)} $$
$$ x^{48}-1 equiv -x^3-2x^2+x+2 pmod{f(x)}$$
give
$$gcd(x^{48}-1,x^4+2x^2-x+1)=gcd(x^3+2x^2-x-2,x^4+2x^2-x+1) $$
$$ = gcd(x^3+2x^2-x-2,-x-3) $$
but $x=4$ is not a root of $x^3+2x^2-x-2$ since $7nmid 90$ and we have finished.
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
$endgroup$
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
add a comment |
$begingroup$
The product of all the monic, irreducible polynomials over $mathbb{F}_7$ wih degree $leq 2$ is given by $x^{49}-x$, so if we prove that $f(x)=(x^2+1)^2-x$ and $x^{48}-1$ are coprime over $mathbb{F}_7[x]$ we are done. Let us compute $x^{48}-1pmod{f(x)}$, for instance through the Brauer chain $x^4to x^8to x^{16}to x^{32}to x^{48}$.
$$ x^4 equiv -2x^2+x-1pmod{f(x)} $$
$$ x^8 equiv 3x^3-3x^2+2x-3pmod{f(x)} $$
$$ x^{16} equiv x^3+3x^2+2x-1pmod{f(x)} $$
$$ x^{32} equiv -x^3+2x^2+x-3pmod{f(x)} $$
$$ x^{48}-1 equiv -x^3-2x^2+x+2 pmod{f(x)}$$
give
$$gcd(x^{48}-1,x^4+2x^2-x+1)=gcd(x^3+2x^2-x-2,x^4+2x^2-x+1) $$
$$ = gcd(x^3+2x^2-x-2,-x-3) $$
but $x=4$ is not a root of $x^3+2x^2-x-2$ since $7nmid 90$ and we have finished.
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
$endgroup$
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
add a comment |
$begingroup$
The product of all the monic, irreducible polynomials over $mathbb{F}_7$ wih degree $leq 2$ is given by $x^{49}-x$, so if we prove that $f(x)=(x^2+1)^2-x$ and $x^{48}-1$ are coprime over $mathbb{F}_7[x]$ we are done. Let us compute $x^{48}-1pmod{f(x)}$, for instance through the Brauer chain $x^4to x^8to x^{16}to x^{32}to x^{48}$.
$$ x^4 equiv -2x^2+x-1pmod{f(x)} $$
$$ x^8 equiv 3x^3-3x^2+2x-3pmod{f(x)} $$
$$ x^{16} equiv x^3+3x^2+2x-1pmod{f(x)} $$
$$ x^{32} equiv -x^3+2x^2+x-3pmod{f(x)} $$
$$ x^{48}-1 equiv -x^3-2x^2+x+2 pmod{f(x)}$$
give
$$gcd(x^{48}-1,x^4+2x^2-x+1)=gcd(x^3+2x^2-x-2,x^4+2x^2-x+1) $$
$$ = gcd(x^3+2x^2-x-2,-x-3) $$
but $x=4$ is not a root of $x^3+2x^2-x-2$ since $7nmid 90$ and we have finished.
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
$endgroup$
The product of all the monic, irreducible polynomials over $mathbb{F}_7$ wih degree $leq 2$ is given by $x^{49}-x$, so if we prove that $f(x)=(x^2+1)^2-x$ and $x^{48}-1$ are coprime over $mathbb{F}_7[x]$ we are done. Let us compute $x^{48}-1pmod{f(x)}$, for instance through the Brauer chain $x^4to x^8to x^{16}to x^{32}to x^{48}$.
$$ x^4 equiv -2x^2+x-1pmod{f(x)} $$
$$ x^8 equiv 3x^3-3x^2+2x-3pmod{f(x)} $$
$$ x^{16} equiv x^3+3x^2+2x-1pmod{f(x)} $$
$$ x^{32} equiv -x^3+2x^2+x-3pmod{f(x)} $$
$$ x^{48}-1 equiv -x^3-2x^2+x+2 pmod{f(x)}$$
give
$$gcd(x^{48}-1,x^4+2x^2-x+1)=gcd(x^3+2x^2-x-2,x^4+2x^2-x+1) $$
$$ = gcd(x^3+2x^2-x-2,-x-3) $$
but $x=4$ is not a root of $x^3+2x^2-x-2$ since $7nmid 90$ and we have finished.
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
answered Jan 2 at 22:39
Jack D'AurizioJack D'Aurizio
288k33280659
288k33280659
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
add a comment |
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
See this answer for a generalization - an efficient algorithm often used in practice (a polynomial analog of the Pocklington-Lehmer integer primality test)
$endgroup$
– Bill Dubuque
Jan 2 at 23:13
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
$begingroup$
That's it. I spent awhile looking for a trick answer, but didn't see any. An alternative way of organizing the calculation would be to first build a list of remainders of $x^0,x^7equiv-1+3x+3x^2+3x^3,x^{14}$ and $x^{21}$ modulo $f(x)$. Raising to seventh power modulo $f(x)$ is linear, so $$x^{49}equiv-1+3x^7+3x^{14}+3x^{21}pmod{f(x)}$$ et cetera. This may help with a higher degree polynomial. I'm afraid I don't have a good feel for the difference in complexity for I usually do this in characteristic two only :-)
$endgroup$
– Jyrki Lahtonen
Jan 2 at 23:19
add a comment |
$begingroup$
You can also try to factor it as a product of two polynomials of degree $2$. Such a factorization must have the form
begin{align}x^4 + 2x^2 - x + 1 & = (x^2+ax+b)(x^2-ax+b^{-1})\
& =x^4+(b+b^{-1}-a^2)x^2+(ab^{-1}-ab)x+1end{align}
Hence the relations
$$b+b^{-1}-a^2=2, ab^{-1}-ab=-1,$$
which can be easily seen to have no solution in $mathbb{Z}_7$.
answered Jan 2 at 22:57
moutheticsmouthetics
50127
$endgroup$
add a comment |
$begingroup$
You can also try to factor it as a product of two polynomials of degree $2$. Such a factorization must have the form
begin{align}x^4 + 2x^2 - x + 1 & = (x^2+ax+b)(x^2-ax+b^{-1})\
& =x^4+(b+b^{-1}-a^2)x^2+(ab^{-1}-ab)x+1end{align}
Hence the relations
$$b+b^{-1}-a^2=2, ab^{-1}-ab=-1,$$
which can be easily seen to have no solution in $mathbb{Z}_7$.
answered Jan 2 at 22:57
moutheticsmouthetics
50127
$endgroup$
add a comment |
$begingroup$
You can also try to factor it as a product of two polynomials of degree $2$. Such a factorization must have the form
begin{align}x^4 + 2x^2 - x + 1 & = (x^2+ax+b)(x^2-ax+b^{-1})\
& =x^4+(b+b^{-1}-a^2)x^2+(ab^{-1}-ab)x+1end{align}
Hence the relations
$$b+b^{-1}-a^2=2, ab^{-1}-ab=-1,$$
which can be easily seen to have no solution in $mathbb{Z}_7$.
answered Jan 2 at 22:57
moutheticsmouthetics
50127
$endgroup$
You can also try to factor it as a product of two polynomials of degree $2$. Such a factorization must have the form
begin{align}x^4 + 2x^2 - x + 1 & = (x^2+ax+b)(x^2-ax+b^{-1})\
& =x^4+(b+b^{-1}-a^2)x^2+(ab^{-1}-ab)x+1end{align}
Hence the relations
$$b+b^{-1}-a^2=2, ab^{-1}-ab=-1,$$
which can be easily seen to have no solution in $mathbb{Z}_7$.
answered Jan 2 at 22:57
moutheticsmouthetics
50127
answered Jan 2 at 22:57
moutheticsmouthetics
50127
answered Jan 2 at 22:57
moutheticsmouthetics
50127
answered Jan 2 at 22:57
moutheticsmouthetics
50127
50127
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%2f3060034%2fis-x4-2x2-x-1-irreducible-in-mathbb-z-7x%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
3
$begingroup$
Just try to solve for the coefficients. if it factored, we'd have $p(x)=(x^2+ax+b)times (x^2+cx+d)$
$endgroup$
– lulu
Jan 2 at 22:12