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

この記事の所要時間: 140

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

\(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*}

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加

コメントをどうぞ

メールアドレスが公開されることはありません。

このサイトはスパムを低減するために Akismet を使っています。コメントデータの処理方法の詳細はこちらをご覧ください