1. 概要

本記事では，$\mathbb{F}_p$ 係数の多項式に関する重要事項について解説します．

議論の大部分は，多項式について中学・高校の数学で学んだ内容の再確認になると思います．ただし，中学・高校の数学では，多項式の係数として主に実数（や複素数）を想定して学習していると思うので，同じようにできることを確認しながら理解してください．

本記事の内容は，競技プログラミングの問題にそのままの形で直接適用するという機会はあまり多くないと思いますが，多くの応用がある重要な内容です．AtCoder Algorithm Lectures 内でも，今後の複数の講座の前提となります．

2. 前提知識

AtCoder Algorithm Lectures における次の講座の内容を前提とします．

素数の性質

3. $\mathbb{F} _ p$ 係数の多項式

本節では，$p$ を法とする合同式ではなく，体 $\mathbb{F} _ p$ を扱うこととします．（合同式の範囲だけで議論を完結させたい場合には，「多項式としての一致」を，「すべての係数の $\operatorname{mod} p$ での一致」に読み替えることなどによりおおよそ同じように議論できますが，ところどころ記述が複雑になります．）

$\mathbb{F} _ p$ 係数の多項式とは，多項式

$$f(x) = f _ nx ^ n+f _ {n - 1}x ^ {n - 1} + \cdots + f _ 1x+f _ 0$$

であって，$f_i\in \mathbb{F} _ p$ であるもののことです．$a\in \mathbb{F} _ p$ に対して，代入 $f(a)\in \mathbb{F} _ p$ が定義されます．

$\mathbb{F} _ p$ 係数の多項式全体を $\mathbb{F} _ p[x]$ と書きます．$\mathbb{F} _ p[x]$ には加算・減算・乗算が定義されています．（代数学の用語では，$\mathbb{F} _ p[x]$ は環です．この環を $\mathbb{F} _ p$ 係数の多項式環といいます．）

本節の内容を理解する上では中学数学レベルの多項式の定義を理解していれば十分だと思いますが，より正確な定義を確認したい場合には文献 2 を参考にしてください．

なお 3.1 節，3.2 節の議論は任意の体を係数とする多項式について全く同じように行えるものです．高校の数学では実数や複素数を係数とする多項式についておおよそ同じことを学ぶと思います．証明についてもよく知られていると思われるものと同じものについては省略しています．

3.1. 剰余定理・因数定理

【定義 1】（多項式の除法）

$f(x), g(x)\in \mathbb{F} _ p[x]$ について $g(x)\neq 0$ であるとき，次の $2$ 条件を満たす $q(x),r(x)\in \mathbb{F} _ p[x]$ が一意に存在する．

$f(x)=g(x)q(x)+r(x)$
$r(x)$ の次数は $g(x)$ の次数よりも小さい．

$q(x)$ を $f(x)$ を $g(x)$ で割ったときの商（quotient），$r(x)$ を余り（remainder）という．

商，余りが一意に存在することの証明は省略します．

【定理 2】（剰余定理）

$f(x)\in \mathbb{F} _ p[x]$ と $a\in \mathbb{F} _ p$ について，$f(x)$ を $x-a$ で割ったときの余りは代入 $f(a)$ に等しい．

商を $q(x)$，余りを $r(x)$ とすると，$f(x) = (x-a)q(x) + r(x)$ が成り立つので，この式の両辺に $x=a$ を代入すると $r(a)=f(a)$ が分かります．$r(x)$ の次数は $0$ 次以下なので，$r(x)=f(a)$ となります． $\blacksquare$

【定理 3】（因数定理）

$f(x)\in \mathbb{F} _ p[x]$ と $a\in \mathbb{F} _ p$ について，$f(a)=0$ であるとき，$f(x)=(x-a)g(x)$ を満たす $g(x)\in \mathbb{F} _ p[x]$ が存在する．

【定理 2】より明らかです． $\blacksquare$

因数定理を次のように一般化しておくと便利です．

【定理 4】

$f(x)\in \mathbb{F} _ p[x]$ と，$\mathbb{F} _ p$ の相異なる要素 $a_1,a_2,\ldots,a_n$ が $$f(a_1)=f(a_2)=\cdots=f(a_n)=0$$ を満たすとき， $$f(x)=(x-a_1)(x-a_2)\cdots(x-a_n)g(x)$$ を満たす $g(x)\in \mathbb{F} _ p[x]$ が存在する．

$n$ についての帰納法により証明します．$n=1$ のときは因数定理より成り立ちます．

$n$ の場合に成り立つとして，$n+1$ の場合に示します．$\mathbb{F} _ p$ の相異なる要素 $a_1,a_2,\ldots,a_n,a_{n+1}$ が

