本記事の内容
本記事は、一般の整数が法であるような多項式の合同式の解き方について解説する記事です。
本記事を読むに当たり、法が素数のベキ乗であるような場合の多項式の合同式の解の存在条件について知っている必要があるため、以下の記事も合わせてご覧ください。
サラッと復習(読み飛ばしてもOK)
前回解説したことをサラッと復習します。
整数係数多項式
整(数)係数多項式、整(数)係数多項式関数
- 整(数)係数多項式 $$ P(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\}\))の形の式を\(x\)の整(数)係数多項式(Polynomial with real coefficients)という。
- 整(数)係数多項式関数 関数\(f:X\longrightarrow Y\)が任意の\(x\in X\)に対して\(f(x)=P(x)\)を満たすとき、\(f\)は(整(数)係数)多項式関数という。
整数係数多項式の合同式
\(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.
\(a,a^\prime,b,b^\prime\in\mathbb{Z}\)、\(m\in\mathbb{Z}\setminus\left\{ 0\right\}\)とする。このとき $$a\equiv a^\prime\ ({\rm mod}\ m),\quad b\equiv b^\prime\ ({\rm mod}\ m)$$ が成り立つならば、- \(a\pm b\equiv a^\prime\pm b^\prime\ ({\rm mod}\ m)\),
- \(ab\equiv a^\prime b^\prime\ ({\rm mod}\ m)\)
一般に、\(a\equiv a^\prime\ ({\rm mod}\ m)\)、\(b\equiv b\ ({\rm mod}\ m)\)、\(c\equiv c^\prime\ ({\rm mod}\ m)\cdots\)で、また\(f(x,y,z,\cdots)\)が\(x,y,z,\cdots\)に関する整数を係数とする多項式であれば、 $$ f(a,b,c,\cdots\cdots)\equiv f(a^\prime,b^\prime,c^\prime,\cdots\cdots)\ ({\rm mod}\ m) $$ である。
定理1.の証明は【代数学の基礎シリーズ】初等整数論編 その10を御覧ください。
また、\(a_\nu\)の中で、\(m\)で割り切れるときは\(a_\nu x^\nu\)の項は消してOKです。
このような消去を行った後に、\(a_n\not\equiv0\ ({\rm mod}\ m)\)であれば、上記の合同式
$$
f(x)\equiv\ ({\rm mod}\ m)
$$
を\(n\)次の合同式と呼ぶことにします。
法が素数の場合の整数係数多項式の合同式の解の個数
定理2.
法\(p\)が素数であるとき、\(n\)次の合同式 $$ f(x)\equiv\ ({\rm mod}\ p)\tag{2} $$ は\(n\)個より多くの解を持つことはない。ただし、解の個数は\(p\)を法として互いに合同でないものを数えていう。一般の法に関する多項式の合同式の解は、法が素数ベキの場合に帰着します。
実は、これについては以前にサラッと述べています。
しかし、主張として明言しておらず、証明の伴っていなかったため、ここで明言しておこう、という記事です。
なぜ素数のベキ乗の場合に帰着するのか？(サラッと流れを紹介)
結論から言えば「中国式剰余定理が成り立つから」です
\(f(x)\)を\(n\)次の整数係数多項式とします。
また、\(m\in\mathbb{Z}\)が合成数(素数でない整数)であるとします。
本来考察したい合同式は
$$
f(x)\equiv0\ ({\rm mod}\ m)\tag{1}
$$
です。
この(1)の解法は法が素数の場合に帰着します。
\(m\)は以下のように一意的に変形することができます。
なぜなら、次の事実が成り立っているからです。
定理3.(素因数分解定理)
合成数は重複を許して素数の積に分解することができる。また、その分解は一意的である。すなわち、\(a\)が正の整数であれば、素数\(p_1,\cdots,p_t\)が重複を許して存在し、 $$ a=p_1\cdots p_t $$ と書くことができる。ただし、\(a=1\)の場合は\(t=0\)と解釈する。また、\(p_1,\cdots,p_t\)は順序を除いて一意的である。定理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.(連立合同式の解の存在条件、中国式剰余定理)
\(m_1,m_2,\cdots,m_k\in\mathbb{Z}\)が2つずつ互いに素、すなわち、 $$ \left( \forall i,j\in\left\{1,2,\cdots,k \right\}:i\neq j\right)\ \gcd(m_i,m_j)=1 $$ (どの2つの\(m_i\)、\(m_j\)も自身以外と互いに素)であり、\(a_1,a_2,\cdots,a_k\in\mathbb{Z}\)とする。このとき、 $$ \begin{cases} x\equiv a_1\ ({\rm mod}\ m_1)\\ x\equiv a_2\ ({\rm mod}\ m_2)\\ \qquad \quad\vdots\\ x\equiv a_k\ ({\rm mod}\ m_k)\\ \end{cases} $$ を満たす\(x\)の類は\(\displaystyle M=\prod_{l=1}^km_l=m_1m_2\cdots m_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.
法\(m\in\mathbb{Z}\)を $$ m=p^{a_1}p^{a_2}\cdots p^{a_n}\tag{1} $$ と素因数分解したとし、\(f(x)\)を整数係数多項式とする。このとき \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} がそれぞれ\(\nu_1,\ \nu_2,\cdots,\nu_n\)個の解を持つならば、 $$ f(x)\equiv0\ ({\rm mod}\ m)\tag{4} $$ は\(\nu_1\nu_2\cdots\nu_n\)個の解を持つ。そして、それらの解は \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} から求められる。ただし、\(\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} の解の任意の一組である。文自体は長いですが、主張としてはシンプルです。
要するに、整数係数の多項式の連立合同式に対して、その法が一般の整数だった場合、各合同式の解の個数の積が元の連立合同式の解の個数となり、解も各合同式の解から導けますよ、という主張です。
平たく言えば、
と言う主張なのです。
この定理の証明は今まで扱った主張を組み合わせることで直ちに証明完了です。
いざ、証明
では、証明をしていきます。
ただ、先述の通り、今まで扱った主張を組み合わせて順々に論をすすめることで証明できるので、是非挑戦してみて下さい。
定理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月はどんな月でしたか？
お仕事、学生生活、どうですか？
筆者は新社会人となりましたが、会社の方々に良くしていただいています。
是非コメントで教えて下さい！
結
今回は、一般の整数が法であるような多項式の合同式の解き方について解説しました。
法が合成数の場合は結局の所、法が素数の場合に帰着されます。
今回で「中国式剰余定理って強力じゃん！」と思った方も多いのではないでしょうか。
そうです。強力です。
次回は、数論的関数(平たく言えば数論でよく使われる関数)の代表例、オイラー関数について解説します。
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)
初等整数論について、以下の書籍をオススメします！
コメントをする