Find all irreducible polynomials of degree 3 in Z(3)[x].
Daniel C. Bastos
Solution. We can express all polynomials of degree 3 over Z(3) by
ax^3 + bx^2 + cx + d.
We now describe the possible choices for the coefficients in order to
make them irreducible over Z(3). If d = 0, then x factors the
polynomial. So, there are only two options for d; that is, d is in {1,
2}. Since the degree must be 3, then a cannot be 0, so a is in {1, 2}.
No matter what elements of Z(3) we choose for b or c, we will never
obtain zero because the result is always positive since we're adding
d, so no restrictions apply for b or c; that is, b is in {0, 1, 2} and
c is in {0, 1, 2}.
Remark. There are 2 * 3 * 3 * 2 = 36 polynomials with the choices for
a, b, c and d as described.
William Elliot
> Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
> Solution. We can express all polynomials of degree 3 over Z(3) by
>
> ax^3 + bx^2 + cx + d.
>
If that polynomial p is of degree three and irreduciable over Z_3, then
a /= 0, d /= 0. Additionally for Z_3, x = -x, thus we can reduce p to
x^3 + bx^2 + cx + d, d /= 0
This gives 3 * 3 * 2 = 18 polynomials p to look at.
If p is reduciable, then p(1) = 0 or p(-1) = 0
1 + b + c + d = 0
or
1 + b - c + d = 0
Thus b = c = d = 1 is irreduciable.
and b = c = d = -1, is reducible.
By similar methods or directly x^3 - 1 and x^3 + 1 are reduciable.
Thus one of b and c isn't zero.
> We now describe the possible choices for the coefficients in order to
> make them irreducible over Z(3). If d = 0, then x factors the
> polynomial. So, there are only two options for d; that is, d is in {1,
> 2}. Since the degree must be 3, then a cannot be 0, so a is in {1, 2}.
>
> No matter what elements of Z(3) we choose for b or c, we will never
> obtain zero because the result is always positive since we're adding
> d, so no restrictions apply for b or c; that is, b is in {0, 1, 2} and
> c is in {0, 1, 2}.
>
You are forgetting 1 + 1 + 1 = 0 (mod 3)
That in Z_n, positive means nothing, there is no way of
comparing 0 with 1 as 1 = 1 - n (mod n). Thus lo!
1 = 1 - n < 0 < 1
> Remark. There are 2 * 3 * 3 * 2 = 36 polynomials with the choices for
> a, b, c and d as described.
>
But they aren't all irreducible.
Daniel C. Bastos
William Elliot wrote:
> On Tue, 28 Mar 2006, Daniel C. Bastos wrote:
>
> > Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
> > Solution. We can express all polynomials of degree 3 over Z(3) by
> >
> > ax^3 + bx^2 + cx + d.
> >
> If that polynomial p is of degree three and irreduciable over Z_3, then
> a /= 0, d /= 0. Additionally for Z_3, x = -x, thus we can reduce p to
> x^3 + bx^2 + cx + d, d /= 0
Are you saying that a = 1? How did you go from a /= 0 to a = 1?
> This gives 3 * 3 * 2 = 18 polynomials p to look at.
> If p is reduciable, then p(1) = 0 or p(-1) = 0
I'm confused. I wasn't considering -1 as a member of Z_3. I thought I
could just consider Z_3 = {0, 1, 2}. Can you explain your strategy in
more details?
William Elliot
> William Elliot wrote:
>
> > On Tue, 28 Mar 2006, Daniel C. Bastos wrote:
> >
> > > Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
> > > Solution. We can express all polynomials of degree 3 over Z(3) by
> > >
> > > ax^3 + bx^2 + cx + d.
> > >
> > If that polynomial p is of degree three and irreduciable over Z_3, then
> > a /= 0, d /= 0. Additionally for Z_3, x = -x, thus we can reduce p to
Whoops, 2 = -1 (mod 3). [x = -x (mod 2)]
> > x^3 + bx^2 + cx + d, d /= 0
>
> Are you saying that a = 1? How did you go from a /= 0 to a = 1?
>
> > This gives 3 * 3 * 2 = 18 polynomials p to look at.
> > If p is reduciable, then p(1) = 0 or p(-1) = 0
>
> I'm confused. I wasn't considering -1 as a member of Z_3. I thought I
> could just consider Z_3 = {0, 1, 2}. Can you explain your strategy in
> more details?
>
Wake up, [2]_3 = [-1]_3 or more explictely using cofactors
2 + (3) = -1 + (3)
or simply -1 = 2 (mod 3), so there is -1 in Z_3.
After all Z_3 is a field as is Z_p for prime p.
Thus for nonzero n in Z_p, -n and 1/n are in Z_p
For example, 2 * 4 = 1 (mod 7), thus 1/2 = 4 (mod 7)
and 2 + 5 = 0 (mod 7), thus -2 = 5 (mod 7)
{ 1,2,3 } is one representative set for Z_3. Others are { -1,0,1 } and
{ 0,1,2 }, even { 6,10,14 }. One can choose the one most to one's liking.
If p(x) is reducible iff -p(x) is reducible and 2 = -1 (mod 3)
2x^3 + ... is reducible iff -x^3 + ... is reducible
iff x^3 - ... is reduciable.
Paul Sperry
<dba...@yahoo.com.br> wrote:
> Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
>
> Solution. We can express all polynomials of degree 3 over Z(3) by
>
> ax^3 + bx^2 + cx + d.
>
> We now describe the possible choices for the coefficients in order to
> make them irreducible over Z(3). If d = 0, then x factors the
> polynomial. So, there are only two options for d; that is, d is in {1,
> 2}. Since the degree must be 3, then a cannot be 0, so a is in {1, 2}.
So far so good.
> No matter what elements of Z(3) we choose for b or c, we will never
> obtain zero because the result is always positive since we're adding
> d, so no restrictions apply for b or c; that is, b is in {0, 1, 2} and
> c is in {0, 1, 2}.
Z_3 has no "positive". [1] is a root of x^3 + x + [1] -- here
[1] = 1 + 3Z.
x^3 + x + [1] = (x + [2])(x^2 + x + [2])
[...]
--
Paul Sperry
Columbia, SC (USA)
Daniel C. Bastos
Paul Sperry wrote:
> In article <20060328033843.000021ad@Saturn>, Daniel C. Bastos
> <dba...@yahoo.com.br> wrote:
>
> > Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
[...]
From scratch.
Solution. We can express all polynomials of degree 3 over Z_3 by ax^3
+ bx^2 + cx + d. We now describe the possible choices for the
coefficients in order to make them irreducible over Z_3.
The constant term d cannot be zero, or zero is a root. The
coefficients cannot sum to zero, or one is a root. Now, to derive a
third rule, evaluate x = 2 = -1: -a + b + -c + d = 0 implies
b + d = a + c.
That is, whenever the sum of the even coefficients equals the sum of
odd coefficients, we have 2 = -1 as a root. Since the degree must be
3, then a cannot be 0, so a is either 1 or 2.
Since factorization is unique except for scalar multiple (and order),
consider all monic polynomials and multiply each by 2 to notice that
factorization doesn't change. So we may consider only the monic
polynomials; in case we want to distinguish them, we may multiply each
irreducible by 2 to obtain its match, doubling the total of
irreducible polynomials.
Now, we have 2 choices for d, 3 choices for c, 3 choices for b, with 1
choice for a. This gives us 18 polynomials p(x). Suppose now that p(x)
is reducible; then its factors will be of degree 2 and degree 1; that
is, p(x) = g(x)h(x) = (x^2 + Ax + B)(x + C). Since 2d isn't zero, B
and C are not zero. So, C = 1 or C = 2, B = 1 or B = 2. This gives us
6 possibilities for g(x) and 2 possibilities for h(x); that is, 12
factorizations, which we list below in the order x^3, x^2, x^1, x^0.
1 0 0 1
1 0 0 2
1 0 1 1
1 0 1 2
1 0 2 1 irreducible
1 0 2 2 irreducible
1 1 0 1
1 1 0 2 irreducible
1 1 1 1
1 1 1 2 irreducible
1 1 2 1 irreducible
1 1 2 2
1 2 0 1 irreducible
1 2 0 2
1 2 1 1 irreducible
1 2 1 2
1 2 2 1
1 2 2 2 irreducible
We found 8 polynomials. If we multiply each by 2, we would get their
matches, yielding 16 irreducible polynomials, with the next 8 as shown
below.
2 0 0 1
2 0 0 2
2 0 1 1 irreducible
2 0 1 2 irreducible
2 0 2 1
2 0 2 2
2 1 0 1
2 1 0 2 irreducible
2 1 1 1 irreducible
2 1 1 2
2 1 2 1
2 1 2 2 irreducible
2 2 0 1 irreducible
2 2 0 2
2 2 1 1
2 2 1 2 irreducible
2 2 2 1 irreducible
2 2 2 2
Daniel C. Bastos
Daniel C. Bastos wrote:
Sorry. This ending of this paragraph is not making much sense. I meant
to say that I will list all of the 18 polynomials by expressing their
coefficients only in the order x^3, x^2, x^1, x^0; and I will be taking
advantage of the listing to add the irreducible ones; since there are 12
factorizations, where 2 repeate, I expect 8 irreducibles and 10
reducibles.
[...]
Paul Sperry
<dba...@yahoo.com.br> wrote:
Good. I agree with your results. This is a good example of the "brute
force" I referred to in another thread.
It seems to me that your explanation just before you list the results
misses the point. Since the polynomials have degree three and Z_3 has
no zero divisors, they will be reducible iff they have a linear factor.
Note that the linear factor need not be monic:
(2x^2 +...)(2x + ..) = x^3+ ...
It is crucial that if 2x + A is a factor then so is x + 2A and thus
there is a root.
That is, the polynomial reducible iff there is a root in Z_3 - it is
important that Z_3 is a field. It might be better to put this remark
before your characterization of which polynomials have roots (so the
reader knows why you _care_ about roots).
I think that if you were to try this with Z_4 instead of Z_3, you would
run into some problems.
William Elliot
Newsgroups: alt.algebra.help
Subject: Re: Find all irreducible polynomials of degree 3 in Z(3)[x].
> Exercise. Find all irreducible polynomials of degree 3 in Z(3)[x].
> Solution. We can express all polynomials of degree 3 over Z_3 by
> ax^3 + bx^2 + cx + d. We now describe the possible choices for the
> coefficients in order to make them irreducible over Z_3.
> The constant term d cannot be zero, or zero is a root. The
> coefficients cannot sum to zero, or one is a root. Now, to derive a
> third rule, evaluate x = 2 = -1: -a + b + -c + d = 0 implies
> b + d = a + c.
First off we notice that f in Z_3[x] is reduciable iff f has a root.
This is because f is degree 3 and if f factors, it has to factor
into a degree 2 and a degree 1 polynomial.
Thus f(x) = ax^3 + bx^2 + cx + d is reduciable iff
f(0) = 0 or f(1) = 0 or f(-1) = 0, ie iff
f(0) f(1) f(-1) = 0 which is equivalent to
d(a + b + c + d)(-a + b - c + d) = 0
d(a + c + b + d)(-a - c + b + d) = 0
d((b + d)^2 - (a + c)^2) = 0
d = 0 or (b + d)^2 = (a + c)^2
d = 0 or b + d = 0 = a + c or b + d /= 0 /= a + c
(because when x /= 0 (mod 3), x^2 = 1)
d = 0 or b + d = 0 = a + c or (b + d)(a + c) /= 0
Consequently f is irreducible iff
d /= 0, (b + d /= 0 or a + c /= 0) and (b + d)(a + c) = 0
(d /= 0, b + d /= 0, a + c = 0) or (d /= 0, b + d = 0, a + c /= 0)
1 0 0 1 f(-1) = 0
1 0 0 2 f(1) = 0
1 0 1 1 f(1) = 0
1 0 1 2 f(-1) = 0
1 0 2 1 irreducible f(0) = 1, f(1) = 1, f(-1) = -1
1 0 2 2 irreducible f(0) = -1, f(1) = -1, f(-1) = -1
----
Daniel C. Bastos
Paul Sperry wrote:
Hmm, I certainly missed; this still isn't clear to me. Is it because 3
is prime that Z_3 has no zero divisors? I tried to convince myself
with: let q be composite. So in Z_q, there is a prime p which divides
q, so that makes pq = 0 in Z_q. If q is prime, there wouldn't be such
p, so there wouldn't be zero divisors.
If a polynomial is reducible, then its factors will have degree 2 and
1. Why? Can't we have something like (x^4 + 1)(x^9 + 2) in Z_3?
Another one that I don't seem to see why is p(x) in Z_3 reducible iff
p(x) has a root in Z_3. Why is this true in Z_3, but not true in Q,
for example?
> Note that the linear factor need not be monic:
> (2x^2 +...)(2x + ..) = x^3+ ...
> It is crucial that if 2x + A is a factor then so is x + 2A and thus
> there is a root.
>
> That is, the polynomial reducible iff there is a root in Z_3 - it is
> important that Z_3 is a field. It might be better to put this remark
> before your characterization of which polynomials have roots (so the
> reader knows why you _care_ about roots).
I agree. I will be trying to prove the theorem: In Z_3, p(x) is
reducible if and only if there is r in Z_3 such that p(r) = 0.
> I think that if you were to try this with Z_4 instead of Z_3, you would
> run into some problems.
Because not always I would have a linear factor?
William Elliot
> Paul Sperry wrote:
> > <dba...@yahoo.com.br> wrote:
> Hmm, I certainly missed; this still isn't clear to me. Is it because 3
> is prime that Z_3 has no zero divisors? I tried to convince myself
> with: let q be composite. So in Z_q, there is a prime p which divides
> q, so that makes pq = 0 in Z_q. If q is prime, there wouldn't be such
> p, so there wouldn't be zero divisors.
>
zero divisors. However when n is prime Z_n not only is it an integral
domain (a commutative ring with identity and no zero divisors), it's also
a field. That is for every non-zero k in Z_n, there's a j in Z_n with
kj = 1 (mod n).
For example, 1 * 1 = 2 * 4 = 3 * 5 = 6 * 6 = 1 (mod 7).
Thus some may write 1/2 = 4 and 1/4 = 2 (mod 7).
By showing Z_n for prime n is a field, it's immediate that Z_n is an
integral domain. In fact, 'tis theorem, every field is an integral
domain.
> If a polynomial is reducible, then its factors will have degree 2 and
> 1. Why? Can't we have something like (x^4 + 1)(x^9 + 2) in Z_3?
>
That is so only of a polynomial of degree three.
Yes, your example is correct.
> Another one that I don't seem to see why is p(x) in Z_3 reducible iff
> p(x) has a root in Z_3. Why is this true in Z_3, but not true in Q,
> for example?
>
It's true of any polynomial in F[x] for any field F such as Q or Z_3.
That if p in F[x] has root r, then (x - r) | p(x). This follows from
the Euclidean division algorithm for F[x]
> I agree. I will be trying to prove the theorem: In Z_3, p(x) is
> reducible if and only if there is r in Z_3 such that p(r) = 0.
> > I think that if you were to try this with Z_4 instead of Z_3, you would
> > run into some problems.
>
> Because not always I would have a linear factor?
>
Z_4 isn't a field. If p in Z_3[x] is of forth degree, then p can be
reducible without any linear factors, as for example, (x^2 + 1)^2
is reducible in Z_3[x] without any roots or linear factors.
Paul Sperry
[[ The problem was to find all irreducible elements of Z_3[x] of degree
three. That was successfully done by exhaustively checking for roots:
no root = irreducible. The question now is why did that work.]]
Let's look at Z_4[x] for a minute.
(2x^2 + 1)(2x^3 + x) = x; the degrees didn't add.
(2x + 1)(2x + 3) has two different linear factors but no roots.
I would not care to try the problem for Z_4[x]. Maybe there is a slick
way to do it but if so, I don't see it.
Now, for Z_3[x] on the other hand,
deg(f(x)g(x)) = deg(f(x)) + deg(g(x)) because the leading coefficient
of f(x)g(x) is the product of the leading coefficients of f(x) and
g(x). Also, if ax + b is a linear factor of f(x) then 1/a exists and
-b/a is a root.
So, if deg(f(x)) = 3 and f(x) is reducible,the degrees of the factors
must add to 3 so at least one factor has degree 1 (not true in Z_4[x])
and a factor of degree 1 gives a root of f(x) (also not true in
Z_4[x]). Conversely if f(x) has a root then f(x) is reducible (that
_is_ true for Z_4[x]). So, all you needed to do was find all the
polynomials of degree 3 which have no root; which is what you did.
Daniel C. Bastos
Paul Sperry wrote:
> [[ The problem was to find all irreducible elements of Z_3[x] of degree
> three. That was successfully done by exhaustively checking for roots:
> no root = irreducible. The question now is why did that work.]]
Right.
> Let's look at Z_4[x] for a minute.
>
> (2x^2 + 1)(2x^3 + x) = x; the degrees didn't add.
>
> (2x + 1)(2x + 3) has two different linear factors but no roots.
>
> I would not care to try the problem for Z_4[x]. Maybe there is a slick
> way to do it but if so, I don't see it.
The problem here happens because Z_4 is not a field? We need it to be a
field because we need to divide; is that right? I guess so. I tried
answering it below.
> Now, for Z_3[x] on the other hand,
> deg(f(x)g(x)) = deg(f(x)) + deg(g(x)) because the leading coefficient
> of f(x)g(x) is the product of the leading coefficients of f(x) and
> g(x). Also, if ax + b is a linear factor of f(x) then 1/a exists and
> -b/a is a root.
>
> So, if deg(f(x)) = 3 and f(x) is reducible,the degrees of the factors
> must add to 3 so at least one factor has degree 1 (not true in Z_4[x])
> and a factor of degree 1 gives a root of f(x) (also not true in
> Z_4[x]). Conversely if f(x) has a root then f(x) is reducible (that
> _is_ true for Z_4[x]). So, all you needed to do was find all the
> polynomials of degree 3 which have no root; which is what you did.
Let's see. If the degree of p(x) is 3 and p(x) is over a field Z_p,
then we will have roots if and only if the polynomial is reducible in
Z_p[x]. Correct? The same would happen for deg(p(x)) = 2. I will
explain that in the solution.
But if Z_n is not a field, then p(x) may be ruducible to linear
factors, but still, not necessarily it will have a root. That is, if
p(x) is reducible to linear factors, then it's because
p(x) = c(x - r(1))(x - r(2)) ... (x - r(n)),
where r(i) is a root for i = 1, 2, ... n and c is an element of
Z_n. Now, if p(x) has any roots, then it's because c(x - r(i)) = 0,
and this yields x = r(i)/c. So, if Z_n is not a field, r(i)/c may not
be in Z_n.
That is, to be sure we get roots, we must have a multiplicative
inverse for each nonzero element; so we need a field.
Paul Sperry
<dba...@yahoo.com.br> wrote:
> In article <300320062257129784%plsp...@sc.rr.com>,
> Paul Sperry wrote:
>
> > [[ The problem was to find all irreducible elements of Z_3[x] of degree
> > three. That was successfully done by exhaustively checking for roots:
> > no root = irreducible. The question now is why did that work.]]
>
> Right.
>
> > Let's look at Z_4[x] for a minute.
> >
> > (2x^2 + 1)(2x^3 + x) = x; the degrees didn't add.
> >
> > (2x + 1)(2x + 3) has two different linear factors but no roots.
> >
> > I would not care to try the problem for Z_4[x]. Maybe there is a slick
> > way to do it but if so, I don't see it.
Now that I think about it, finding the irreducibles (of any degree) in
Z_4[x] is pretty easy - there aren't any.
Things are worse than that. Take another look at the two Z_4[x]
examples.
The presence of zero divisors messes things up more than the lack of
inverses. If there were no zero divisors in Z_4 then I could, if I were
industrious enough, find all reducible degree 3 polynomials of Z_4[x]
by finding all products of degree 2 polynomials with linear
polynomials. However, that won't work. See the example that gives a
factorization of x.
Also note that a polynomial in Z_4[x] may factor into a product of
linear factors but not into a product of monic linear factors.
Daniel C. Bastos
Paul Sperry wrote:
> In article <20060405121741.00006f01@Saturn>, Daniel C. Bastos
> <dba...@yahoo.com.br> wrote:
>
> > In article <300320062257129784%plsp...@sc.rr.com>,
> > Paul Sperry wrote:
> >
> > > [[ The problem was to find all irreducible elements of Z_3[x] of degree
> > > three. That was successfully done by exhaustively checking for roots:
> > > no root = irreducible. The question now is why did that work.]]
> >
> > Right.
> >
> > > Let's look at Z_4[x] for a minute.
> > >
> > > (2x^2 + 1)(2x^3 + x) = x; the degrees didn't add.
> > >
> > > (2x + 1)(2x + 3) has two different linear factors but no roots.
> > >
> > > I would not care to try the problem for Z_4[x]. Maybe there is a slick
> > > way to do it but if so, I don't see it.
>
> Now that I think about it, finding the irreducibles (of any degree) in
> Z_4[x] is pretty easy - there aren't any.
Trying to see why; I tried an explanation below.
[...]
Your example factors x. But x was supposed to be irreducible, no? It
has roots, 0 is one, but isn't it supposed to be irreducible? So,
maybe the explanation is that all linear polynomials are reducible, so
no polynomial of any degree will be irreducible because they are all
factorized by the linear ones. The factorization of linear polynomials
are only possible with zero divisors.
But factors are supposed to be of lesser degree, right? The way we
``factor'' x is by using x^2 and x^3. Is that a valid factor?
Paul Sperry
<dba...@yahoo.com.br> wrote:
> In article <050420062248391356%plsp...@sc.rr.com>,
> Paul Sperry wrote:
>
> > In article <20060405121741.00006f01@Saturn>, Daniel C. Bastos
> > <dba...@yahoo.com.br> wrote:
> >
> > > In article <300320062257129784%plsp...@sc.rr.com>,
> > > Paul Sperry wrote:
> > >
> > > > [[ The problem was to find all irreducible elements of Z_3[x] of degree
> > > > three. That was successfully done by exhaustively checking for roots:
> > > > no root = irreducible. The question now is why did that work.]]
> > >
> > > Right.
> > >
> > > > Let's look at Z_4[x] for a minute.
> > > >
> > > > (2x^2 + 1)(2x^3 + x) = x; the degrees didn't add.
> > > >
> > > > (2x + 1)(2x + 3) has two different linear factors but no roots.
> > > >
> > > > I would not care to try the problem for Z_4[x]. Maybe there is a slick
> > > > way to do it but if so, I don't see it.
> >
> > Now that I think about it, finding the irreducibles (of any degree) in
> > Z_4[x] is pretty easy - there aren't any.
>
> Trying to see why; I tried an explanation below.
[...]
> Your example factors x. But x was supposed to be irreducible, no? It
> has roots, 0 is one, but isn't it supposed to be irreducible? So,
> maybe the explanation is that all linear polynomials are reducible, so
> no polynomial of any degree will be irreducible because they are all
> factorized by the linear ones. The factorization of linear polynomials
> are only possible with zero divisors.
>
> But factors are supposed to be of lesser degree, right?
Not necessarily; zero divisors screw things up.
> The way we
> ``factor'' x is by using x^2 and x^3. Is that a valid factor?
[...]
Here is what I had in mind for Z_4[x]. Given any p(x) in Z_4[x] factor
2x^2 + 1 out of one x for every non-constant term. For the constant
term note (2x^2 + 1)^2 = 1 so 2x^2 + 1 factors out of p(x);
(2x^2 + 1)^2 = 1 should have set off alarm bells but did not.
All of that is correct but it does not show p(x) is reducible. The
problem is that x^2 + 1 has an inverse and thus doesn't count as a
proper factor.
All is not lost however. Let's switch our attention to Z_6[x]. In
Z_6[x], x = (2x + 3)(3x + 2) and neither 2x + 3 nor 3x + 2 is
invertible (because neither 2 nor 3 is invertible). An argument similar
to the one for Z_4[x] shows that any element of Z_6[x] with constant
term equal to zero is reducible. I don't know about the others.
Anyway, my point was that if there were zero divisors and
non-invertible elements, most of the familiar polynomial properties are
no longer true.