合同式は法が素数のベキ乗の場合に帰着する

本記事の内容

本記事は、一般の整数が法であるような多項式の合同式の解き方について解説する記事です。

本記事を読むに当たり、法が素数のベキ乗であるような場合の多項式の合同式の解の存在条件について知っている必要があるため、以下の記事も合わせてご覧ください。

多項式の合同式の解の個数と存在条件(法が合成数)

...

for-spring.com

2023.04.23

サラッと復習(読み飛ばしてもOK)

前回解説したことをサラッと復習します。

整数係数多項式

整数係数多項式の合同式

$f(x)$を整数係数多項式、すなわち
$$f(x)=\sum_{i=0}^na_ix_i=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0$$
($a_i\in\mathbb{Z}$、$n\in\mathbb{N}\cup\left\{ 0\right\}$)とします。
このとき、$m\in\mathbb{Z}$に対して、合同式
$$f(x)\equiv\ ({\rm mod}\ m)\tag{1}$$
を整数係数多項式の合同式といいます。

次数

$f(x)$を整数係数多項式、すなわち
$$f(x)=\sum_{i=0}^na_ix_i=a_nx^n+a_{n-1}x^{n-1}+\cdots+a_2x^2+a_1x+a_0$$
($a_i\in\mathbb{Z}$、$n\in\mathbb{N}\cup\left\{ 0\right\}$)とします。
このとき、$m\in\mathbb{Z}$に対して、合同式
$$f(x)\equiv\ ({\rm mod}\ m)\tag{1}$$
を解くには、各係数$a_\nu$を、$m$を法として$a_\nu$と合同な数で置き換えてOKです。

なぜなら、次が成り立つからです。

定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。

また、$a_\nu$の中で、$m$で割り切れるときは$a_\nu x^\nu$の項は消してOKです。
このような消去を行った後に、$a_n\not\equiv0\ ({\rm mod}\ m)$であれば、上記の合同式
$$f(x)\equiv\ ({\rm mod}\ m)$$
を$n$次の合同式と呼ぶことにします。

法が素数の場合の整数係数多項式の合同式の解の個数

一般の法に関する多項式の合同式の解は、法が素数ベキの場合に帰着します。

実は、これについては以前にサラッと述べています。
しかし、主張として明言しておらず、証明の伴っていなかったため、ここで明言しておこう、という記事です。

なぜ素数のベキ乗の場合に帰着するのか？(サラッと流れを紹介)

結論から言えば「中国式剰余定理が成り立つから」です

$f(x)$を$n$次の整数係数多項式とします。
また、$m\in\mathbb{Z}$が合成数(素数でない整数)であるとします。
本来考察したい合同式は
$$f(x)\equiv0\ ({\rm mod}\ m)\tag{1}$$
です。
この(1)の解法は法が素数の場合に帰着します。

$m$は以下のように一意的に変形することができます。

なぜなら、次の事実が成り立っているからです。

定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その8を御覧ください。

要するに、$m$を素因数分解した、ということです。

これを踏まえて(1)を変形すると、
$$f(x)\equiv0\ ({\rm mod}\ m)\Longleftrightarrow f(x)\equiv0\ ({\rm mod}\ p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k})$$
です。

すなわち、
$$(\exists l\in\mathbb{Z})\ {\rm s.t.}\ f(x)=l\cdot p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k}$$
です。

このとき、中国式剰余定理を使います。

定理4.(中国式剰余定理)の証明は【代数学の基礎シリーズ】初等整数論編 その12を御覧ください。

中国式剰余定理から、$p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k}$に対して、
$$(\forall i\in\mathbb{N}\ ;\ 1\leq i\leq k)\ f(x)\equiv0\ ({\rm mod}\ p_i^{a_i})\Longleftrightarrow f(x)\equiv 0\ ({\rm mod}\ p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k})$$
が成り立つのです。

したがって、結局の所は素数$p$と自然数$n$に対して
$$f(x)\equiv0\ ({\rm mod}\ p^{n})$$
という形の合同式の解がわかれば良い、ということになるのです。

主張の明示とその証明

では、主張を明示します。

文自体は長いですが、主張としてはシンプルです。

要するに、整数係数の多項式の連立合同式に対して、その法が一般の整数だった場合、各合同式の解の個数の積が元の連立合同式の解の個数となり、解も各合同式の解から導けますよ、という主張です。

平たく言えば、

と言う主張なのです。

この定理の証明は今まで扱った主張を組み合わせることで直ちに証明完了です。

いざ、証明

では、証明をしていきます。
ただ、先述の通り、今まで扱った主張を組み合わせて順々に論をすすめることで証明できるので、是非挑戦してみて下さい。

定理0.の証明

$x\in\mathbb{Z}$が(4)の解、すなわち
$$f(x)\equiv0\ ({\rm mod}\ m)\tag{4}$$
を満たすとしましょう。

このとき、法$m\in\mathbb{Z}$を

と変形します。
なぜこのように変形できるかというと、定理3.(素因数分解定理)が成り立っているからです。

これを踏まえれば、(4)を変形すると、
$$f(x)\equiv0\ ({\rm mod}\ m)\Longleftrightarrow f(x)\equiv0\ ({\rm mod}\ p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k})$$
です。
すなわち、
$$(\exists l\in\mathbb{Z})\ {\rm s.t.}\ f(x)=l\cdot p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k}$$
です。

