%% This document created by Scientific Notebook (R) Version 3.0


\documentclass[12pt,thmsa]{article}
\usepackage{amssymb}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\usepackage{makeidx}
\usepackage{sw20jart}

%TCIDATA{TCIstyle=article/art4.lat,jart,sw20jart}

%TCIDATA{<META NAME="ViewSettings" CONTENT="31">}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="Title" CONTENT="Polynomials Modulo Polynomials">}
%TCIDATA{Created=Mon Aug 19 14:52:24 1996}
%TCIDATA{LastRevised=Thu Feb 13 16:58:07 1997}
%TCIDATA{Language=American English}
%TCIDATA{CSTFile=MathHelp.cst}
%TCIDATA{<LINK REL="begin" HREF="DM12-1.tex">}
%TCIDATA{<LINK REL="contents" HREF="DM0-0.tex">}
%TCIDATA{<LINK REL="end" HREF="DM12-6.tex">}
%TCIDATA{<LINK REL="next" HREF="DM12-5.tex">}
%TCIDATA{<LINK REL="parent" HREF="DM12.tex">}
%TCIDATA{<LINK REL="previous" HREF="DM12-3.tex">}
%TCIDATA{<LINK REL="top" HREF="DM0-0.tex">}

\input{tcilatex}
\begin{document}


\section{\label{Polynomials modulo polynomials}Polynomials Modulo Polynomials
}

Two polynomials 
\index{Polynomials@Polynomials!modulo polynomials@modulo polynomials}$f(x)$
and $g(x)$ are 
\index{Congruence@Congruence!mod q(x)@mod q(x)}\textsl{congruent modulo a
polynomial} \label{Congruence, modulo polynomials}$q(x)$ if and only if $%
f(x)-g(x)$ is a multiple of $q(x)$, in which case we write 
\[
f(x)\equiv g(x)\;\left( 
\limfunc{mod}q(x)\right) 
\]
We write 
\[
g(x)\limfunc{mod}q(x)=h(x) 
\]
if $h(x)$ is a polynomial of minimal degree that is congruent to $g(x)$
modulo $q(x)$.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$x^{4}+x+1\limfunc{mod}\left( x^{2}+4x+5\right) =\allowbreak -23x-54\medskip 
$
\end{quotation}

To verify this calculation, note the following.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Polynomials + Divide}
\end{quote}

\begin{quotation}
$\dfrac{x^{4}+x+1}{x^{2}+4x+5}=\,x^{2}-4x+11+\dfrac{-23x-54}{x^{2}+4x+5}%
\medskip $
\end{quotation}

This result implies that indeed $x^{4}+x+1\limfunc{mod}\left(
x^{2}+4x+5\right) =-23x-54$.\bigskip

\subsection{\ 
\index{Polynomials@Polynomials!greatest common divisor@greatest common divisor}%
\label{gcd, polynomials}Greatest Common Divisor of Polynomials}

The \textsl{greatest common divisor of two polynomials} $p(x)$ and $q(x)$ is
a\label{Polynomials, greatest common divisor} polynomial $d(x)$ of highest
degree that divides both $p(x)$ and $q(x)$.

Define $p(x)=18x^{7}-9x^{5}+36x^{4}+4x^{3}-16x^{2}+19x+12$ and $%
q(x)=15x^{5}-9x^{4}+11x^{3}+17x^{2}-10x+8$, then use \textsf{Evaluate} to
calculate $\gcd \left( p(x),q(x)\right) .\medskip $

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\gcd \left( p(x),q(x)\right) =\allowbreak 3x^{3}+x+4\medskip $
\end{quotation}

Use the following to verify that $3x^3+x+4$ is indeed a common
divisor.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Polynomials + Divide}
\end{quote}

\begin{quotation}
$%
\dfrac{18x^{7}-9x^{5}+36x^{4}-5x^{3}-16x^{2}+16x}{3x^{3}+x+4}%
=6x^{4}-5x^{2}+4x\medskip $

$\dfrac{15x^{5}-9x^{4}+11x^{3}+17x^{2}-10x+8}{3x^{3}+x+4}=5x^{2}-3x+2%
\medskip $
\end{quotation}