$$f(a_1)=f(a_2)=\cdots=f(a_n)=f(a_{n+1})=0$$

を満たすとします．まず帰納法の仮定より

$$f(x)=(x-a_1)(x-a_2)\cdots(x-a_n)g(x)$$

を満たす $g(x)\in \mathbb{F} _ p[x]$ が存在します．

$$0 = (a _ {n + 1} - a _ 1)(a _ {n + 1} - a _ 2)\cdots (a _ {n + 1}- a _ n)g(a _ {n + 1})$$

となりますが，$a _ {n + 1}$ が $a_1,a_2,\ldots,a_n$ と異なることから $g(a _ {n + 1})=0$ が成り立ちます．よって因数定理より $g(x)=(x - a _ {n + 1})h(x)$ を満たす $h(x)\in \mathbb{F} _ p[x]$ が存在します．このとき

$$f(x) = (x - a_1)(x-a_2)\cdots(x-a_n)(x-a_{n+1})h(x)$$

となるので示されました． $\blacksquare$

3.2. 方程式の解の個数

【定理 5】

$\mathbb{F} _ p$ 係数の多項式について，$n$ 次方程式の解の個数は $n$ 個以下である．つまり $f(x)=f_nx^n+\cdots+f_1x+f_0$ について $f_n\neq 0$ であるとき，$f(a)=0$ を満たす $a\in \mathbb{F} _ p$ の個数は $n$ 個以下である．

$n$ 個以上の解があると仮定して，解は $n$ 個ちょうどであることを示します．$n$ 個の解を $a_1,a_2,\ldots,a_n$ とすると【定理 4】から

$$f(x)=f_n(x-a_1)(x-a_2)\cdots(x-a_n)$$

が成り立ちます．$0$ でない数の積は $0$ でないことから，$f(x)=0$ の解は $a_1,a_2,\ldots,a_n$ に限られます． $\blacksquare$

次は，これまでの議論のうち素数であることが使われた部分を確認するための問題です．

【問題 6】

$n$ を素数とは限らない整数として，これまでの議論の $\mathbb{F} _ p$ の部分を環 $\mathbb{Z}/n\mathbb{Z}$ に取り換えたときに，以下のことを答えてください．

多項式の除法（【定義 1】）は同じように定義できますか？
剰余定理（【定理 2】）は成り立ちますか？
因数定理（【定理 3】）は成り立ちますか？
【定理 4】は成り立ちますか？
【定理 5】は成り立ちますか？

解説

一般には定義できません．$\mathbb{Z}/4\mathbb{Z}$ において，$f(x)=x^2, g(x)=2x$ としたときに【定義 1】の式を満たす $q(x), r(x)$ は存在しません．
除法は通常定義しないため，「余りは $f(a)$ である」という主張自体がこのままでは未定義になります．ただし多項式の除法は一般的には定義されないのですが，$g(x)=(x-a)$ の場合については同じようにできて，$f(x)=(x-a)q(x)+f(a)$ を満たす $q(x)$ は存在するため，ある意味では剰余定理は成り立つといってもよいでしょう．
成り立ちます．
成り立ちません．$\mathbb{Z}/4\mathbb{Z}$ において $f(x)=2x$，$a_1=0,a_2=2$ とすると反例となります．他には $\mathbb{Z}/8\mathbb{Z}$ において $f(x)=x^2-1$，$a_1=1,a_2=3,a_3=5,a_4=7$ とすると反例となります．【定理 4】の証明では $0$ でない数が乗法逆元を持つことが用いられており，ここが一般の $\mathbb{Z}/n\mathbb{Z}$ では破綻します．
成り立ちません．反例は 4 と同様です．証明については【定理 4】を用いた部分が破綻しているだけでなく，$f(x)=f_n(x-a_1)(x-a_2)\cdots(x-a_n)$ と因数分解したあとの議論も誤りになります．

3.3. $x ^ p - x$ の因数分解

【系 7】

$\mathbb{F} _ p[x]$ において $x ^ p - x=\prod_{a\in\mathbb{F} _ p}(x-a)$ が成り立つ．

Fermat の小定理と【定理 5】より示されます． $\blacksquare$

【系 8】（Wilson の定理）
$p$ を素数とするとき $(p-1)!\equiv -1 \pmod{p}$ が成り立つ．

【系 7】において両辺の $x ^ 1$ の係数を比較することで示されます． $\blacksquare$

4. Schwartz–Zippel の補題

Schwartz–Zippel の補題は，【定理 5】の一般化で，【定理 5】とともに乱択アルゴリズムの理論保証をする際の主要な道具となります．

