多項式の合同の基礎
本ページでは、合同式の概念を整数係数の多項式に拡張する。
多項式の合同の定義
まず、整数係数多項式の合同について定義する。$2$つの整数係数多項式 $P(X), Q(X)$ が $n$ を法として合同であるとは、各 $X^k (k=0, 1, \ldots)$ の係数がすべて整数 $n$ を法として合同であることをいい、$P(X)\equiv Q(X)\Mod{n}$ であらわす。$P(X)\equiv Q(X)\Mod{n}$ は $P(X)-Q(X)$ の係数がすべて $n$ で割り切れることと言い換えられる。
合同式の導入:定理2
より $x, y$ が整数で $P(X)\equiv Q(X)\Mod{n}$ かつ $x\equiv y\Mod{n}$ ならば $P(x)\equiv Q(y)\Mod{n}$ となる。
とくに $x\equiv y\Mod{n}$ のとき $P(x)\equiv 0\Mod{n}\Longleftrightarrow P(y)\equiv 0\Mod{n}$ となる。
$\Z$ における剰余類の定義と同様に、$\Z[X]$ における剰余類を
$$R(X)\Mod{Q(X)}=Q(X)\Z[X] +R(X)=\{Q(X)P(X)+R(X), P(X)\in\Z[X]\}$$
と定義すると
$$P(X)\equiv Q(X)\Mod{n}\Longleftrightarrow n\Z[X]+P(X)=n\Z[X]+Q(X)$$
が成り立つ。
多項式の剰余類 $P(X)\Mod{n}$ の次数は、$P(X)$ の係数が $n$ で割り切れない最も高い $X$ の次数と一致する。これを $n$ を法とする多項式 $P(X)$ の次数といい、$\deg P(X)\Mod{p}$ であらわすことにする。
それで、$P(X)\Mod{n}$ の次数が $d$ のとき $P(X)\equiv P_1(x)\Mod{n}$ となる、$d$ 次の、最高次の係数が $n$ で割り切れない整数係数多項式 $P_1(X)$ がとれる。
素数を法とする多項式の次数
$p$ が素数のとき、$p$ を法とする $P(X), Q(X)$ の次数をそれぞれ $e, f$ とおくと $p$ を法とする $P(X)Q(X)$ の次数は $e+f$ に一致する。
実際
$$P(X)\equiv a_e x^e+\cdots +a_0, Q(X)\equiv b_f x^f+\cdots +b_0 \Mod{p}, \gcd(p, a_e)=\gcd(p, b_f)=1$$
となるように係数をとると
$$P(X) Q(X)\equiv a_e b_f x^{e+f}+\cdots +a_0 b_0\Mod{p}$$
となるが、$\gcd(p, a_e)=\gcd(p, b_f)=1$ より $\gcd(p, a_e b_f)=1$ なので、$p$ を法とする $P(X)Q(X)$ の次数は $e+f$ に一致する。
この定理は、$p$ が素数でないときには一般には成り立たない。たとえば
$$(2X+1)(3X+1)\equiv 6X^2+5X+1\equiv 5X+1\Mod{6}$$
となり、$6$ を法とする $(2X+1)(3X+1)$ の次数は $1$ となる。
$p$ が素数のとき、$p$ を法とする $f(X), g(X)$ の次数をそれぞれ $e, f$ とおくと $e\geq f$ のとき
$$f(X)\equiv Q(X)g(X)+R(X)\Mod{p}$$
となる多項式 $Q(X), R(X)$ で $p$ を法とする $\deg Q(X) \Mod{p}=e-f, \deg R(X)\Mod{p}\leq f-1$ となるものが $p$ を法として一意的に定まる。
すなわち、$p$ を法とする多項式の計算においても除法の原理が成立する。
$$f(X)\equiv a_e X^e+\cdots +a_0, g(X)\equiv b_f X^f+\cdots +b_0 \Mod{p}, \gcd(p, a_e)=\gcd(p, b_f)=1$$
となる係数がとれる。
$e=f$ のとき、
$$f(X)-sg(X)=(a_e-b_e s) X^e+(a_{e-1}-b_{e-1} s) X^{e-1}+\cdots +(a_0-b_0 s)\Mod{p}$$
より
$$\deg (f(X)-sg(X))\Mod {p} \leq f-1\Longleftrightarrow a_e\equiv b_e s\Mod{p}$$
となる。よって、定理の条件を満足するものは
$Q(X)\equiv a_e b_e^{-1}\Mod{p}, R(X)\equiv (a_{e-1}-b_{e-1} s) X^{e-1}+\cdots +(a_0-b_0 s)\Mod{p}$ により $p$ を法として一意的に定まる。
$e\leq f+k-1$ のとき定理が正しいと仮定し、$e=f+k$ の場合を考える。
$$f(X)-sX^k g(X)=(a_e-b_f s) X^e+(a_{e-1}-b_{f-1} s) X^{e-1}+\cdots +(a_k-b_0 s)X^k+a_{k-1} X^{k-1}+\cdots +a_0\Mod{p}$$
より、
$$\deg (f(X)-sg(X))\leq f+k-1\Longleftrightarrow a_e\equiv b_f s\Mod{p}$$
となる。そして $\deg (f(X)-sg(X))\Mod{p} \leq f+k-1$ のとき、仮定より
$$(f(X)-sX^k g(X))-Q_1(X)g(X)=R_1(X)\Mod{p}$$
かつ $\deg Q_1(X) \Mod{p}=\deg (f(X)-sg(X))\Mod{p}-f, \deg R_1(X)\Mod{p}\leq f-1$ となる $Q_1(X), R(X)$ が $p$ を法として一意的に定まる。
よって、定理の条件を満足するものは $Q(X)\equiv (a_e b_f^{-1})X^k+Q_1(X)\Mod{p}, R(X)\equiv R_1(X)\Mod{p}$ により $p$ を法として一意的に定まる。
これらのことから、数学的帰納法より、$e\geq f$ のとき定理は成り立つことが証明された。
素数を法とする方程式
上記のことから、与えられた整数係数多項式 $P$ の、与えられた整数 $x$ における値 $P(x)$ の属する剰余類は、$P$ の属する剰余類 $P\Mod{n}$ と $x$ の属する剰余類 $x\Mod{n}$ のみによって定まる。それで、この剰余類を
$$P\Mod{n}(x\Mod{n})$$
と定める。とくに、
$$P(x)\equiv 0\Mod{n}\Longleftrightarrow P\Mod{n}(x\Mod{n}) \equiv 0\Mod{n}$$
となって、$P(x)\equiv 0\Mod{n}$ の解は $P$ の属する剰余類と $x$ の属する剰余類のみで定まるといえるので、$P(x)\equiv 0\Mod{n}$ となるような剰余類 $x\Mod{n}$ そのものを $P(x)\equiv 0\Mod{n}$ の解とみることができる。法が素数の場合、解を与える剰余類について次のことがわかる。
$p$ が素数で、整数 $a$ について
$$P(a)\equiv 0\Mod{p}$$
となるとき
$$P(X)\equiv (X-a)Q(X)\Mod{p}$$
となる多項式 $Q(X)$ がとれる。さらに、$a\Mod{p}$ と合同でない整数 $b$ について
$$P(b)\equiv 0\Mod{p}$$
となるとき
$$Q(b)\equiv 0\Mod{p}$$
も成り立つ。すなわち $a\Mod{p}$ 以外の剰余類で
$$P(x)\equiv 0\Mod{p}$$
の解となるものは
$$Q(x)\equiv 0\Mod{p}$$
の解でもある。
また、
$$P(x)\equiv 0\Mod{p}$$
の解となる剰余類の個数は、$\deg P(x)\Mod{p}$ 以下である。
定理2
より
$$P(X)\equiv (X-a)Q(X)+c\Mod{p}$$
となる $c$ がとれる。$X=a$ を代入すると
$$c\equiv P(a)\equiv 0\Mod{p}$$
より、
$$P(X)\equiv (X-a)Q(X)\Mod{p}$$
が成り立つ。このとき、$b\not\equiv a\Mod{p}$ で
$$P(b)\equiv 0\Mod{p}$$
ならば
$$(b-a)Q(b)\equiv P(b)\equiv 0\Mod{p}$$
となるが、$p$ は $b-a$ を割り切らないから
倍数と約数: 定理5
より
$p$ は $Q(b)$ を割り切る。つまり
$$Q(b)\equiv 0\Mod{p}$$
も成り立つ。
最後に、$d=\deg P(x)\Mod{p}$ とし、
$$P(x)\equiv 0\Mod{p}$$
が $d+1$ 個の解 $a_1, a_2, \ldots, a_{d+1}\Mod{p}$ をもつとすると、先に証明したことから
$$P(X)\equiv (X-a_1)P_1(X)\Mod{p}$$
となる多項式 $P_1(X)$ が存在し、$a_2, \ldots, a_{d+1}\Mod{p}$ は
$$P_1(x)\equiv 0\Mod{p}$$
の解である。これを繰り返し
$$P(X)\equiv (X-a_1)(X-a_2)\cdots (X-a_{d+1})Q(X)\Mod{p}$$
となる多項式 $Q(X)$ がとれるので、
$$\deg P(x)\Mod{p}\geq d+1+\deg Q(x)\Mod{p}>d=\deg P(x)\Mod{p}$$
となり、矛盾する。よって
$$P(x)\equiv 0\Mod{p}$$
の解となる剰余類の個数は、$d=\deg P(x)\Mod{p}$ 以下である。
たとえば
$$x(x-1)\equiv 0\Mod{2}$$
は、ちょうど $2$ つの解 $x\equiv 0, 1\Mod{2}$ をもつ。このことから、
$\Z/2\Z$ において $x(x-1)$ はつねに $0$ をとる。しかし、$X(X-1)\nequiv 0\Mod{2}$ なので、これは零多項式ではない。
つまり、$\Z/p\Z$ 上では恒等的に $0$ となるからといって零多項式になるとは限らない。
もちろん、定理3は法が素数でないときには一般には成り立たない。たとえば
$$x^2\equiv 1\Mod{8}$$
は $4$ つの解 $x\equiv 1, 3, 5, 7\Mod{8}$ をもつ。
参考文献