Thus, 
\[
p(x)=\left( 6x^4-5x^2+4x+3\right) \left( 3x^3+x+4\right) 
\]
and 
\[
q(x)=\left( 5x^2-3x+2\right) \left( 3x^3+x+4\right) 
\]

\subsection{\ \label{Multiple roots}Multiplicity of Roots of Polynomials}

A root $a$ of a polynomial 
\index{Polynomials@Polynomials!multiple roots@multiple roots} \label%
{Polynomials, roots (2)}$f(x)$ has 
\index{Roots@Roots!multiplicity@multiplicity}\textsl{multiplicity} $k$ if $%
f(x)=(x-a)^{k}g(x)$, where $g(a)\neq 0$. If $k>1$, then $f^{\prime
}(x)=k(x-a)^{k-1}g(x)+(x-a)^{k}g^{\prime
}(x)=(x-a)^{k-1}(kg(x)+(x-a)g^{\prime }(x))$, and hence $\gcd
(f(x),f^{\prime }(x))=(x-a)^{k-1}h(x)\neq 1$. This observation provides a
test for multiple roots: If $\gcd \left( f(x),f^{\prime }(x)\right) $ is a
constant, then $f(x)$ has no 
\index{Multiple roots@Multiple roots}multiple roots; otherwise, $f(x)$ has
at least one multiple root.

The graphs of 
\[
f(x)=5537x^{5}-34804x^{4}+60229x^{3}-29267x^{2}+19888x+54692 
\]
and 
\[
g(x)=5537x^{5}-34797x^{4}+60207x^{3}-29260x^{2}+19873x+54670 
\]
appear indistinguishable. Both appear to have a root near 3.1.

\begin{center}
\FRAME{itbpFU}{2.1577in}{1.7573in}{0in}{\Qcb{$f(x)$}}{}{}{\special{language
"Scientific Word";type "MAPLEPLOT";width 2.1577in;height 1.7573in;depth
0in;display "PICT";function
\TEXUX{$5537x^{5}-34804x^{4}+60229x^{3}-29267x^{2}+19888x+54692$};linecolor
"red";linestyle 1;linethickness 1;pointstyle "point";xmin "-2";xmax
"4";xviewmin "-2.12";xviewmax "4.122";yviewmin "0";yviewmax
"100000";viewset"XY";rangeset"X";phi 45;theta 45;plottype 4;numpoints
49;axesstyle "normal";xis \TEXUX{x};var1name \TEXUX{$x$};}} \FRAME{itbpFU}{%
2.1577in}{1.7573in}{0in}{\Qcb{$g(x)$}}{}{}{\special{language "Scientific
Word";type "MAPLEPLOT";width 2.1577in;height 1.7573in;depth 0in;display
"PICT";function
\TEXUX{$5537x^{5}-34797x^{4}+60207x^{3}-29260x^{2}+19873x+54670$};linecolor
"red";linestyle 1;linethickness 1;pointstyle "point";xmin "-2";xmax
"4";xviewmin "-2.12";xviewmax "4.122";yviewmin "0";yviewmax
"100000";viewset"XY";rangeset"X";phi 45;theta 45;plottype 4;numpoints
49;axesstyle "normal";xis \TEXUX{x};var1name \TEXUX{$x$};}}
\end{center}

However,\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\gcd (f(x),f^{\prime }(x))=\,791x-2486\medskip $
\end{quotation}

whereas\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$\gcd (g(x),g^{\prime }(x))=\,7\medskip $
\end{quotation}

Thus, $x=2486/791=22/7$ is a root of $f(x)$ of multiplicity at least $2$,
whereas $g(x)$ has no multiple roots. Solving $f(x)=0$ and $g(x)=0$, the
real solutions are as follows.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Solve + Exact}
\end{quote}

\begin{quotation}
$f(x)=0$, Solution is : $\left\{ x=\frac{22}{7}\right\} ,\,\left\{ x=\frac{22%
}{7}\right\} ,$

