Polynomials Modulo Polynomials

Two polynomials f (x) and g(x) are congruent modulo a polynomial q(x) if and only if f (x) - g(x) is a multiple of q(x), in which case we write

f (x)≡g(x)  $\displaystyle \left(\vphantom{
\limfunc{mod}q(x)}\right.$$\displaystyle \limfunc$modq(x)$\displaystyle \left.\vphantom{
\limfunc{mod}q(x)}\right)$

We write

g(x)$\displaystyle \limfunc$modq(x) = h(x)

if h(x) is a polynomial of minimal degree that is congruent to g(x) modulo q(x).


$\blacktriangleright$ Evaluate

x4 + x + 1$\limfunc$mod$\left(\vphantom{ x^{2}+4x+5}\right.$x2 + 4x + 5$\left.\vphantom{ x^{2}+4x+5}\right)$ = -23x - 54


To verify this calculation, note the following.


$\blacktriangleright$ Polynomials + Divide

${\dfrac{{x^{4}+x+1}}{{x^{2}+4x+5}}}$ =  x2 -4x + 11 + ${\dfrac{{-23x-54}}{{x^{2}+4x+5}%
}}$


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




Subsections