次: 合同方程式の解法 上: 合同式 前: 合同式

一次合同方程式

$f(x)$が整数係数の整式であるとき，

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

を合同方程式と呼ぶ． $x_0$をこの合同式を満たす一つの整数とし, $x_1\equiv x_0$とすれば，定理10より

$$f(x_1)\equiv f(x_0)\equiv 0 \quad (\bmod.\ m)$$

である．すなわち$m$を法として$x_0$と合同な数はすべてこの合同方程式の解である．

以下，合同方程式の解とはその合同方程式を満たす$m$を法とする剰余類のこととする． 合同方程式を解くとは，それを満たす剰余類を求めることとする． 簡単に「合同式を解く」ともいう．

合同方程式のすべての解を求めようとすれば, $x=0,\ 1,\ \cdots,\ m-1$の$m$個の値を代入してみればよい．つまりどんな合同方程式の解も，有限回の計算で求めることが出来る． その意味で解を有理整数にかぎるなら，必ず解ける． そのうえで，解の存在とより少ない手順で解を構成する方法を調べよう．

まず一次合同方程式について考える．

定理 12
     一次合同方程式

$$ax\equiv b\quad (\bmod.\ m)$$

は$(a,\ m)=1$のときただ一つの解がある． $(a,\ m)=d>1$のときは，$b$が$d$で割り切れるときにかぎって解がある． その解の個数は$d$である．■

証明      $(a,\ m)=1$のとき．

$$\{x_1,\ x_2,\ \cdots,\ x_m\}$$

を$m$を法とする剰余系とする．このとき

$$\{ax_1,\ ax_2,\ \cdots,\ ax_m\}$$

もまた$m$を法とする剰余系である．なぜならもし

$$ax_i\equiv ax_j\quad (\bmod.\ m)$$

なら, $a$が$m$と互いに素であることから

$$x_i\equiv x_j\quad (\bmod.\ m)$$

となる．それは$i=j$のときにかぎるからである． ゆえに任意の$b$に対して $\{x_1,\ x_2,\ \cdots,\ x_m\}$のなかのただ一つ

$$ax_i\equiv b\quad (\bmod.\ m)$$

となる$x_i$が存在する．

$(a,\ m)=d>1$のとき．

$$ax\equiv b\quad (\bmod.\ m)$$ (2.3)

に解があるとすると, $ax-b=mN\ (N\ は整数)$と表される．ゆえに$b=ax-mN$は $d=(a,\ m)$で割りきれる．そこで

$$a=da',\ m=dm',\ b=db'$$

とおく．(2.3)は定理11 より

$$a'x\equiv b'\quad (\bmod\ m')$$ (2.4)

と同値である．ここで$a'$と$m'$は互いに素であるから(2.4)を満たす$x$は $m'$を法とする一つの類である．それを $x\equiv x_0\quad (\bmod.\ m')$とする． (2.4)の解は

$$x=x_0+m't\quad t\ は任意の整数$$ (2.5)

によって与えられる．$t_1$と$t_2$に対する$x$が$m$を法として合同になるのは

$$m'(t_1-t_2)\equiv 0\quad (\bmod.\ m)$$

つまり

$$t_1-t_2\equiv 0\quad (\bmod.\ d)$$

となるときにかぎる． したがって，(2.5)で$t$に対して，$d$を法とする剰余系 $\{0,\ 1,\ \cdots,\ d-1\}$ の値を与えるとき, $m$を法とする(2.3)のすべての解が得られる．すなわちその 解の個数は$d$である．□

このように合同方程式(2.3)を解くことは，一次不定方程式

$$ax+my=b$$

の整数解を求めることと同じである．

定理 13
     $m_1,\ m_2,\ \cdots,\ m_k$が二つずつ互いに素で, $a_1,\ a_2,\ \cdots,\ a_k$は 任意の整数であるとする．

$$x a_1\quad (\bmod.\ m_1)$$ ≡

$$x a_2\quad (\bmod.\ m_2)$$ ≡

$$x a_k\quad (\bmod.\ m_k)$$ ≡

を満たす$x$は $M=m_1m_2\cdots m_k$を法としてただ一つ存在する．■

証明     第一の合同式を満たす$x$は

$$x=a_1+m_1t$$ (2.7)

と書ける．これが第二の合同式も満たすのは

$$a_1+m_1t\equiv a_2\quad (\bmod.\ m_2)$$

すなわち

$$m_1t\equiv a_2-a_1\quad (\bmod.\ m_2)$$

のときである．ところが, $m_1$と$m_2$は互いに素なのでこれには

$$t=t_0+m_2s$$

のように$m_2$を法とするただ一つの類が解として存在する．これを(2.7)に代入して

$$x=a_1+m_1t_0+m_1m_2s$$

つまり

$$x\equiv a_1+m_1t_0\quad (\bmod.\ m_1m_2)$$

この一つの合同式を(2.6)の最初の二つの合同式に置き換えてよい． 同様の操作を繰りかえすことができる．ついには

$$x\equiv x_0\quad (\bmod.\ M)$$

を得る．□

この定理は 中国の剰余定理(Chinese Remainder Teorem) と呼ばれる． 中国古代(一世紀頃)の書『孫子算経』の中に,「3で割れば2余り，5で割れば3余り， 7で割れば2余るような数は何か」という問いと解の求め方が述べられている． この種の問題が孫子以降の中国の算術の書に見られる．下って16世紀の終わり頃の 『算法統宗』(程大位)にはこの孫子の問いに対する解の求め方が歌で述べられている． このような歴史があるのでこの定理が上のように呼ばれるのである．

ここでガウス(Gauss) による対称性を用いたより美しい別証を紹介する．

ガウスの別証明

$M=m_1m_2\cdots m_k$に対し

$$M=m_1M_1=m_2M_2=\cdots=m_kM_k$$ (2.8)

とおく．$M_n$と$m_n$は互いに素なので

$$M_nt_n\equiv 1\quad (\bmod.\ m_n)\quad (n=1,\ 2,\ \cdots,\ k)$$ (2.9)

となる解 $t_n\ (n=1,\ 2,\ \cdots,\ k)$が存在する． このとき(2.6)の解は

$$x\equiv a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k\quad (\bmod.\ M)$$

である． 実際，(2.9)から

$$a_nM_nt_n\equiv a_n\quad (\bmod.\ m_n)$$

で, $M_1,\ \cdots,\ M_k$のうち$M_n$以外はすべて$m_n$で割りきれるので，

$$x\equiv a_n\quad (\bmod.\ m_n) (n=1,\ 2,\ \cdots,\ k)$$

である．

唯一の解であることは, $x_1$と$x_2$がともに(2.6)を満たせば

$$x_1\equiv x_2\quad (\bmod.\ m_n) (n=1,\ 2,\ \cdots,\ k)$$

なので, $m_1,\ m_2,\ \cdots,\ m_k$の最小公倍数$M$に関して

$$x_1\equiv x_2\quad (\bmod.\ M)$$

となるからである．□

 

次: 合同方程式の解法 上: 合同式 前: 合同式