本記事の内容
本記事は、多項式の合同式(法が素数の場合)の解き方について解説する記事です。
本記事を読むに当たり、合同式を知っている必要があるため、以下の記事も合わせてご覧ください。
多項式の合同式？整数係数多項式の合同式？
まずは復習をし、その後整数係数多項式を導入します。
多項式って？(復習)
まず、多項式及び多項式関数について復習します。
実係数多項式
- 実係数多項式 $$ 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{R}\)、\(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\)は(実係数)多項式関数という。
不要かもしれませんが、
$$
x^2+2x+1,\quad 3x^7-\frac{1}{7}x^3+\pi x
$$
などが実係数多項式です。
後者は見慣れないかもしれませんが、”実係数”ですので、実係数多項式としては後者の要な場合もありえます。
整数係数(または、単に整係数)多項式は、単に係数が整数というだけです。
つまり、先の例の前者は整数係数多項式です。
整(数)係数多項式、整(数)係数多項式関数
- 整(数)係数多項式 $$ 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}
$$
を整数係数多項式の合同式といいます。
代数学の基本定理（サラッと説明）※証明はしません
一旦、解いてみて下さい！
以下の問題を解いてみて下さい(大丈夫、簡単です)。
例1. \(x^2-3x+2=0\)の解を求めよ。
勿論、\(x^2-3x+2=(x-1)(x-2)=0\)により、\(x=1,2\)が答えですね。
例2. \(x^2-2x+1=0\)の解を求めよ。
勿論、\(x^2-2x+1=(x-1)^2=0\)により、\(x=1\)ですね。
このように、２次方程式は多くとも2個の解しか持ちません。
重解を2つ解(例えば例2.でいえば、\(x=1,1\)と捉える)と捉えれば、ちょうど2つです。
実は、複素係数\(n\)次方程式は複素数の範囲で\(n\)個より多くの解を持たないのです。
重複を許せば、複素係数\(n\)次方程式はちょうど\(n\)個の解を持ちます。
これが代数学の基本定理のイメージです(厳密にはちょっと違うのですがそれは後述)。
代数学の基本定理 ※証明はしません
代数学の基本定理とは以下です。
代数学の基本定理
複素係数の\(n\)次方程式 $$ x^n+a_{n-1}x^n+a_{n-2}x^{n-2}+\cdots+a_1x+a_0=0\quad a_0,a_1,\cdots,a_{n-1}\in\mathbb{C} $$ は必ず複素数に根を持つ。「あれ？さっきと話が違うじゃないか？」と思うでしょう。
確かにそうです。
ただ、この代数学の基本定理から次の事実がわかります。
定理0.
複素係数の\(n\)次方程式 $$ f(x)=x^n+a_{n-1}x^n+a_{n-2}x^{n-2}+\cdots+a_1x+a_0=0\quad a_0,a_1,\cdots,a_{n-1}\in\mathbb{C} $$ は必ず $$ f(x)=(x-\alpha_1)(x-\alpha_2)\cdots(x-\alpha_n) $$ (\(\alpha_1,\cdots,\alpha_n\))と一次式の積に因数分解できる。定理0.の証明
代数学の基本定理から、\(f(\alpha_1)=0\)となるような\(\alpha_1\in\mathbb{C}\)が存在します。
多項式\(f(x)\)を一次式\((x-\alpha_1)\)で割って、
$$
f(x)=f_1(x)(x-\alpha_1)+r
$$
(ただし、\(f_1(x)\)は\(n-1\)次多項式、\(r\in\mathbb{C}\))と書けます。
\(\alpha_1\)を代入して両辺を比較すると、\(r=0\)だとわかります。
すなわち、\(f(x)=f_1(x)(x-\alpha_1)\)となります。
今の議論を\(f_1(x)\)に適用すれば、
$$
f_1(x)=f_2(x)(x-\alpha_1)(x-\alpha_2)
$$
(ただし、\(f_2(x)\)は\(n-2\)次多項式、\(\alpha_2\in\mathbb{C}\))と書くことができます。
この操作を繰り返していけば、題意のような分解が得られます。
定理0.の証明終わり
さて、定理0.から、\(\alpha_1,\cdots,\alpha_n\)は勿論\(f(x)=0\)の根(答え)になりますが、実は根はこれらしか存在しません。
実際、仮に\(\alpha_1,\cdots,\alpha_n\)とは異なる\(\beta\in\mathbb{C}\)に対して、\(f(\beta)=0\)になったとしましょう。
定理0.の分解式に代入すれば、
$$
(\beta-\alpha_1)(\beta-\alpha_2)\cdots(\beta-\alpha_n)=0
$$
が成り立ちます。
ここで、\(0\)でない複素数は必ず逆数を持つから、両辺に\((\beta-\alpha_1)^{-1}(\beta-\alpha_2)^{-1}\cdots(\beta-\alpha_n)^{-1}\)を掛けると、\(1=0\)となり、矛盾です。
以上の話から、代数学の基本定理により、複素係数\(n\)次方程式は重複を含めてちょうど\(n\)個の解を持つという事実を導くことができるのです。
多項式の合同式でも似たような事実が成り立ちます。
多項式の合同式でも似たような事実が成り立ちますよ、というのが今回の内容です。
ただし、今回は法は素数の場合に限って解説します。
ちょっとその前に…(次数)
\(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\)を法として互いに合同でないものを数えていう。定理2.の証明
合同式(2)が解を持ったとして、\(x\equiv a\ ({\rm mod}\ p)\)をその1つの解とします。
すなわち、\(f(a)\equiv0\ ({\rm mod}\ p)\)です。
さて、次の恒等式を考えます。
$$
f(x)=(x-a)f_1(x)+f(a)
$$
において、\(f_1(x)\)は\(a_nx^{n-1}\)を最高次数の項とする整数係数の多項式です。
故に、合同式(2)は
$$
(x-a)f_1(x)\equiv 0\ ({\rm mod}\ p)
$$
と同じ解を持ちます。
\(p\)は素数だから、この合同式は\(x-a\)または\(f_1(x)\)が\(p\)で割り切れるときに限って成り立ちます。
実際、\((x-a)f_1(x)\equiv 0\ ({\rm mod}\ p)\)により
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ (x-a)f_1(x)=kp
$$
となり、\(p\)が\(x-a\)または\(f_1(x)\)を割り切ります。
今、\(x\equiv a\ ({\rm mod}\ p)\)なわけですので、\(f_1(x)\equiv0\ ({\rm mod}\ p)\)です。
故に、\(x\equiv a\ ({\rm mod}\ p)\)以外の(2)の解は\(n-1\)次の合同式
$$
f_1(x)\equiv\ ({\rm mod}\ p)
$$
の解でなければなりません。
故に、定理の主張が\(n-1\)次の多項式に関して正しければ、\(n\)次の多項式に関しても正しいことになります。
ここで、次の事実を使います。
定理3.
一次合同式 $$ ax\equiv b\ ({\rm mod}\ m) $$ は\(\gcd(a,m)=1\)なるときは、1つの解を持つ。\(\gcd(a,m)=d>1\)であるときは、\(b\)が\(d\)で割り切れるときに限って解を持つ。その解の数は\(d\)である。ただし、解の数は\(m\)を法としての類の関してである。定理3.の証明は【代数学の基礎シリーズ】初等整数論編 その11を御覧ください。
定理3.から、一次の合同式
$$
a_1x+a_0\equiv0\ ({\rm mod}\ p),\quad \gcd(a_1,p)=1
$$
は\(p\)を法として唯一の解を持ちます。
したがって、定理2.は数学的帰納法で証明されました。
定理2.の証明終わり
実際に確かめてみる
例3.
例えば、\(x^2\equiv-2\ ({\rm mod}\ 11)\)を解いてみましょう。
\(x^2\equiv9\ ({\rm mod}\ 11)\)ですから、\(x\equiv3\ ({\rm mod}\ 11)\)は一つの会です。
故に、
$$
(11-3)^2\equiv11^2-2\times 11\times 3+3^2\ ({\rm mod}\ 11)
$$
に\(9\equiv-1\ ({\rm mod}\ 11)\)により、を代入することで\((11-3)^2\equiv-2\ ({\rm mod}\ 11)\)です。
したがって、\(8^2\equiv-2\ ({\rm mod}\ 11)\)から\(x\equiv8\ ({\rm mod}\ 11)\)も解です。
確かに2個ですね。
例4.
例えば、\(x^2\equiv1\ ({\rm mod}\ 15)\)を解いてみましょう。
$$
(\exists k_1\in\mathbb{Z})\ {\rm s.t.}\ x^2-1=15k\Longleftrightarrow x^2-1=3\times1\times 5\timesk_1
$$
と書けるため、
$$
x^2\equiv1\ ({\rm mod}\ 3)\quad \land\quad x^2\equiv1\ ({\rm mod}\ 5)
$$
です。
\(x\equiv 1\ ({\rm mod}\ 3)\)については、\((x+1)(x-1)\equiv1\ ({\rm mod}\ 3)\)であり、かつ\(3\)は素数だから、
$$
x+1\equiv0\ ({\rm mod}\ 3)\quad \lor\quad x-1\equiv0\ ({\rm mod}\ 3)
$$
です。
したがって、\(x\equiv\pm1\ ({\rm mod}\ 3)\)です。
同様にして、\(x\equiv\pm1\ ({\rm mod}\ 5)\)です。
故に答えは
$$
\begin{cases}
x\equiv\pm1\ ({\rm mod}\ 3)\\
x\equiv\pm1\ ({\rm mod}\ 5)
\end{cases}
$$
の解です。
ここで、中国式剰余定理を使います。
定理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)\\ \tag{1} \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を御覧ください。
中国式剰余定理から、
$$
\begin{cases}
x\equiv a\ ({\rm mod}\ 3)\\
x\equiv b\ ({\rm mod}\ 5)
\end{cases}
$$
の解は\(x\equiv-5a+6b\ ({\rm mod}\ 15)\)と表され、今回は\((a,b)=(-1,-1),(-1,1),(1,-1),(1,1)\)ですから\(x\equiv-1,11,-11,1\ ({\rm mod}\ 15)\)。
すなわち\(x\equiv1,4,11,14\ ({\rm mod}\ 15)\)が解となります。
確かに、法が素数でない場合は解は2個ではありませんでしたね。
皆様のコメントを下さい！
さて、新生活が始まりましたが、どうですか？
筆者は新環境になれるので必死です….
新年度でいい出会いはありましたか？
是非コメントで教えて下さい！
結
今回は、多項式の合同式に対し解の個数について解説しました。
ただし、法が素数の場合に限ります。
この場合、代数学の基本定理から導かれるような事実と似ていて、\(n\)次の合同式はその素数を法として\(n\)個より多くの解を持たないということを証明しました。
次回は、法が素数でないような場合について解説します。
乞うご期待！
乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ１週間以内にお答えします。
(難しかったらもう少しかかるかもしれませんが…)
初等整数論について、以下の書籍をオススメします！
コメントをする