$\,\qquad \left\{ x=-\sqrt[3]{\left( \frac{1}{2}+\frac{1}{18}\sqrt{93}%
\right) }+\dfrac{1}{3\sqrt[3]{\left( \frac{1}{2}+\frac{1}{18}\sqrt{93}%
\right) }}\right\} $

\ 

$g(x)=0$, Solution is : $\left\{ x=\frac{22}{7}\right\} ,\,\left\{ x=\frac{%
355}{113}\right\} ,$

$\qquad \,\left\{ x=-\sqrt[3]{\left( \frac{1}{2}+\frac{1}{18}\sqrt{93}%
\right) }+\dfrac{1}{3\sqrt[3]{\left( \frac{1}{2}+\frac{1}{18}\sqrt{93}%
\right) }}\right\} ,\,\medskip $
\end{quotation}

\begin{quote}
$\blacktriangleright $ \textsf{Solve + Numeric}
\end{quote}

\begin{quotation}
$f(x)=0$, Solution is : $\left\{ x=-.68233\right\} ,\,\left\{
x=3.1429\right\} ,\,\left\{ x=3.1429\right\} $

$g(x)=0$, Solution is : $\left\{ x=-.68233\right\} ,\,\left\{
x=3.1416\right\} ,\,\left\{ x=3.1429\right\} \medskip $
\end{quotation}

\ 

Thus, $g$ has two distinct roots that are extremely close, whereas $f$ has a
root of multiplicity two.

\ 

\subsection{\ \label{Irreducible polynomial}The Galois Field GF$_{p^{n}}$}

Assume that $q(x)$ is an 
\index{Polynomials@Polynomials!irreducible@irreducible}\label%
{Polynomials, irreducible}\textsl{irreducible} polynomial of degree $n$ over 
$GF_{p}$; that is, assume that $q(x)$ is of degree $n$ and, whenever $%
q(x)=a(x)b(x)$ for some $a(x)$ and $b(x)$ in $GF_{p}[x]$, then either $\deg
(a(x))=0$ or $\deg (b(x))=0$. Given two polynomials $f(x)$ and $g(x)$ in $%
GF_{p}[x]$, define the product to be the polynomial $(f(x)g(x)%
\limfunc{mod}q(x))\limfunc{mod}p$ and the sum to be the polynomial $\left(
f(x)+g(x)\right) \limfunc{mod}p$. With these definitions, the set of
polynomials in $GF_{p}[x]$ of degree less than $n$ forms a field called the 
\textsl{Galois field} $GF_{p^{n}}$.

The set of polynomials in $GF_2[x]$ of degree less than $2$ forms the field $%
GF_{2^2}=\;GF_4$. The multiplication and addition tables for $GF_2$ are
given by 
\[
\begin{tabular}{c|cc}
$\times $ & 0 & 1 \\ \hline
0 & 0 & 0 \\ 
1 & 0 & 1
\end{tabular}
\qquad \qquad 
\begin{tabular}{c|cc}
$+$ & 0 & 1 \\ \hline
0 & 0 & 1 \\ 
1 & 1 & 0
\end{tabular}
\]
The polynomial $q(x)=x^2+x+1$ is an (in fact, the only) irreducible
polynomial of degree $2$ over $GF_2$. The elements of $GF_4$ are $0$, $1$, $%
x $, and $1+x$.

To find the product $x\cdot x$ in $GF_4,$ reduce the product modulo $%
x^2+x+1, $ then reduce the result modulo $2.\medskip $

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate}
\end{quote}

\begin{quotation}
$(x^{2}\limfunc{mod}q(x))\limfunc{mod}2=x+1\medskip $
\end{quotation}

Thus, $x^2=x+1$ in $GF_4$. You can generate the entire multiplication table
efficiently using matrix and modular arithmetic.\medskip

\begin{quote}
$\blacktriangleright $ \textsf{Evaluate }(3 times)
\end{quote}

\begin{quotation}
$\left[ 
\begin{array}{c}
0 \\ 
1 \\ 
x \\ 
x+1
\end{array}
\right] \left[ 
\begin{array}{cccc}
0 & 1 & x & x+1
\end{array}
\right] =\allowbreak \left[ 
\begin{array}{cccc}
0 & 0 & 0 & 0 \\ 
0 & 1 & x & x+1 \\ 
0 & x & x^{2} & x\left( x+1\right) \\ 
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
\right] $