ここで定理4.(中国式剰余定理)を使えば、$p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k}$に対して、
$$(\forall i\in\mathbb{N}\ ;\ 1\leq i\leq k)\ f(x)\equiv0\ ({\rm mod}\ p_i^{a_i})\Longleftrightarrow f(x)\equiv 0\ ({\rm mod}\ p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k})$$
が成り立ちます。

したがって、(4)の解$x\in\mathbb{Z}$は
$$\begin{align} &f(x)\equiv0\ ({\rm mod}\ p^{a_1})\tag{2}\\ &f(x)\equiv0\ ({\rm mod}\ p^{a_2})\tag{3}\\ &\qquad \quad\vdots\\ &f(x)\equiv0\ ({\rm mod}\ p^{a_n})\\ \end{align}$$
を満たすわけですから、勿論(2)も満たすし、(3)も満たします。

そして、$\alpha_1,\ \alpha_2,\cdots,\alpha_n$はそれぞれ(p^{a_1},\ p^{a_2},\cdots,p^{a_n})を法としての(f(x)\equiv0)の解、すなわち
$$\begin{eqnarray} \begin{cases} f(x)\equiv0\ ({\rm mod}\ p^{a_1})\\ f(x)\equiv0\ ({\rm mod}\ p^{a_2})\\ \qquad \qquad \vdots\\ f(x)\equiv0\ ({\rm mod}\ p^{a_n})\\ \end{cases} \end{eqnarray}$$
の解の任意の一組だったため、
$$\begin{eqnarray} \begin{cases} x\equiv\alpha_1\ ({\rm mod}\ p^{a_1})\\ x\equiv\alpha_2\ ({\rm mod}\ p^{a_2})\\ \qquad \qquad \vdots\tag{5}\\ x\equiv\alpha_n\ ({\rm mod}\ p^{a_n})\\ \end{cases} \end{eqnarray}$$
を満たします。

逆に、(5)を満たしているような$x\in\mathbb{Z}$は、
$$\begin{align} &f(x)\equiv0\ ({\rm mod}\ p^{a_1})\tag{2}\\ &f(x)\equiv0\ ({\rm mod}\ p^{a_2})\tag{3}\\ &\qquad \quad\vdots\\ &f(x)\equiv0\ ({\rm mod}\ p^{a_n})\\ \end{align}$$
を満たしているわけですから、結局は
$$f(x)\equiv0\ ({\rm mod}\ m)\tag{4}$$
を満たしているということになります。

あとは、$\alpha_1,\ \alpha_2,\cdots,\alpha_n$は
$$\begin{eqnarray} \begin{cases} f(x)\equiv0\ ({\rm mod}\ p^{a_1})\\ f(x)\equiv0\ ({\rm mod}\ p^{a_2})\\ \qquad \qquad \vdots\\ f(x)\equiv0\ ({\rm mod}\ p^{a_n})\\ \end{cases} \end{eqnarray}$$
の解の任意の一組だっため、この連立合同式の各合同式の解の個数を(\nu_1,\ \nu_2,\cdots,\nu_n\)個とすれば、$\alpha_1,\ \alpha_2,\cdots,\alpha_n$のパターンは$\nu_1\nu_2\cdots\nu_n$個ある、ということになるわけです。

定理0.の証明終わり

解いてみる

例題を解いてみましょう。

例. $x^2\equiv0\ ({\rm mod}\ 12)$

$12=2^2\cdot3$と素因数分解します。
$x^2\equiv1\ ({\rm mod}\ 3)$は2つの解$\alpha\equiv\pm1\ ({\rm mod}\ 3)$を持ちます。
また、$x^2\equiv1\ ({\rm mod}\ 2^2)$は2つの解$\beta\equiv\pm1\ ({\rm mod}\ 2^2)$を持ちます。

故に、$x^2\equiv0\ ({\rm mod}\ 12)$は4つの解を持ちます。
そしてそれらの4つの解は
$$\begin{eqnarray} \begin{cases} x\equiv1\ ({\rm mod}\ 3)\\ x\equiv1\ ({\rm mod}\ 2^2)\\ \end{cases},\ \begin{cases} x\equiv1\ ({\rm mod}\ 3)\\ x\equiv-1\ ({\rm mod}\ 2^2)\\ \end{cases},\ \begin{cases} x\equiv-1\ ({\rm mod}\ 3)\\ x\equiv1\ ({\rm mod}\ 2^2)\\ \end{cases},\ \begin{cases} x\equiv-1\ ({\rm mod}\ 3)\\ x\equiv-1\ ({\rm mod}\ 2^2)\\ \end{cases} \end{eqnarray}$$
から求まります。
すなわち、
$$x\equiv1,\ 7,\ 5,\ 11\ ({\rm mod}\ 12)$$
が答えです。

皆様のコメントを下さい！

新年度が始まって1ヶ月が経とうとしています。
新環境で頑張っていらっしゃる方も多いことでしょう。

4月はどんな月でしたか？
お仕事、学生生活、どうですか？
筆者は新社会人となりましたが、会社の方々に良くしていただいています。

是非コメントで教えて下さい！

結

今回は、一般の整数が法であるような多項式の合同式の解き方について解説しました。
法が合成数の場合は結局の所、法が素数の場合に帰着されます。
今回で「中国式剰余定理って強力じゃん！」と思った方も多いのではないでしょうか。
そうです。強力です。

次回は、数論的関数(平たく言えば数論でよく使われる関数)の代表例、オイラー関数について解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)

初等整数論について、以下の書籍をオススメします！