次: オイラーの関数 上: 合同式 前: 一次合同方程式

合同方程式の解法

$f(x)=a_0x^n+a_1x^{n-1}+\cdots +a_n$が整数係数の多項式であるとき，合同方程式

$$f(x)\equiv 0\quad (\bmod.\ m)$$

を満たす$x(の類)$を求めることを考える．このときは，各係数$a_i$をそれと合同な数で 置き換えてもかまわない．特に$m$で割りきれる係数は消し去ってかまわない．このような消 去をおこなった後に $a_0\not \equiv 0\quad (\bmod.\ m)$なら，この合同方程式を$n$次という． 合同方程式の解法に関する三つの基本定理を証明しよう．

定理 14
     法$p$が素数であるとき, $n$次の合同方程式

$$f(x)\equiv 0\quad (\bmod.\ p)$$ (2.10)

は$n$個より多くの解を有することはない． 解の数とは(2.10)を満たす$p$を法とする剰余類の個数である． ■

証明     次数$n$に関する数学的帰納法で示す．

$n=1$のとき．一次の合同方程式

$$a_0x+a_1\equiv 0\quad (\bmod.\ p),\ (a_0,\ p)=1$$

は定理12によって, $p$を法としてただ一つの解を有する．

$n-1$次のとき解が$n-1$個以下であることが示されたとする． (2.10)が解を有するときその一つを $x\equiv a\quad (\bmod.\ p)$とする． すなわち $f(a)\equiv 0\quad (\bmod.\ p)$． このとき多項式の除法の原理(定理37)によって

$$f(x)=(x-a)f_1(x)+f(a)$$

となる$n-1$次の多項式$f_1(x)$がある． $$f(x)=\sum_{k=0}^na_kx^{n-k}$$とおくと

$$f(x)-f(a)=\sum_{k=0}^{n-1}a_k(x^{n-k}-a^{n-k})$$

なので, $f_1(x)$は整数が係数の多項式である． このとき合同方程式(2.10)は

$$(x-a)f_1(x)\equiv 0\quad (\bmod.\ p)$$

と同一の解を有する．$p$が素数であるからこの合同式は$(x-a)$または$f_1(x)$が$p$ で割り切れるときにかぎって成り立つ． ゆえに $x\equiv a\quad (\bmod.\ p)$以外の解は$n-1$次の合同方程式

$$f_1(x)\equiv 0\quad (\bmod.\ p)$$

の解でなければならない．帰納法の仮定によりこの解は$n-1$個以下である．

よって(2.10)の解は$n$個以下である．□

さて一般の合同方程式

$$f(x)\equiv 0\quad (\bmod.\ m)$$

は，$m$が素数の場合に解ければ， $m$を素因数分解して各因子を法とする方程式の解から 具体的に構成することが出来る．

それを二段階に分けて示そう．

まず，$m$が素数$p$のべきつまり$m=p^e$のときの解は, $m=p$のときの解から帰納的に構成することが出来ることを示す． そのために，$m=p^e$の解から$m=p^{e+1}$のときの解が構成できることを示す(定理15)． この定理によって，$p$のときから順次解を構成してゆくことによって，$m=p^e$のときの解が構成できる．

次に，$m$が $m=p^eq^f\cdots$と因数分解されるときの解は, $m=p^e,\ m=q^f,\ \cdots$のときの解から構成することが出来ることを示す(定理16)．

定理 15
     $e$を自然数，$p$を素数とする．合同方程式

$$f(x)\equiv 0\quad (\bmod.\ p^{e+1})$$ (2.11)

の解は

$$f(x)\equiv 0\quad (\bmod.\ p^e)$$ (2.12)

の解から構成することが出来る．

証明     (2.11)の解は法を$p^e$で考えることにより(2.12)を満たす． よって$x$が(2.11)の解であるために， (2.12)の解$x_0$を用いて

$$x=x_0+p^ey\quad$$ (2.13)

と表されることが必要である．

逆に方程式(2.12)の各解$x_0$に対し(2.13)の形の数$x$が 方程式(2.11)の解となるように$y$をとることができるか否かを判断し， 可能ならそれを求めることができる．

一般に整数係数の整式$f(x)$に対して

$$f(x+y)=f(x)+yf'(x)+\cdots+y^k\dfrac{f^{(k)}(x)}{k!}+\cdots +y^n\dfrac{f^{(n)}(x)}{n!}$$

と展開され，さらに各 $\dfrac{f^{(k)}(x)}{k!}$は$x$の$n-k$次の整数係数の整式で あることに注意する．

この$x$に$x_0$を，$y$に$p^ey$を代入することにより

$$f(x)=f(x_0+p^ey)=f(x_0)+p^eyf'(x_0)+p^{2e}y^2\dfrac{f''(x_0)}{2!}+\cdots$$

を得る． 上の注意から各$f'(x_0)$, $\dfrac{f''(x_0)}{2!}\ \cdots$は整数である． ゆえにこの展開式の第3項以下は$p^{e+1}$で割りきれる．

この結果合同方程式 $f(x)\equiv 0\quad (\bmod.\ p^{e+1})$は

