この記事の所要時間： 約 1分40秒
合同式における剰余の定理
\(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)\) よりもひとつ下がっている.
等式の剰余の定理は高校でも学習する範囲に入っていますが, 合同式でも同様の定理がなあり立ちます. この定理はウィルソンの定理の証明などで使います.
合同式についてはこちら.
証明
\((\Rightarrow)\)
\(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*}
\((\Leftarrow)\)
\(f(x)\equiv (x-a)Q(x)\) を前提すれば, \(x=a\) を代入して
\begin{align*}
f(a)\equiv 0
\end{align*}