本節では $x_1,x_2,\ldots,x_n$ を変数とする $\mathbb{F}_p$ 多項式を考えます．$n$ 変数の場合の多項式の定義も中学数学で扱うものと同じなので定義は省略します．

$x_1,x_2,\ldots,x_n$ を変数とする $\mathbb{F} _ p$ 多項式全体を $\mathbb{F} _ p[x_1,x_2,\ldots,x_n]$ と書きます．

【定理 9】（Schwartz–Zippel の補題）
$f(x_1,x_2,\ldots,x_n) \in \mathbb{F}_p[x_1,x_2,\ldots,x_n]$ を $0$ でない $d$ 次多項式とする．このとき， $\mathbb{F}_p$ の元の $n$ 個組 $(a_1,a_2,\ldots,a_n)$ であって $f(a_1,a_2,\ldots,a_n)=0$ を満たすものは $d\cdot p^{n-1}$ 個以下である．言い換えれば，組 $(a_1,a_2,\ldots,a_n)$ を一様ランダムに選ぶとき，$f(a_1,a_2,\ldots,a_n)=0$ となる確率は $\dfrac{d}{p}$ 以下である．

$n$ についての帰納法により証明します．$n=1$ の場合は【定理 5】で示されています．

$n$ の場合の結果を仮定して，$n+1$ の場合の結果を示します．$f(x_1,x_2,\ldots,x_n,t) \in \mathbb{F}_p[x_1,x_2,\ldots,x_n,t]$ を $0$ でない $d$ 次多項式とします．（$n+1$ 番目の変数を $t$ としています．）

$f(x_1,x_2,\ldots,x_n,t)$ の $t$ に関する次数を $k$ として，$t$ の多項式として見たときの $t ^ i$ の係数を $g_i(x_1,x_2,\ldots,x_n)\in \mathbb{F}_p[x_1,x_2,\ldots,x_n]$ とします．つまり

$$ f(x_1,x_2,\ldots,x_n,t)=\sum_{i=0} ^ k g_i(x_1,x_2,\ldots,x_n)t ^ i $$

により $g_i(x_1,x_2,\ldots,x_n)\in \mathbb{F}_p[x_1,x_2,\ldots,x_n]$ を定めます． $g_k$ は $0$ ではなく，その次数は $d-k$ 以下です．

$(a_1,a_2,\ldots,a_n,a_{n+1})$ を一様ランダムに選ぶとき，

帰納法の仮定より，$g_k(a_1,\ldots,a_n)=0$ となる確率は $\dfrac{d-k}{p}$ 以下です．
$g_k(a_1,\ldots,a_n)\neq 0$ である場合，【定理 5】より，$f(a_1,a_2,\ldots,a_n,a_{n+1})=0$ となる確率は $\dfrac{k}{p}$ 以下です．

ここから $f(a_1,a_2,\ldots,a_n,a_{n+1})=0$ となる確率は，$\dfrac{d-k}{p}+\dfrac{k}{p}=\dfrac{d}{p}$ 以下であることが分かります． $\blacksquare$

5. 関連問題

6. まとめ

本記事では，$\mathbb{F}_p$ 係数の多項式について解説しました．

本記事の内容は，競技プログラミングの問題に直接適用するという機会はあまり多くないと思いますが，多くの応用がある重要な内容です．特に初等整数論では，原始根の存在証明に【定理 5】が用いられます．

他には文字列のハッシュ手法であるローリングハッシュの解析に【定理 5】が用いられることが有名です．

【系 7】は競技プログラミングでもときどき用いられる有名事実ですが，$\mathbb{F}_p$ における方程式の求解や，有限体の理論でも重要になります．

【定理 5】の一般化である Schwartz–Zippel の補題（【定理 9】）は，様々なハッシュの解析に用いられる他，Tutte 行列による最大マッチングの計算アルゴリズムなどへの応用もあります．

7. 参考文献

Wikipedia．Schwartz–Zippel lemma．https://en.wikipedia.org/wiki/Schwartz%E2%80%93Zippel_lemma．（閲覧日: 2026-03-31）．
mapsy．[多項式・形式的べき級数]（補足）定義や式変形の正当性の確認．https://maspypy.com/[多項式・形式的べき級数]（補足）定義や式変形の正当性の確認．（閲覧日: 2026-03-31）．
noshi91．Schwartz–Zippel lemma による hash の解析．https://github.com/noshi91/blog/blob/master/pages/hash.pdf．（閲覧日: 2026-03-31）．

トップページ：AtCoder Algorithm Lectures