Mixing
Showing existence of irreducible polynomial of degree 3 in $mathbb{F}_p$
$begingroup$
I'am trying to show that for every p$ in mathbb{N}$ where p is prime,
there is an irreducible polynomial of degree 3 in $mathbb{F}_p$.
I've found too general answers for that question, but I want to show it in the most simple way.
I know to do so for polynomial of degree 2:
the function $xmapsto x^2$ is not surjective, thus there is $ain mathbb{F}_p$ with $forall b in mathbb{F}_p $ $b^2 - a neq 0$
, which means $x^2-a$ has no roots.
But I can't do the reduction to my problem.
Thanks.
abstract-algebra ring-theory field-theory
asked Jan 12 at 21:20
Simon GreenSimon Green
825
$endgroup$
add a comment |
$begingroup$
I'am trying to show that for every p$ in mathbb{N}$ where p is prime,
there is an irreducible polynomial of degree 3 in $mathbb{F}_p$.
I've found too general answers for that question, but I want to show it in the most simple way.
I know to do so for polynomial of degree 2:
the function $xmapsto x^2$ is not surjective, thus there is $ain mathbb{F}_p$ with $forall b in mathbb{F}_p $ $b^2 - a neq 0$
, which means $x^2-a$ has no roots.
But I can't do the reduction to my problem.
Thanks.
abstract-algebra ring-theory field-theory
asked Jan 12 at 21:20
Simon GreenSimon Green
825
$endgroup$
add a comment |
$begingroup$
I'am trying to show that for every p$ in mathbb{N}$ where p is prime,
there is an irreducible polynomial of degree 3 in $mathbb{F}_p$.
I've found too general answers for that question, but I want to show it in the most simple way.
I know to do so for polynomial of degree 2:
the function $xmapsto x^2$ is not surjective, thus there is $ain mathbb{F}_p$ with $forall b in mathbb{F}_p $ $b^2 - a neq 0$
, which means $x^2-a$ has no roots.
But I can't do the reduction to my problem.
Thanks.
abstract-algebra ring-theory field-theory
asked Jan 12 at 21:20
Simon GreenSimon Green
825
$endgroup$
I'am trying to show that for every p$ in mathbb{N}$ where p is prime,
there is an irreducible polynomial of degree 3 in $mathbb{F}_p$.
I've found too general answers for that question, but I want to show it in the most simple way.
I know to do so for polynomial of degree 2:
the function $xmapsto x^2$ is not surjective, thus there is $ain mathbb{F}_p$ with $forall b in mathbb{F}_p $ $b^2 - a neq 0$
, which means $x^2-a$ has no roots.
But I can't do the reduction to my problem.
Thanks.
abstract-algebra ring-theory field-theory
abstract-algebra ring-theory field-theory
asked Jan 12 at 21:20
Simon GreenSimon Green
825
asked Jan 12 at 21:20
Simon GreenSimon Green
825
asked Jan 12 at 21:20
Simon GreenSimon Green
825
asked Jan 12 at 21:20
Simon GreenSimon Green
825
asked Jan 12 at 21:20
Simon GreenSimon Green
825
825
add a comment |
add a comment |
4 Answers
4
active
oldest
votes
$begingroup$
For something in the same spirit as the example for $2$: $x^3-x=(x+1)x(x-1)$ has three zeros (two for $p=2$), so it can't be surjective. Thus some $x^3-x-a$ has no zeros, and a cubic with no linear factors is irreducible.
This approach won't generalize any further; we need to account for more than just linear factors to verify that a polynomial of degree $ge 4$ is irreducible.
Oh, and your example for quadratic polynomials isn't quite universal; both $x^2=xcdot x$ and $x^2+1=(x+1)(x+1)$ factor for $p=2$. We need a special case $(x^2+x+1)$ for that.
edited Jan 12 at 22:17
Chris Custer
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
$endgroup$
add a comment |
$begingroup$
Let $a_1$ and $a_2$ be distinct elements in $mathbb{F}_p$. Next let $c in mathbb{F}_p$ be such that $a^3_1-a^3_2 = c(a_1 - a_2)$, there exists such a $c$ as $a_1 not = a_2$. Then the mapping $f: x mapsto x^3- cx$; $x in mathbb{F}_p$ is not surjective mapping from $mathbb{F}_p$ onto $mathbb{F}_p$, as there exist two distinct $a_1,a_2 in mathbb{F}_p$ satisfying $f(a_1)=f(a_2)$. So for this particular $c$, there exists an $A in mathbb{F}_p$ such that there is no $x in mathbb{F}_p$ that satisfies $x^3-cx = A$. Thus the polynomial $x^3-cx-A$ is irreducible in $mathbb{F}_p$.
answered Jan 12 at 21:31
MikeMike
3,981412
$endgroup$
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
add a comment |
$begingroup$
Count.
Find the number of monic (irreducible) polynomials of degree $1$.
Then count the number of monic polynomials of degree $2$ and subtract the number of reducible ones (they factor) to find the number of irreducible quadratics.
Now do the same for degree $3$. The reducible ones factor into three linear factors or one linear factor and an irreducible quadratic.
This method can be generalized.
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
$endgroup$
add a comment |
$begingroup$
If a degree $3$ polynomial is reducible over a field, then it has a root. So you (just) need a degree $3$ polynomial without a root.
There are $frac{p^3-p}3$ monic irreducible polynomials of degree $3$, according to this argument.
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
$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%2f3071406%2fshowing-existence-of-irreducible-polynomial-of-degree-3-in-mathbbf-p%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
4 Answers
4
active
oldest
votes
4 Answers
4
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
For something in the same spirit as the example for $2$: $x^3-x=(x+1)x(x-1)$ has three zeros (two for $p=2$), so it can't be surjective. Thus some $x^3-x-a$ has no zeros, and a cubic with no linear factors is irreducible.
This approach won't generalize any further; we need to account for more than just linear factors to verify that a polynomial of degree $ge 4$ is irreducible.
Oh, and your example for quadratic polynomials isn't quite universal; both $x^2=xcdot x$ and $x^2+1=(x+1)(x+1)$ factor for $p=2$. We need a special case $(x^2+x+1)$ for that.
edited Jan 12 at 22:17
Chris Custer
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
$endgroup$
add a comment |
$begingroup$
For something in the same spirit as the example for $2$: $x^3-x=(x+1)x(x-1)$ has three zeros (two for $p=2$), so it can't be surjective. Thus some $x^3-x-a$ has no zeros, and a cubic with no linear factors is irreducible.
This approach won't generalize any further; we need to account for more than just linear factors to verify that a polynomial of degree $ge 4$ is irreducible.
Oh, and your example for quadratic polynomials isn't quite universal; both $x^2=xcdot x$ and $x^2+1=(x+1)(x+1)$ factor for $p=2$. We need a special case $(x^2+x+1)$ for that.
edited Jan 12 at 22:17
Chris Custer
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
$endgroup$
add a comment |
$begingroup$
For something in the same spirit as the example for $2$: $x^3-x=(x+1)x(x-1)$ has three zeros (two for $p=2$), so it can't be surjective. Thus some $x^3-x-a$ has no zeros, and a cubic with no linear factors is irreducible.
This approach won't generalize any further; we need to account for more than just linear factors to verify that a polynomial of degree $ge 4$ is irreducible.
Oh, and your example for quadratic polynomials isn't quite universal; both $x^2=xcdot x$ and $x^2+1=(x+1)(x+1)$ factor for $p=2$. We need a special case $(x^2+x+1)$ for that.
edited Jan 12 at 22:17
Chris Custer
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
$endgroup$
For something in the same spirit as the example for $2$: $x^3-x=(x+1)x(x-1)$ has three zeros (two for $p=2$), so it can't be surjective. Thus some $x^3-x-a$ has no zeros, and a cubic with no linear factors is irreducible.
This approach won't generalize any further; we need to account for more than just linear factors to verify that a polynomial of degree $ge 4$ is irreducible.
Oh, and your example for quadratic polynomials isn't quite universal; both $x^2=xcdot x$ and $x^2+1=(x+1)(x+1)$ factor for $p=2$. We need a special case $(x^2+x+1)$ for that.
edited Jan 12 at 22:17
Chris Custer
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
edited Jan 12 at 22:17
Chris Custer
13.1k3827
edited Jan 12 at 22:17
Chris Custer
13.1k3827
edited Jan 12 at 22:17
Chris Custer
13.1k3827
13.1k3827
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
answered Jan 12 at 21:40
jmerryjmerry
8,2531022
8,2531022
add a comment |
add a comment |
$begingroup$
Let $a_1$ and $a_2$ be distinct elements in $mathbb{F}_p$. Next let $c in mathbb{F}_p$ be such that $a^3_1-a^3_2 = c(a_1 - a_2)$, there exists such a $c$ as $a_1 not = a_2$. Then the mapping $f: x mapsto x^3- cx$; $x in mathbb{F}_p$ is not surjective mapping from $mathbb{F}_p$ onto $mathbb{F}_p$, as there exist two distinct $a_1,a_2 in mathbb{F}_p$ satisfying $f(a_1)=f(a_2)$. So for this particular $c$, there exists an $A in mathbb{F}_p$ such that there is no $x in mathbb{F}_p$ that satisfies $x^3-cx = A$. Thus the polynomial $x^3-cx-A$ is irreducible in $mathbb{F}_p$.
answered Jan 12 at 21:31
MikeMike
3,981412
$endgroup$
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
add a comment |
$begingroup$
Let $a_1$ and $a_2$ be distinct elements in $mathbb{F}_p$. Next let $c in mathbb{F}_p$ be such that $a^3_1-a^3_2 = c(a_1 - a_2)$, there exists such a $c$ as $a_1 not = a_2$. Then the mapping $f: x mapsto x^3- cx$; $x in mathbb{F}_p$ is not surjective mapping from $mathbb{F}_p$ onto $mathbb{F}_p$, as there exist two distinct $a_1,a_2 in mathbb{F}_p$ satisfying $f(a_1)=f(a_2)$. So for this particular $c$, there exists an $A in mathbb{F}_p$ such that there is no $x in mathbb{F}_p$ that satisfies $x^3-cx = A$. Thus the polynomial $x^3-cx-A$ is irreducible in $mathbb{F}_p$.
answered Jan 12 at 21:31
MikeMike
3,981412
$endgroup$
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
add a comment |
$begingroup$
Let $a_1$ and $a_2$ be distinct elements in $mathbb{F}_p$. Next let $c in mathbb{F}_p$ be such that $a^3_1-a^3_2 = c(a_1 - a_2)$, there exists such a $c$ as $a_1 not = a_2$. Then the mapping $f: x mapsto x^3- cx$; $x in mathbb{F}_p$ is not surjective mapping from $mathbb{F}_p$ onto $mathbb{F}_p$, as there exist two distinct $a_1,a_2 in mathbb{F}_p$ satisfying $f(a_1)=f(a_2)$. So for this particular $c$, there exists an $A in mathbb{F}_p$ such that there is no $x in mathbb{F}_p$ that satisfies $x^3-cx = A$. Thus the polynomial $x^3-cx-A$ is irreducible in $mathbb{F}_p$.
answered Jan 12 at 21:31
MikeMike
3,981412
$endgroup$
Let $a_1$ and $a_2$ be distinct elements in $mathbb{F}_p$. Next let $c in mathbb{F}_p$ be such that $a^3_1-a^3_2 = c(a_1 - a_2)$, there exists such a $c$ as $a_1 not = a_2$. Then the mapping $f: x mapsto x^3- cx$; $x in mathbb{F}_p$ is not surjective mapping from $mathbb{F}_p$ onto $mathbb{F}_p$, as there exist two distinct $a_1,a_2 in mathbb{F}_p$ satisfying $f(a_1)=f(a_2)$. So for this particular $c$, there exists an $A in mathbb{F}_p$ such that there is no $x in mathbb{F}_p$ that satisfies $x^3-cx = A$. Thus the polynomial $x^3-cx-A$ is irreducible in $mathbb{F}_p$.
answered Jan 12 at 21:31
MikeMike
3,981412
edited Jan 12 at 21:37
answered Jan 12 at 21:31
MikeMike
3,981412
answered Jan 12 at 21:31
MikeMike
3,981412
answered Jan 12 at 21:31
MikeMike
3,981412
3,981412
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
add a comment |
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
The $c$ in question is simply $a_1^2+a_1a_2+a_2^2$, as in any commutative ring.
$endgroup$
– Bernard
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
$begingroup$
*.....as any factorable degree-3 monic polynomial $p$ in a field $F$ has a factor of the form $(x-C)$ for some $C in F$. Or equivalently, some $C in F$ s.t. $p(C) = 0$
$endgroup$
– Mike
Jan 12 at 21:55
add a comment |
$begingroup$
Count.
Find the number of monic (irreducible) polynomials of degree $1$.
Then count the number of monic polynomials of degree $2$ and subtract the number of reducible ones (they factor) to find the number of irreducible quadratics.
Now do the same for degree $3$. The reducible ones factor into three linear factors or one linear factor and an irreducible quadratic.
This method can be generalized.
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
$endgroup$
add a comment |
$begingroup$
Count.
Find the number of monic (irreducible) polynomials of degree $1$.
Then count the number of monic polynomials of degree $2$ and subtract the number of reducible ones (they factor) to find the number of irreducible quadratics.
Now do the same for degree $3$. The reducible ones factor into three linear factors or one linear factor and an irreducible quadratic.
This method can be generalized.
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
$endgroup$
add a comment |
$begingroup$
Count.
Find the number of monic (irreducible) polynomials of degree $1$.
Then count the number of monic polynomials of degree $2$ and subtract the number of reducible ones (they factor) to find the number of irreducible quadratics.
Now do the same for degree $3$. The reducible ones factor into three linear factors or one linear factor and an irreducible quadratic.
This method can be generalized.
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
$endgroup$
Count.
Find the number of monic (irreducible) polynomials of degree $1$.
Then count the number of monic polynomials of degree $2$ and subtract the number of reducible ones (they factor) to find the number of irreducible quadratics.
Now do the same for degree $3$. The reducible ones factor into three linear factors or one linear factor and an irreducible quadratic.
This method can be generalized.
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
answered Jan 12 at 21:43
Ethan BolkerEthan Bolker
43k549114
43k549114
add a comment |
add a comment |
$begingroup$
If a degree $3$ polynomial is reducible over a field, then it has a root. So you (just) need a degree $3$ polynomial without a root.
There are $frac{p^3-p}3$ monic irreducible polynomials of degree $3$, according to this argument.
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
$endgroup$
add a comment |
$begingroup$
If a degree $3$ polynomial is reducible over a field, then it has a root. So you (just) need a degree $3$ polynomial without a root.
There are $frac{p^3-p}3$ monic irreducible polynomials of degree $3$, according to this argument.
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
$endgroup$
add a comment |
$begingroup$
If a degree $3$ polynomial is reducible over a field, then it has a root. So you (just) need a degree $3$ polynomial without a root.
There are $frac{p^3-p}3$ monic irreducible polynomials of degree $3$, according to this argument.
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
$endgroup$
If a degree $3$ polynomial is reducible over a field, then it has a root. So you (just) need a degree $3$ polynomial without a root.
There are $frac{p^3-p}3$ monic irreducible polynomials of degree $3$, according to this argument.
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
edited Jan 13 at 0:21
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
answered Jan 12 at 22:47
Chris CusterChris Custer
13.1k3827
13.1k3827
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%2f3071406%2fshowing-existence-of-irreducible-polynomial-of-degree-3-in-mathbbf-p%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