\ 

$\left[ 
\begin{array}{cccc}
0 & 0 & 0 & 0 \\ 
0 & 1 & x & x+1 \\ 
0 & x & x^{2} & x\left( x+1\right) \\ 
0 & x+1 & x\left( x+1\right) & \left( x+1\right) ^{2}
\end{array}
\right] \func{mod}x^{2}+x+1$

$\qquad \qquad \qquad \qquad \qquad \qquad \qquad \quad =\left[ 
\begin{array}{cccc}
0 & 0 & 0 & 0 \\ 
0 & 1 & x & x+1 \\ 
0 & x & -x-1 & -1 \\ 
0 & x+1 & -1 & x
\end{array}
\right] $

\ 

$\left[ 
\begin{array}{cccc}
0 & 0 & 0 & 0 \\ 
0 & 1 & x & x+1 \\ 
0 & x & -x-1 & -1 \\ 
0 & x+1 & -1 & x
\end{array}
\right] \func{mod}2=\allowbreak \left[ 
\begin{array}{cccc}
0 & 0 & 0 & 0 \\ 
0 & 1 & x & x+1 \\ 
0 & x & x+1 & 1 \\ 
0 & x+1 & 1 & x
\end{array}
\right] \medskip $
\end{quotation}

\ 

Sums require only reduction of polynomial sums modulo $2$. The
multiplication and addition tables are given by 
\[
\begin{tabular}{c|cccc}
$\times $ & 0 & 1 & $x$ & $x+1$ \\ \hline
0 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 1 & $x$ & $x+1$ \\ 
$x$ & 0 & $x$ & $x+1$ & 1 \\ 
$x+1$ & 0 & $x+1$ & 1 & $x$%
\end{tabular}
\]
\[
\begin{tabular}{c|cccc}
$+$ & 0 & 1 & $x$ & $x+1$ \\ \hline
0 & 0 & 1 & $x$ & $x+1$ \\ 
1 & 1 & 0 & $x+1$ & $x$ \\ 
$x$ & $x$ & $x+1$ & 0 & 1 \\ 
$x+1$ & $x+1$ & $x$ & 1 & 0
\end{tabular}
\]
Given a polynomial $f(x)=ax+b$ with $a$ and $b$ in $GF_{2}$, consider the 
\index{Binary@Binary}\label{Binary}binary representation $(ab)_{2}$. The
binary representations for the multiplication and addition tables for $%
GF_{4} $ are given by \medskip 
\[
\begin{tabular}{c|cccc}
$\times $ & 00 & 01 & 10 & 11 \\ \hline
00 & 00 & 00 & 00 & 00 \\ 
01 & 00 & 01 & 10 & 11 \\ 
10 & 00 & 10 & 11 & 01 \\ 
11 & 00 & 11 & 01 & 10
\end{tabular}
\quad \qquad 
\begin{tabular}{c|cccc}
$+$ & 00 & 11 & 10 & 11 \\ \hline
00 & 00 & 01 & 10 & 11 \\ 
01 & 01 & 00 & 11 & 10 \\ 
10 & 10 & 11 & 00 & 01 \\ 
11 & 11 & 10 & 01 & 00
\end{tabular}
\medskip 
\]
Converting from binary to decimal, we have $0=(00)_{2}$, $1=(01)_{2}$, $%
2=(10)_{2}$, and $3=\left( 11\right) _{2}$. Using this shorthand notation
for polynomials, the multiplication and addition tables become \medskip 
\[
\begin{tabular}{c|cccc}
$\times $ & 0 & 1 & 2 & 3 \\ \hline
0 & 0 & 0 & 0 & 0 \\ 
1 & 0 & 1 & 2 & 3 \\ 
2 & 0 & 2 & 3 & 1 \\ 
3 & 0 & 3 & 1 & 2
\end{tabular}
\quad \qquad 
\begin{tabular}{c|cccc}
$+$ & 0 & 1 & 2 & 3 \\ \hline
0 & 0 & 1 & 2 & 3 \\ 
1 & 1 & 0 & 3 & 2 \\ 
2 & 2 & 3 & 0 & 1 \\ 
3 & 3 & 2 & 1 & 0
\end{tabular}
\medskip 
\]

