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

本記事の内容
サラッと復習(読み飛ばしてもOK)
法が合成数の場合(素数でない場合)は？
実際に計算してみる
1. 例1.　定理0.の1.の場合
2. 例2.　定理0.の2.の場合
皆様のコメントを下さい！
結

本記事の内容

本記事は、多項式の合同式(法が合成数の場合)の解の個数と存在条件について解説する記事です。

本記事を読むに当たり、法が合成数である場合について知っている必要があるため、以下の記事も合わせてご覧ください。

サラッと復習(読み飛ばしても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.

$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$を法として互いに合同でないものを数えていう。

法が合成数の場合(素数でない場合)は？

では、本題です。

結論(主張の明示)

結論としては、次が成り立ちます。

定理0.

整数係数多項式の合同式$f(x)\equiv0\ ({\rm mod}\ p^n)$の解は$f(x)\equiv0\ ({\rm mod}\ p)$の解から導かれる。

$f^\prime(x_0)\not\equiv\ ({\rm mod}\ p)$ならば、$f(x)\equiv0\ ({\rm mod}\ p^n)$の解の中に、$x\equiv x_0\ ({\rm mod}\ p)$なるものが、$\ ({\rm mod}\ p^n)$に関してただ1つ存在する。
$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$の場合には、$f(x)\equiv0\ ({\rm mod}\ p^n)$が$x\equiv x_0\ ({\rm mod}\ p^n)$なる解を持つとき、その解から$f(x)\equiv0\ ({\rm mod}\ p^{n+1})$の$p$個の解が派生することもあり、あるいは、また$f(x)\equiv0\ ({\rm mod}\ p^{n+1})$は$x\equiv x_0\ ({\rm mod}\ p^{n})$なる解を持たないこともある。

「おい、ちょっと待ってくれ。“法が合成数の場合”じゃないのか？これだと素数のべき乗ではないか」と疑問に思われる方もいらっしゃると思います。

実は、法が合成数の場合は結局の所、法が素数のベキ乗の場合を考えれば十分なのです。
なぜなのか？を説明しましょう。

なぜ素数のベキ乗の場合を考えるだけで十分なのか？

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

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

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

$m=p_1^{a_1}p_1^{a_2}\cdots p_k^{a_k}$　$(p_1<p_2<\cdots<p_k$は素数)

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

定理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.の証明

まず、素数$p$を法とするとき、
$$
f(x)\equiv0\ ({\rm mod}\ p)\tag{3}
$$
(ただし、$f(x)$は整数係数多項式)の解が求められたとして、それから$p$の任意のベキを法とするときの解を求める方法について述べます。

$$
f(x)\equiv0\ ({\rm mod}\ p^2)\tag{4}
$$
という合同式の解は(3)の解でもあります。
実際、(4)から
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ f(x)=k\cdot p^2
$$
ですので、
$$
f(x)=\left( kp\right)\cdot p
$$
を満たすため、$f(x)-0=f(x)$が$p$の倍数だからです。

さて、$x_0$を(3)の解としましょう。
すなわち$x_0\in\mathbb{Z}$は
$$
f(x_0)\equiv0\ ({\rm mod}\ p)
$$
を満たすとしましょう。
すると、(4)の解$x$は、$y\in\mathbb{Z}$を用いて
$$
x=x_0+py\tag{5}
$$
という形をしていなければなりません。
これを(4)に代入すると、
$$
f(x)=f(x_0+py)\equiv0\ ({\rm mod}\ p^2)
$$
となります。

ここで、$f(x)$が多項式であることから、$f(x_0+py)$(変数は$y$)はテイラー展開が可能です(１変数実数値関数の微分編その11)。
$f(x_0+py)$を$y=0$周りでテイラー展開すると、
\begin{eqnarray}
f(x_0+py)=f(x_0)+pyf^\prime(x_0)+p^2y^2\frac{f^{\prime\prime}(x_0)}{2}+\cdots
\end{eqnarray}
となるため、
$$
f(x_0)+pyf^\prime(x_0)+p^2y^2\frac{f^{\prime\prime}(x_0)}{2}+\cdots\equiv0\ ({\rm mod}\ p^2)
$$
となります。

さて、そもそも$f(x)$は整数係数の多項式でした。
故に、$\displaystyle f^\prime(x),\ \frac{f^{\prime\prime}(x_0)}{2},\ \frac{f^{\prime\prime\prime}(x_0)}{3!},\ \cdots$も整数係数の多項式です。

したがって、$\displaystyle f^\prime(x_0),\ \frac{f^{\prime\prime}(x_0)}{2},\ \frac{f^{\prime\prime\prime}(x_0)}{3!},\ \cdots$は整数です。

故に、上記の展開の式の第3項より先の項はすべて$p^2$で割り切れるため、(5)を満たしている整数で(4)も満たすような整数を求めることは
$$
f(x_0)+pyf^\prime(x_0)\equiv0\ ({\rm mod}\ p^2)
$$
から$y$を求めることに帰着するわけです。
(3)から、$f(x_0)$は$p$で割り切れる為、上記の式を変形すると、
$$
\frac{f(x_0)}{p}+yf^\prime(x_0)\equiv0\ ({\rm mod}\ p)\tag{6}
$$
です。

さて、ここで以下の2つの場合に分けます。

$f^\prime(x_0)\not\equiv0\ ({\rm mod}\ p)$である場合
$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$である場合

(6)に対して、なぜこの2つの場合に分けるのか？ということを説明します。
結論としては、以下が成り立つからです。

定理5.

一次合同式 $$ ax\equiv b\ ({\rm mod}\ m) $$ は$\gcd(a,m)=1$なるときは、1つの解を持つ。$\gcd(a,m)=d>1$であるときは、$b$が$d$で割り切れるときに限って解を持つ。その解の数は$d$である。ただし、解の数は$m$を法としての類の関してである。

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

定理5.において、今の状況は
$$
a=f^\prime(x_0),\quad x=y,\quad b=\frac{f(x_0)}{p},\quad m=p
$$
です。
したがって、(6)の解は

$\gcd(a,m)=\gcd\left(f^\prime(x_0),p\right)=1$のときは1つの解を持つ。
$\gcd(a,m)=\gcd\left(f^\prime(x_0),p\right)=d>1$のときは、$\displaystyle b=\frac{f(x_0)}{p}$が$\displaystyle d=\gcd\left(f^\prime(x_0),p\right)$で割り切れる場合にのみ解を持ち、その個数は$d$個。

という条件下で存在します。
今、$p$は素数ですので、$\displaystyle\gcd\left(f^\prime(x_0),p\right)=1$であることと、$f^\prime(x_0)$が$p$で割り切れないことは同値です。
以上から

$f^\prime(x_0)\not\equiv0\ ({\rm mod}\ p)$である場合
$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$である場合

の2つの場合に分けるのです。

$f^\prime(x_0)\not\equiv0\ ({\rm mod}\ p)$である場合
このとき、定理5.から(6)は唯一つの解を持ちます。
それを$y_0\in\mathbb{Z}$としましょう。
すなわち、
$$
y\equiv y_0\ ({\rm mod}\ p)
$$
とします。
すなわち
$$
(\exists r\in\mathbb{Z})\ {\rm s.t.}\ y-y_0=pr
$$
です。
故に、$py-py_0=p^2r$だから、$py=py_0+p^2r$を得ます。
これを(5)に代入すれば、
$$
x=x_0+py=x_0+py_0+p^2r\Longleftrightarrow x-\left(x_0+py_0 \right)=p^2r
$$
となるため、
$$
x\equiv x_0+py_0\ ({\rm mod}\ p^2)\tag{7}
$$
となります。
すなわち、(3)の解$x\equiv x_0\ ({\rm mod}\ p)$から(4)の1つの解(7)を得たのです。
$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$である場合
これも定理5.を使います。
定理5.から、$\displaystyle\frac{f(x_0)}{p}$が$p$で割り切れないならば、解は存在しません。

もし、$\displaystyle\frac{f(x_0)}{p}$が$p$で割り切れるならば、任意の$y\in\mathbb{Z}$に対して(6)が成り立ちます。
実際、$\displaystyle\frac{f(x_0)}{p}$が$p$で割り切れるとすると、
$$
(\exists s\in\mathbb{Z})\ {\rm s.t.}\ \frac{f(x_0)}{p}=sp
$$
です。
故に、(6)は
$$
sp+y\cdot f^\prime(x_0)\equiv 0\ ({\rm mod}\ p)
$$
となり、これを満たす$y\in\mathbb{Z}$を知りたい、という状況になります。
そもそも(6)は
$$
(\exists k\in\mathbb{Z})\ {\rm s.t.}\ \frac{f(x_0)}{p}+yf^\prime(x_0)=kp
$$
ということでしたので、これを基に先の式を変形すれば、
$$
sp+y\cdot f^\prime(x_0)=kp
$$
となります。
今、$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$という状況を考えているため、
$$
(\exists t\in\mathbb{Z})\ {\rm s.t.}\ f^\prime(x_0)=tp
$$
であるから、
$$
y\cdot tp=(k-s)p
$$
を満たすわけです。
これはたとえ$y\in\mathbb{Z}$がどんな整数であったとしても成り立ちます。
もっと平たく言えば、
$$
sp+y\cdot tp\equiv0\ ({\rm mod}\ p)
$$
は$y\in\mathbb{Z}$が何であっても成り立つということです。

さて、以上を踏まえて、(5)に立ち返ってみましょう。
すると、$y\in\mathbb{Z}$は何でも良いわけですので、
\begin{eqnarray}
x=x_0+p\cdot0,\ x_0+p\cdot2,\cdots,x_0+p\cdots (p-1),\cdots
\end{eqnarray}
の全てが(4)を満たしている、ということになります。
この$y\in\mathbb{Z}$を$p$を法として考えれば
$$
x\equiv x_0,\ x_0+p,\ x_0+2p,\cdots,x_0+(p-1)p\ ({\rm mod}\ p^2)
$$
が(4)を満たすということになります。

すなわち、(5)の形の数$x$は1つも(4)の解を与えないか、あるいは$p^2$を法として、$p$個の解を与えるかのいずれか一方が成り立つということになります。

同様にして、(3)の代わりに
$$
f(x)\equiv 0\ ({\rm mod}\ p^n)\quad (n\in\mathbb{N})\tag{8}
$$
を考察すれば、(8)の1つの解を$x_0$とするとき、
$$
x=x_0+p^ny\tag{9}
$$
の形の数で、
$$
f(x)\equiv0\ ({\rm mod}\ p^{n+1})\tag{10}
$$
を満たす数は、

$f^\prime(x_0)\not\equiv0\ ({\rm mod}\ p)$の場合には、$p^{n+1}$を法として唯一である。
$f^\prime(x_0)\equiv0\ ({\rm mod}\ p)$の場合には、$p^{n+1}$を法として1つも存在しないか、または$p$個存在する。
ただし、$p$個の解が存在するのは$f(x_0)\equiv0\ ({\rm mod}\ p^{n+1})$で、(9)において$y$を任意に取ったとしても、それが(10)を満たすときである。

ということになります。

定理0.の証明終わり

実際に計算してみる

実例で計算してみます。

例1.　定理0.の1.の場合

$x^2\equiv2\ ({\rm mod}\ 49)$の解を求めてみます。

まずは、$49=7^2$と書けるため、$x^2\equiv2\ ({\rm mod}\ 7)$の解を$x\equiv\pm3\ ({\rm mod}\ 7)$と求めます。

$x^2\equiv2\ ({\rm mod}\ 49)$の解を求めるために$x=3+7y$とおけば、
$$
(3+7y)^2\equiv2\ ({\rm mod}\ 49)
$$
となるため、
$$
9+42y\equiv2\ ({\rm mod}\ 49)
$$
です。
すなわち、
$$
6u\equiv-1\ ({\rm mod}\ 7)
$$
であるから、
$$
y\equiv1\ ({\rm mod}\ 7)
$$
です。
したがって、$x\equiv10\ ({\rm mod}\ 49)$となり、今1つの解は$x\equiv-10\equiv39\ ({\rm mod}\ 49)$となります。

例2.　定理0.の2.の場合

これは初等整数論において重要な事実です。
素数の中で$2$が別格の素数で有理整数論における特異点ともいうべきものであることをある種表しています。

命題6.

$a\equiv1\ ({\rm mod}\ 8)$なるとき、 $$ x^2\equiv a\ ({\rm mod}\ 2^n)\quad (n\geq3) $$ の解は4つである。その1つを$x_0$とすれば、解は $$ \pm x_0,\ \pm x_0+2^{n-1} $$ である。

命題6.の証明

$x=1+2y$を奇数としましょう。
すると、$x^2=1+4y(y+1)$で、$y$または$y+1$は偶数ですから、$x^2\equiv1\ ({\rm mod}\ 8)$です。

故に、$a\equiv1\ ({\rm mod}\ 8)$は$a$が奇数であるときに命題の合同式が解を持つための必要十分条件です。

$n=3$であれば、この条件下において、解は$x\equiv1,3,5,7\ ({\rm mod}\ 8)$です。
あるいは$x\equiv\p,1,\ \pm1+4\ ({\rm mod}\ 8)$です。

数学的帰納法で証明します。
ある指数$n\in\mathbb{N}$に対して命題が成り立つとすると、指数$n+1$のときの解は
$$
\pm x_0+2^ny\quad \lor\quad \left( \pm x_0+2^{n+1}\right)+2^ny\ ({\rm mod}\ 2^{n+1})
$$
でなければなりません。
その$y$($y=0$または$1$)は
$$
\left( \pm x_0+2^ny\right)^2\equiv a\ ({\rm mod}\ 2^{n+1})\tag{11}
$$
あるいは
$$
\left\{\left( \pm x_0+2^{n-1}+2^ny\right) \right\}^2\equiv a\ ({\rm mod}\ 2^{n+1})\tag{12}
$$
から求められます。

仮定から、$x_0^2-a=2^nt$という$t\in\mathbb{Z}$が存在します。
故に(11)から
$$
2^nt\equiv0\ ({\rm mod}\ 2^{n+1})
$$
です。
$t$が奇数であれば、これは解が存在しません。
一方で、$t$が偶数であれば、$y\in\mathbb{Z}$は任意です。
故に$\ ({\rm mod}\ 2^{n+1})$に関しては、$y=0,1$として$\pm x_0$および$\pm x_0+2^n$が解です。
すなわち、$\ ({\rm mod}\ 2^{n})$に関する解$\om x_0$から、$\ ({\rm mod}\ 2^{n+1})$に関する解が得られないか、あるいは4つの解が得られます。

次に、
\begin{eqnarray}
\left( \pm x_0+2^{n-1}+2^n\right)^2&\equiv& x_0^2\pm 2^nx_0+2^{2n-2}\\
&\equiv&x_0^2+2^n\ ({\rm mod}\ 2^{n+1})
\end{eqnarray}
(ただし、$x_0$は奇数、また$2n-2\geq n+1$だから)です。
故に(12)から
$$
2^nt+2^n\equiv0\ ({\rm mod}\ 2^{n+1})
$$
です。

今度は$t$がぐうすうであれば、これに解は存在しませんが、$t$が奇数であれば、$y$は任意です。
故に$\ ({\rm mod}\ 2^{n+1})$に関して
$$
\pm\left( x_0+2^{n-1}\right),\quad \pm\left( x_0+2^{n-1}\right)+2^n
$$
の4つの解が得られました。

命題6.の証明終わり

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

さてさて、GWが近づいてきました。
皆様はどこかお出かけですか？それとも家で数学ですか？

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

結

今回は、多項式の合同式(法が合成数の場合)の解の個数と存在条件について解説しました。

法が合成数の場合は結局の所、法が素数の場合に帰着されます。
しかし、どういうときに解が存在するのか、存在するなら何個か？ということは一筋縄では行きません(少々複雑という意味で)。

次回は合同式の連立方程式について解説します。

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

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

コメントをする

Warning: Undefined variable $req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 32

Warning: Undefined variable $commenter in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Trying to access array offset on value of type null in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34

Warning: Undefined variable $aria_req in /home/nori9901/for-spring.com/public_html/wp-content/themes/cocoon-child-master/functions.php on line 34