合同式における剰余の定理

$x$ の整数係数多項式 $f(x)$ が

\begin{align*}
f(a)\equiv 0 \pmod{m}
\end{align*}

を満たす ( $a$ は整数)

$\Leftrightarrow$ 任意の $x$ に対して

\begin{align*}
f(x)\equiv (x-a)Q(x) \pmod{m}
\end{align*}

となる整数係数多項式 $Q(x)$ が存在する. $Q(x)$ の次数は $f(x)$ よりもひとつ下がっている.

等式の剰余の定理は高校でも学習する範囲に入っていますが, 合同式でも同様の定理がなあり立ちます. この定理はウィルソンの定理の証明などで使います.

証明

$f(a)\equiv 0\pmod{m}$ を前提する.

\begin{align*}
f(x) = (x-a)Q(x)+R
\end{align*}

となる整数係数多項式 $Q(x)$ と整数 $R$ が存在する. (つまり, $f(x)$ を $x-a$ で割った商が $Q(x)$ , 余りが $R$ .)

このとき $f(a)=R$ なので前提より, $R\equiv 0$ .

よって,

\begin{align*}
f(x) &= (x-a)Q(x)+R\\
&\equiv (x-a)Q(x) \pmod{m}
\end{align*}

$f(x)\equiv (x-a)Q(x)$ を前提すれば, $x=a$ を代入して

\begin{align*}
f(a)\equiv 0
\end{align*}