\begin{example}
\label{BCH code}This setting provides the basis for the
Bose-Chaudhuri-Hocquenghem (BCH) Codes. Given the message word $%
(a_{r},a_{r-1},...,a_{2},a_{1},a_{0})_{2}$ as a number in base 2, associate
the polynomial $a(x)=a_{r}x^{r}+a_{r-1}x^{r-1}+\cdot \cdot \cdot
+a_{2}x^{2}+a_{1}x+a_{0}$ in $GF_{2}[x]$. A codeword 
\index{Code word@Code word}is then generated by the formula $a(x)q(x)%
\limfunc{mod}2$, where $q(x)$ is a specially selected polynomial.

Consider the Galois field $GF_{2^{4}}=GF_{16}$. Let $\alpha $ be a primitive
element in $GF_{16}$, so that the nonzero elements of $GF_{16}$ are all
powers of $\alpha $. In particular, this property holds if we take $\alpha $
to be a root of the irreducible polynomial $x^{4}+x+1$. Let $m_{i}(x)$ be
the minimal polynomial of $\alpha ^{i}$. If $q(x)=\limfunc{lcm}[%
m_{1}(x),m_{2}(x),...,m_{2t}(x)]$, then the corresponding 
\index{BCH code@BCH code}BCH code corrects at least $t$ errors.

Since $\alpha ^{4}+\alpha +1=0$, it follows that $0^{2}=\left( \alpha
^{4}+\alpha +1\right) ^{2}=$ $\left( \alpha ^{4}\right) ^{2}+\alpha
^{2}+1=\left( \alpha ^{2}\right) ^{4}+\alpha ^{2}+1$; hence, $%
m_{1}(x)=m_{2}(x)$. By the same reasoning, $m_{2}(x)=m_{4}(x)=m_{8}(x)$.
Likewise, $m_{3}(x)=(x-\alpha ^{3})(x-\alpha ^{6})(x-\alpha ^{12})(x-\alpha
^{9})=x^{4}+x^{3}+x^{2}+x+1$; hence, a double error-correcting code is
generated by 
\[
q(x)=%
\limfunc{lcm}[m_{1}(x),m_{2}(x),m_{3}(x),m_{4}(x)]\limfunc{mod}%
2=x^{8}+x^{7}+x^{6}+x^{4}+1 
\]
\bigskip
\end{example}

\subsection{\ Related topics}

\hyperref{Solving Equations}{}{}{DM12-1.tex#Integer solutions}

\hyperref{Integers Modulo m}{}{}{DM12-2.tex#Integers modulo m}

\hyperref{Other Systems Modulo m}{}{}{DM12-3.tex#Matrices modulo m}

\hyperref{Linear Programming}{}{}{DM12-5.tex#Linear programming}

\hyperref{Exercises and Solutions}{}{}{DM12-6.tex#Exercises}

\rule{0.67in}{0.01in}

\hyperref{\FRAME{itbpF}{0.5275in}{0.3399in}{0.0519in}{}{}{index.wmf}{\special%
{language "Scientific Word";type "GRAPHIC";display "PICT";valid-file
"F";width 0.5275in;height 0.3399in;depth 0.0519in;original-width
36.875pt;original-height 22.5625pt;cropleft "0";croptop "1";cropright
"1";cropbottom "0";filename 'index.wmf';file-properties "XNPEU";}}}{}{}{%
DMIndex.tex#Math Index}\quad {\small Index entries: \hyperref{Applied modern
algebra}{}{}{DMIndex.tex#Applied modern algebra}, \hyperref{Congruence}{}{}{%
DMIndex.tex#Congruence}, \hyperref{Polynomials}{}{}{DMIndex.tex#Polynomials}%
, \hyperref{Solve}{}{}{DMIndex.tex#Solve}}

\end{document}
