Mixing
Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than 5
$begingroup$
Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than $5$.
This is what I tried:
It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.
Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.
My question is: is there any easier way to find these polynomials?
P.S.: this is not exactly homework, but a question which I came across while studying for an exam.
abstract-algebra finite-fields irreducible-polynomials
edited May 17 '15 at 9:24
user26857
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
$endgroup$
add a comment |
$begingroup$
Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than $5$.
This is what I tried:
It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.
Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.
My question is: is there any easier way to find these polynomials?
P.S.: this is not exactly homework, but a question which I came across while studying for an exam.
abstract-algebra finite-fields irreducible-polynomials
edited May 17 '15 at 9:24
user26857
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
$endgroup$
1
$begingroup$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
6
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09
add a comment |
$begingroup$
Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than $5$.
This is what I tried:
It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.
Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.
My question is: is there any easier way to find these polynomials?
P.S.: this is not exactly homework, but a question which I came across while studying for an exam.
abstract-algebra finite-fields irreducible-polynomials
edited May 17 '15 at 9:24
user26857
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
$endgroup$
Find all irreducible monic polynomials in $mathbb{Z}/(2)[x]$ with degree equal or less than $5$.
This is what I tried:
It's evident that $x,x+1$ are irreducible. Then, use these to find all reducible polynomials of degree 2. There ones that can't be made are irreducible. Then use these to make polynomials of degree 3, the ones that can't be made are irreducible. Repeat until degree 5.
Doing this way takes way too long and I just gave up during when I was about to reach degree 4 polynomials.
My question is: is there any easier way to find these polynomials?
P.S.: this is not exactly homework, but a question which I came across while studying for an exam.
abstract-algebra finite-fields irreducible-polynomials
abstract-algebra finite-fields irreducible-polynomials
edited May 17 '15 at 9:24
user26857
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
edited May 17 '15 at 9:24
user26857
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
edited May 17 '15 at 9:24
user26857
39.4k124183
edited May 17 '15 at 9:24
user26857
39.4k124183
edited May 17 '15 at 9:24
user26857
39.4k124183
39.4k124183
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
asked Apr 11 '11 at 0:46
Leonardo FontouraLeonardo Fontoura
5891817
5891817
1
$begingroup$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
6
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09
add a comment |
1
$begingroup$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
6
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09
1
1
$begingroup$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
6
6
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09
add a comment |
3 Answers
3
active
oldest
votes
$begingroup$
Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $mathbb{Z}_2[x]$ of degree $leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
edited Jan 8 '14 at 7:53
Community♦
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
$endgroup$
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
add a comment |
$begingroup$
The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.
In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.
Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $dfrac{x^{16}-x}{(x^2+x+1)x(x+1)} = 1 + x^3 + x^6 + x^9 + x^{12}:. $ So we know that there are $3$ primes of order $4$.
Finally, the products of the primes of degree $5$ must be $ dfrac{x^{32}-x}{x(x+1)} = 1 + x + x^2 +:cdots: + x^{30}$.
Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
$endgroup$
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
add a comment |
$begingroup$
As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).
The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:
$x^2 + x + 1$
Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.
$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]
For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
$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%2f32197%2ffind-all-irreducible-monic-polynomials-in-mathbbz-2x-with-degree-equal%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $mathbb{Z}_2[x]$ of degree $leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
edited Jan 8 '14 at 7:53
Community♦
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
$endgroup$
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
add a comment |
$begingroup$
Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $mathbb{Z}_2[x]$ of degree $leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
edited Jan 8 '14 at 7:53
Community♦
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
$endgroup$
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
add a comment |
$begingroup$
Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $mathbb{Z}_2[x]$ of degree $leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
edited Jan 8 '14 at 7:53
Community♦
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
$endgroup$
Extrapolated Comments converted to answer:
First, we note that there are $2^n$ polynomials in $mathbb{Z}_2[x]$ of degree $n$.
A polynomial $p(x)$ of degree $2$ or $3$ is irreducible if and only if it does not have linear factors. Therefore, it suffices to show that $p(0) = p(1) = 1$. This quickly tells us that $x^2 + x + 1$ is the only irreducible polynomial of degree $2$. This also tells us that $x^3 + x^2 + 1$ and $x^3 + x + 1$ are the only irreducible polynomials of degree $3$.
As hardmath points out, for a polynomial $p(x)$ of degree $4$ or $5$ to be irreducible, it suffices to show that $p(x)$ has no linear or quadratic factors. To rule out the linear factors, we can again throw out any polynomial not satisfying $p(0) = p(1) = 1$. That is, we can throw out any polynomial with constant term $0$, and we can throw out any polynomial with an even number of terms. This rules out $3/4$ of the polynomials. For example, the $4^{th}$ degree polynomials which do not have linear factors are:
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x^2 + 1 $
- $ x^4 + x + 1 $
The $5^{th}$ degree polynomials which do not contain linear factors are:
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^4 + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
- $x^5 + x + 1$
It still remains to check whether $x^2 + x + 1$ (which is the only quadratic irreducible polynomial in $mathbb{Z}_2[x]$) divides any of these polynomials. This can be done by hand for sufficiently small degrees. Again, as hardmath points out, since $x^2 + x + 1$ is the only irreducible polynomial of degree $2$, it follows that $(x^2 + x + 1)^2 = x^4 + x^2 + 1$ is the only polynomial of degree $4$ which does not have linear factors and yet is not irreducible. Therefore, the other $3$ polynomials listed must be irreducible. Similarly, for degree $5$ polynomials, we can rule out
$$
(x^2 + x + 1)(x^3 + x^2 + 1) = x^5 + x + 1
$$
and
$$
(x^2 + x + 1)(x^3 + x + 1) = x^5 + x^4 + 1.
$$
The other $6$ listed polynomials must therefore be irreducible.
Notice that this trick of throwing out polynomials with linear factors, then quadratic factors, etc. (which hardmath called akin to the Sieve of Eratosthenes) is not efficient for large degree polynomials (even degree $6$ starts to be a problem, as a polynomial of degree $6$ can factor as a product of to polynomials of degree $3$). This method, therefore only works for sufficiently small degree polynomials.
To recap, the irreducible polynomials in $mathbb{Z}_2[x]$ of degree $leq 5$ are:
- $x$
- $x+1$
- $x^2 + x + 1$
- $x^3 + x^2 + 1$
- $x^3 + x + 1$
- $ x^4 + x^3 + x^2 + x + 1 $
- $ x^4 + x^3 + 1 $
- $ x^4 + x + 1 $
- $x^5 + x^4 + x^3 + x^2 + 1$
- $x^5 + x^4 + x^3 + x + 1$
- $x^5 + x^4 + x^2 + x + 1$
- $x^5 + x^3 + x^2 + x + 1$
- $x^5 + x^3 + 1$
- $x^5 + x^2 + 1$
edited Jan 8 '14 at 7:53
Community♦
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
edited Jan 8 '14 at 7:53
Community♦
1
edited Jan 8 '14 at 7:53
Community♦
1
edited Jan 8 '14 at 7:53
Community♦
1
1
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
answered Apr 11 '11 at 23:31
JavaManJavaMan
11.1k12655
11.1k12655
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
add a comment |
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Very good and concise answer.
$endgroup$
– Leonardo Fontoura
Apr 13 '11 at 3:15
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
Thanks! Credit should also go to @Hardmath for pointing out the bit about quadratics.
$endgroup$
– JavaMan
Apr 13 '11 at 3:17
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
$begingroup$
This is amazing, thanks!
$endgroup$
– Galois in the Field
Oct 2 '15 at 11:26
add a comment |
$begingroup$
The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.
In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.
Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $dfrac{x^{16}-x}{(x^2+x+1)x(x+1)} = 1 + x^3 + x^6 + x^9 + x^{12}:. $ So we know that there are $3$ primes of order $4$.
Finally, the products of the primes of degree $5$ must be $ dfrac{x^{32}-x}{x(x+1)} = 1 + x + x^2 +:cdots: + x^{30}$.
Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
$endgroup$
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
add a comment |
$begingroup$
The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.
In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.
Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $dfrac{x^{16}-x}{(x^2+x+1)x(x+1)} = 1 + x^3 + x^6 + x^9 + x^{12}:. $ So we know that there are $3$ primes of order $4$.
Finally, the products of the primes of degree $5$ must be $ dfrac{x^{32}-x}{x(x+1)} = 1 + x + x^2 +:cdots: + x^{30}$.
Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
$endgroup$
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
add a comment |
$begingroup$
The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.
In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.
Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $dfrac{x^{16}-x}{(x^2+x+1)x(x+1)} = 1 + x^3 + x^6 + x^9 + x^{12}:. $ So we know that there are $3$ primes of order $4$.
Finally, the products of the primes of degree $5$ must be $ dfrac{x^{32}-x}{x(x+1)} = 1 + x + x^2 +:cdots: + x^{30}$.
Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
$endgroup$
The tricky way to do this is to realize that if $p(x)$ is prime polynomial of degree $n$, then ${mathbb{Z}_2[z]}/{p(z)}$ is a field of order $2^n$ and hence for every element $a$ of the field, $ a^{2^n}-a = 0$. In particular, then, $z^{2^n}-z$ must be divisible by $p(z)$. Now, $z^{2^n}-z$ is also divisible by any prime polynomial of degree $d|n$, so we first have to factor those out, and then you get the product of the primes of degree $n$.
In particular, $x^8-x$ must be a product of the primes of degree one and the primes of degree $3$. We can easily factor out $x(x+1),$ and we see that the primes of degree $3$ must multiply together to get $x^6+x^5+x^4+x^3+x^2+x+1$. So you can test for primeness of a polynomial of degree $3$ by seeing if it divides into this polynomial.
Similarly, for $n=4$, you have $x^{16}-x$ must be the product of the primes of degrees $1,2$ and $4$. The only prime of degree $2$ is $x^2+x+1,$ so the product of the primes of degree $4$ must be $dfrac{x^{16}-x}{(x^2+x+1)x(x+1)} = 1 + x^3 + x^6 + x^9 + x^{12}:. $ So we know that there are $3$ primes of order $4$.
Finally, the products of the primes of degree $5$ must be $ dfrac{x^{32}-x}{x(x+1)} = 1 + x + x^2 +:cdots: + x^{30}$.
Note that the primes of degree $3$ have to be $x^3+x+1$ and $x^3+x^2+1$. That's because if $p(x)$ is prime, then $p(1)=1$ and $p(0)=1$. So we have to have $x^3$ and $1$ as terms f $p(x)$, and we have to have an odd number of non-zero terms in $p(x)$.
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
edited Apr 1 '15 at 16:46
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
answered Apr 11 '11 at 1:39
Thomas AndrewsThomas Andrews
130k11146297
130k11146297
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
add a comment |
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
1
1
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
$begingroup$
I'm not sure if I find this easier or not. ):
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:49
2
2
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
Yeah,this trick is really more useful for higher degrees.
$endgroup$
– Thomas Andrews
Apr 11 '11 at 1:54
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
$begingroup$
This gives a useful short cut to know the number of polynomials you are looking for and also a way of checking once all are found.
$endgroup$
– Mark Bennet
Oct 6 '18 at 15:16
add a comment |
$begingroup$
As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).
The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:
$x^2 + x + 1$
Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.
$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]
For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
$endgroup$
add a comment |
$begingroup$
As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).
The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:
$x^2 + x + 1$
Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.
$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]
For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
$endgroup$
add a comment |
$begingroup$
As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).
The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:
$x^2 + x + 1$
Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.
$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]
For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
$endgroup$
As DJC points out, much of the spade work is noticing which polynomials have linear factors, or equivalently which have roots at 0 or 1. This is sufficient to check quadratic and cubic polynomials (mod 2).
The only other thing to rule out (in finding irreducible polynomials of degree 5 or less) is a quadratic factor! So by analogy with the Sieve of Eratosthenes, let's use the evaluation at 0 and 1 (constant term not 0 and number of nonzero coefficients odd) to quickly list all the irreducible polynomials (mod 2) of degree 2:
$x^2 + x + 1$
Then a polynomial (mod 2) of degree 4 or 5 is irreducible if and only if in addition to not having a root at x = 0 or x = 1, the polynomial does not have the one irreducible quadratic above as a factor. For degree 4 it is only possible to have the quadratic factor but no linear one if the polynomial is the quadratic irreducible squared, so that's just one case to check.
$(x^2 + x + 1)^2 = x^4 + x^2 + 1$
[reducible]
For degree 5 the analogous test would be to rule out the irreducible quadratic times one of the (two) irreducible cubic polynomials.
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
answered Apr 11 '11 at 2:58
hardmathhardmath
28.8k95296
28.8k95296
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%2f32197%2ffind-all-irreducible-monic-polynomials-in-mathbbz-2x-with-degree-equal%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$
A polynomial of degree $2$ or $3$ must have a linear factor. To show that linear functions $x$ and $x + 1$ are not factors of $p(x)$, it suffices to show that $p(0) neq 0$ and $p(1) neq 0$. For polynomials of degree $4$ and $5$, you need to check that it has no linear factor and no factor of degree $2$. Also, in your degree $4$ and $5$ calculations, you can rule out all polynomials $q(x)$ with $q(0) = 0$ or $q(1) = 0$, so you can at least rule out a few cases.
$endgroup$
– JavaMan
Apr 11 '11 at 1:24
$begingroup$
Interesting. I was checking only for the factors, completely forgot about evaluating them at 0 and 1. That already helps quite a bit. Thought at degree 5 there are still too many polynomials to check, so my guess is there is some really clever way to check if a pol. is irreducible in this ring.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 1:30
6
$begingroup$
There are $2^5 = 32$ polynomials of degree $5$. For a polynomial $p(x)$, note that the condition $p(0) neq 0$ implies that $p(x) = x^5 + ax^4 + bx^3 + cx^2 + dx + 1$ (i.e., $p$ has nonzero constant term). The condition $p(1) neq 0 $ implies that $p(x)$ has an odd number of terms. This already eliminates 24 of the 32 cases. I cannot, however, see a more clever way, although I'm also sure that one exists.
$endgroup$
– JavaMan
Apr 11 '11 at 1:39
$begingroup$
@DJC Both your comments combined ended up being the most helpful (even thought both submited answers are good). So, if you would care to submit it as an answer, I'll accept it. Thank you.
$endgroup$
– Leonardo Fontoura
Apr 11 '11 at 18:09