Exercise 4.2.7

Question

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

For each of the following polynomials, determine, without using a computer, whether it is irreducible over the given field.
\begin{enumerate}
\item[(a)] $x^3+x+1$ over $\F_5$.
\item[(b)] $x^4+x+1$ over $\F_2$.
\end{enumerate}

Richard Ganaye · Accepted Answer

\def\imp{\Rightarrow}
\def\gcro{\mbox{[\hspace{-.15em}[}}% intervalles d'entiers 
\def\dcro{\mbox{]\hspace{-.15em}]}}

ewcommand{\be} {\begin{enumerate}}

ewcommand{\ee} {\end{enumerate}}

ewcommand{\deb}{\begin{eqnarray*}}

ewcommand{\fin}{\end{eqnarray*}}

ewcommand{\ssi} {si et seulement si }

ewcommand{\D}{\mathrm{d}}

ewcommand{\Q}{\mathbb{Q}}

ewcommand{\Z}{\mathbb{Z}}

ewcommand{\N}{\mathbb{N}}

ewcommand{\R}{\mathbb{R}}

ewcommand{\C}{\mathbb{C}}

ewcommand{\F}{\mathbb{F}}

ewcommand{\U}{\mathbb{U}}

ewcommand{e}{\,\mathrm{Re}\,}

ewcommand{\im}{\,\mathrm{Im}\,}

ewcommand{\ord}{\mathrm{ord}}

ewcommand{\Gal}{\mathrm{Gal}}

ewcommand{\legendre}[2]{\genfrac{(}{)}{}{}{#1}{#2}}

\begin{proof}

\begin{enumerate}
\item[(a)]
$f= x^3+x+1$ being of degree 3, it is reducible iff it has a linear factor (see Ex. 6), iff  it has a root in $\mathbb{F}_5$, which request 5 verifications:

$f(0)=1, f(1)=3, f(2)=1, f(-2) = 1, f(-1) = -1$, all nonzero, so $f$ is irreducible over $\F_5$.

\item[(b)]
$f = x^4+x+1$ has no root in  $\F_2$.

It is so sufficient to test the divisibility of $f$ by quadratic polynomials, which are

$$x^2,x^2+1, x^2+x, x^2+x+1.$$

$x^2$ and $x^2+x$ are not irreducible, can be excluded of the list. It remains to test two divisions by

$$x^2+1,x^2+x+1$$.

\begin{align*}
x^4+x+1 &= (x^2+1)(x^2+1)+x\
&=(x^2+x+1)(x^2+x)+1
\end{align*}
The remainders of these divisions being nonzero, $x^4+x+1$ is so irreducible over $\mathbb{F}_2$.

Note: the factorization of $\Phi_{15}$ over the field $\mathbb{F}_2$, gives the list of irreducible polynomials over $\mathbb{F}_2$ of degree 4.
\begin{verbatim}
S.<t> = GF(2)['t']
phi15 =( (x^15-1)*(x-1)*(x-1))/((x-1)*(x^3-1)*(x^5-1)); phi15
	x^8 + x^7 + x^5 + x^4 + x^3 + x + 1
factor(phi15)
	(x^4 + x + 1) * (x^4 + x^3 + 1)
\end{verbatim}
\end{enumerate}
\end{proof}

Exercise 4.2.7

Answers

Comments

Exercise 4.2.7

Answers

Comments

Add answer