$$f(x_0)+p^eyf'(x_0)\equiv 0\quad (\bmod.\ p^{e+1})$$

と同値である．$f(x_0)$は$p^e$で割り切れるので

$$\dfrac{f(x_0)}{p^e}+yf'(x_0)\equiv 0\quad (\bmod.\ p)$$ (2.14)

ここで二つの場合を区別する．

(1)     $f'(x_0)\not\equiv 0\quad (\bmod.\ p)$のとき． このときは(2.14)は$p$を法としてただ一つの解をもつ．それを $y_0\ (\bmod.\ p)$とする．

$$x\equiv x_0+p^ey_0\quad (\bmod.\ p^{e+1})$$

は(2.11)の解である．

(2)     $f'(x_0)\equiv 0\quad (\bmod.\ p)$のとき． このときは(2.14)は $\dfrac{f(x_0)}{p^e}$がさらに$p$で割り切れなければ解がない． $\dfrac{f(x_0)}{p^e}$が$p$で割り切れるなら$p$の剰余系の任意の$y$が解になる．つまり

$$x_0,\ x_0+p^e,\ x_0+2p^e,\ \cdots,\ x_0+(p-1)p^e \quad \quad (\bmod.\ p^{e+1})$$

が(2.11)を満たす． すなわち $f'(x_0)\equiv 0\quad (\bmod.\ p)$となる(2.12)の解$x_0$に対して， (2.13)の形の数$x$は， $f(x_0)\not\equiv 0\quad (\bmod.\ p^{e+1})$なら$y$によらず(2.11)の解でなく， $f(x_0)\equiv 0\quad (\bmod.\ p^{e+1})$なら(2.11)の$p^{e+1}$を法とする$p$個の解を与える． □

例 2.1.3        $p\ne 2$が素数で, $a$は$p$で割り切れないとする．そのとき

$$x^2\equiv a\quad (\bmod.\ p)$$

に解があるときは，その解は二つある．それを$\pm x_0$とする．

$$x_0\not \equiv 0\quad (\bmod.\ p),\ x_0\not \equiv -x_0\quad (\bmod.\ p)$$

この場合には, $f(x)=x^2-a,\ f'(x)=2x$である．ゆえに

$$f'(\pm x_0)=\pm 2x_0\not\equiv 0\quad (\bmod.\ p)$$

これは上定理の(1)の場合である．ゆえに

$$x^2\equiv a\quad (\bmod.\ p^e)$$

には二つの解がある．

例えば，

$$x^2\equiv 2\quad (\bmod.\ 7)$$

の解は $x_0\equiv \pm 3$である．これから

$$x^2\equiv 2\quad (\bmod.\ 49)$$

の解を求めてみよう．そのために$x=3+7y$とおく．

$$\begin{eqnarray*} &&(3+7y)^2\equiv 2\quad (\bmod.\ 49)\\ から&&9+42y\equi... ...\ 49)\\ 他の解は&&x\equiv -10\equiv 39\quad (\bmod.\ 49) \end{eqnarray*}$$

定理 16
     法$m$を素数べきに因数分解して

$$m=p^eq^f\cdots$$

とするとき，

$$f(x) 0\quad (\bmod.\ p^e)$$ ≡ (2.15)

$$f(x) 0\quad (\bmod.\ q^f)$$ ≡ (2.16)

がそれぞれ $l,\ l',\ \cdots$個の解をもつとすれば，

$$f(x)\equiv 0\quad (\bmod.\ m)$$ (2.17)

は$ll'\cdots$個の解をもつ．それは

$$x \alpha\quad (\bmod.\ p^e)$$ ≡

$$x \beta\quad (\bmod.\ q^f)$$ ≡ (2.18)

から求められる．ここで $\alpha,\ \beta,\ \cdots$はそれぞれ $p^e,\ q^f,\ \cdots$ を法としての$f(x)\equiv 0$の任意の解の一組である．■

証明     $x$が(2.17)の解ならば(2.15)，(2.16)の解である． したがって(2.18)を満たす．

逆に(2.18)を満たす$x$は，(2.15)，(2.16)を満たすから， (2.17)を満たす．□

例 2.1.4  

$$\begin{array}{l} x^2\equiv 1\quad (\bmod.\ 3)\\ x^2\equiv 1\quad (\bmod.\ 4) \end{array}$$

の解はそれぞれ二つある．それらを $\alpha\equiv \pm1\quad (\bmod.\ 3)$と $\beta\equiv \pm1\quad (\bmod.\ 4)$とする．

$$x^2\equiv 1\quad (\bmod.\ 12)$$

は四つの解をもつ．それらは，

$$\left. \begin{array}{l} x\equiv 1\\ x\equiv 1 \end... ...\begin{array}{l} (\bmod.\ 3)\\ (\bmod.\ 4) \end{array}$$

から求められる．

$$∴\quad x\equiv 1,\ x\equiv 7,\ x\equiv 5,\ x\equiv 11\quad (\bmod.\ 12)$$

次: オイラーの関数 上: 合同式 前: 一次合同方程式