初 等 整 数 論 講 義 第 $2$ 版

$\blacktriangleleft$ $\S\ 5.$ 合同式  $\S\ 7.$ 合同式解法の概論 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ



第 $1$ 章 初 等 整 数 論


 $\S\ 6.$ 一 次 合 同 式

 $\boldsymbol{1.}$ $f\left(x\right)$ が整係数の多項式であるとき,合同式\[f\left(x\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right)\]を満足させる未知の整数 $x$ を求めることを合同式を解くという.$x_0$ をこの合同式の一つの解とし,$x_1\equiv x_0\hphantom{m}\left(\text{mod}.\ m\right)$ とすれば\[f\left(x_1\right)\equiv f\left(x_0\right)\equiv0\hphantom{m}\left(\text{mod}.\ m\right).\hspace{5mm}\left(\cssId{eq1}{定理\ 1. 11}\right).\] すなわち $m$ を法として $x_0$ と同類なる数はすべて $\left(\ 1\ \right)$ の解である.
 故に合同式を解くとは,それを満足させる整数の類を求めることである.
 よって $\left(\ 1\ \right)$ のすべての解を求めるには,$x=0$,$1$,$2$,$\cdots\cdots$,$m-1$ なる $m$ 個の値を当てはめてみればよろしい(故にどのような合同式が与えられてあるとしても,手数さえいとわなければ,それを解くことはできるのである).
 〔定理 $\boldsymbol{1.\ 13}$〕 一次合同式\[ax\equiv b\hphantom{m}\left(\text{mod}.\ m\right)\]は $\left(a,\ m\right)=1$ なるときは,一つの解を有する.$\left(a,\ m\right)=d\gt1$ であるときは,$b$ が $d$ で割り切れるときに限って解を有する.その解の数は $d$ である.解の数は,$m$ を法としての類に関していう.
 〔〕  $\text{i}$ $)$ $\left(a,\ m\right)=1$ の場合.$x$ に $m$ を法としての剰余系\[x_1,\ x_2,\ \cdots\cdots,\ x_m\]の値を与えるときに,$ax$ の値\[ax_1,\ ax_2,\ \cdots\cdots,\ ax_m\]は,やはり $m$ を法としての剰余の一組であることは明白である.実際 $ax_h\equiv ax_k\hphantom{m}\left(\text{mod}.\ m\right)$ となるのは $a\left(x_h-x_k\right)$ が $m$ で割り切れるときに限り,仮定によって $\left(a,\ m\right)=1$ であるから,$x_h\equiv x_k\hphantom{m}\left(\text{mod}.\ m\right)$.それは $h=k$ であるときに限る.
 よって $b$ がいかなる整数であっても,$x_1$,$x_2$,$\cdots\cdots$,$x_m$ の中のただ一つによって\[ax\equiv b\hphantom{m}\left(\text{mod}.\ m\right)\]が満足させられねばならない.
 $\text{ii}$ $)$  $\left(a,\ m\right)=d\gt1$ の場合\[ax\equiv b\hphantom{m}\left(\text{mod}.\ m\right)\tag{$\ 1\ $}\]に解があるとすれば,$ax-b=my$ であるから,$b=ax-my$ は $d=\left(a,\ m\right)$ で割り切れねばならない.$b$ が $d$ で割り切れるとすれば,\[a=da^\prime,\ \ m=dm^\prime,\ \ b=db^\prime\]と置くとき,$\left(\ 1\ \right)$ は\[a^\prime x\equiv b^\prime\hphantom{m}\left(\text{mod}.\ m^\prime\right)\tag{$\ 2\ $}\]に帰する(定理 $1.\ 12$).ここでは $\left(a^\prime,\ m^\prime\right)=1$ であるから,$\left(\ 2\ \right)$ を満足させる $x$ は,$m^\prime$ を法としての一つの類である.それを $x\equiv x_0\hphantom{m}\left(\text{mod}.\ m^\prime\right)$ とすれば,$\left(\ 2\ \right)$ の解は\[x=x_0+m^\prime t\tag{$\ 3\ $}\]によって与えられる.ここで $t$ は任意の整数である.$t$ の二つの値 $t_1$,$t_2$ に関して,これらが $m$ を法として合同になるのは\[m^\prime\left(t_1-t_2\right)\]が $m$ で割り切れるとき,すなわち $t_1-t_2$ が $d$ で割り切れるときに限るから,$\left(\ 3\ \right)$ において $t$ に $0$,$1$,$2$,$\cdots\cdots$,$d-1$ なる値を与えるときに,$m$ を法としての $\left(\ 1\ \right)$ のすべての解が得られる.すなわち解の数は $d$ である.
 〔注意〕 合同式 $\left(\ 1\ \right)$ を解くことは不定方程式\[ax+my=b\]を満足させる整数 $x$ を求めることと同じである.上記の定理 $1.\ 13$ は実は定理 $1.\ 7$ と同一である.
 〔例〕 $26x\equiv1\hphantom{m}\left(\text{mod}.\ 57\right)$ を解くこと.
 〔解〕 $\left(26,\ 57\right)=1$ であるから,一つの解がある.その解を $x$ とする.
 $57=26\times2+5$ を用いるために,両辺に $2$ を掛けて\begin{alignat*}{1}52x&\equiv2\hphantom{m}\left(\text{mod}.\ 57\right).\\[1mm]\therefore\hphantom{m}-5x&\equiv2\hphantom{m}\left(\text{mod}.\ 57\right).\end{alignat*} 両辺に $5$ を掛けて与えられた合同式の両辺に加えて\[x\equiv11\hphantom{m}\left(\text{mod}.\ 57\right)\]を得る.
 すなわち解があれば,それは $x\equiv11\hphantom{m}\left(\text{mod}.\ 57\right)$ でなければならないが,解があることがわかっているから,これがすなわち求める解である.
 〔検算〕$26\times11=286=57\times5+1$.
 このようにして $26x-57y=1$ を解くまでもなく,$x=11$ を得たのである.実際は上記のようにして $26x-57y=1$ の解を求めるのが近道である.すなわち,一つの解が $x=11$,$y=5$ であるから,一般の解は $x=11+57t$,$y=5+26t$ である.
 読者は自ら任意の合同式を提出して解いてみるとよろしい.このような練習が整数論を理解するのに必要である.


 $\boldsymbol{2.}$ 次の定理も後に引用されるものである(補遺 $5$ 参照).
 〔定理 $\boldsymbol{1.\ 14}$〕 $m_1$,$m_2$,$\cdots\cdots$,$m_k$ が二つずつ互いに素で,$a_1$,$a_2$,$\cdots\cdots$,$a_k$ は任意の整数であるとき\[\begin{alignat*}{1}x&\equiv a_1\hphantom{m}\left(\text{mod}.\ m_1\right)\\[1mm]x&\equiv a_2\hphantom{m}\left(\text{mod}.\ m_2\right)\\[1mm]&{\small\cdots\cdots\cdots\cdots\cdots\cdots\cdots}\\[1mm]x&\equiv a_k\hphantom{m}\left(\text{mod}.\ m_k\right)\end{alignat*}\tag{$\ 4\ $}\]を満足させる $x$ は $M=m_1m_2\cdots\cdots m_k$ を法としてただ一つ存在する.
 〔〕 第一の合同式を満足させる $x$ は\[x=a_1+m_1t\tag{$\ 5\ $}\]である.それが第二の合同式をも満足させるのは\[a_1+m_1t\equiv a_2\hphantom{m}\left(\text{mod}.\ m_2\right),\]すなわち\[m_1t\equiv a_2-a_1\hphantom{m}\left(\text{mod}.\ m_2\right)\tag{$\ 6\ $}\]であるときである.仮定によって $\left(m_1,\ m_2\right)=1$ であるから, $\left(\ 6\ \right)$ の解は\[t=t_0+m_2s\]のような,$m_2$ を法としての一類である.これを $\left(\ 5\ \right)$ に代入すれば,\[x=a_1+m_1t_0+m_1m_2s,\]すなわち\[x\equiv a_1+m_1t_0\hphantom{m}\left(\text{mod}.\ m_1m_2\right)\]である.この一つの合同式で $\left(\ 4\ \right)$ の最初の二つの合同式を置き換えてよい.よってこれを $\left(\ 4\ \right)$ の第三の合同式と組み合わせて同様の方法を行なうことができる.次第にこのようにして,ついに $\left(\ 4\ \right)$ と等値な\[x\equiv x_0\hphantom{m}\left(\text{mod}.\ M\right)\]を得る.
 あるいはまた Gauss が Disquisitiones に述べたように,すべての $\text{mod}.$ を対称的に取り扱う方法もある.
 前のように\[M=m_1m_2\cdots\cdots m_k\]とし,\[M=m_1M_1=m_2M_2=\cdots\cdots=m_kM_k\tag{$\ 7\ $}\]と置いて\[M_nt_n\equiv1\hphantom{m}\left(\text{mod}.\ m_n\right)\tag{$\ 8\ $}\\[2mm]\left(n=1,\ 2,\ \cdots\cdots,\ k\right)\]なる $t_n$ を求める.
 しからば $\left(\ 4\ \right)$ の解は\[x\equiv a_1M_1t_1+a_2M_2t_2+\cdots\cdots+a_kM_kt_k\hphantom{m}\left(\text{mod}.\ M\right).\] 実際,$\left(\ 8\ \right)$ によって,右辺の第一項 $a_1M_1t_1\equiv a_1\hphantom{m}\left(\text{mod}.\ m_1\right)$ で,第二項以下は $\left(\ 7\ \right)$ によって $M_2$,$\cdots\cdots$,$M_k$ が $m_1$ で割り切れるから,$x\equiv a_1\hphantom{m}\left(\text{mod}.\ m_1\right)$.$m_2$,$\cdots\cdots$,$m_k$ に関しても同様であるから,$\left(\ 4\ \right)$ は満足させられる.
 $\left(\ 4\ \right)$ の解が $\text{mod}.\ M$ に関してただ一つに限ることは初めから明白である.$x$,$x^\prime$ を $\left(\ 4\ \right)$ の解とすれば $x\equiv x^\prime\hphantom{m}\text{mod}.\ m_1$,$\cdots\cdots$,$\text{mod}.\ m_k$ だから,$x-x^\prime$ は $m_1$,$m_2$,$\cdots\cdots$,$m_k$ で割り切れ,したがってそれらの最小公倍数である $M$ で割り切れる.すなわち $x\equiv x^\prime\hphantom{m}\left(\text{mod}.\ M\right)$.

 上記の解では,$M_1$,$M_2$,$\cdots\cdots$,$M_k$,したがって $t_1$,$t_2$,$\cdots\cdots$,$t_k$ が $a_1$,$a_2$,$\cdots\cdots$,$a_k$ に関係なく定められる.$M_nt_n$ はすなわち $a_1$,$\cdots\cdots$,$a_k$ の中で $a_n$ だけが $1$ で,その他は $0$ なる場合における $\left(\ 4\ \right)$ の解であって,それらの一次的結合として,任意の $a$ に関する $\left(\ 4\ \right)$ の解が得られるのである.
 〔例〕$m_1=3$,$m_2=5$,$m_3=7$ とすれば $M=105$,  
$\rule{0mm}{5.7mm}M_1=35$,$M_2=21$,$M_3=15,$
$\rule{0mm}{5.7mm}t_1=-1$,$t_2=1$,$t_3=1,$
$\rule{0mm}{5.7mm}M_1t_1=-35$,$M_2t_2=21$,$M_3t_3=15.$
 故に\[x\equiv a_1\hphantom{m}\left(\text{mod}.\ 3\right),\ \equiv a_2\hphantom{m}\left(\text{mod}.\ 5\right),\ \equiv a_3\hphantom{m}\left(\text{mod}.\ 7\right)\]の解は\[x\equiv-35a_1+21a_2+15a_3\hphantom{m}\left(\text{mod}.\ 105\right).\]例えば,$3$ で割れば $1$ が残り,$5$ で割れば $2$ が残り,$7$ で割れば $3$ が残るような数 $x$ は\[x=-35\hspace{0.7mm}\cdotp1+21\hspace{0.7mm}\cdotp2+15\hspace{0.7mm}\cdotp3=52\]あるいは一般に\[x\equiv52\hphantom{m}\left(\text{mod}.\ 105\right).\] 〔注意〕 上記の解法を部分分数への分解に応用することができる.既約分数 $x/M$ の分母 $M$ を二つずつ互いに素である因数 $m_1$,$m_2$,$\cdots\cdots$,$m_k$ に(例えば素数巾に)分解し,$x$ を $m_1$,$m_2$,$\cdots\cdots$,$m_k$ で割った剰余を $a_1$,$a_2$,$\cdots\cdots$,$a_k$ とすれば\[x=a_1M_1t_1+a_2M_2t_2+\cdots\cdots+a_kM_kt_k+Mt\]から\[\frac{\lower{0.1em}x}{M}=\frac{a_1t_1}{m_1}+\frac{a_2t_2}{m_2}+\cdots\cdots+\frac{a_kt_k}{m_k}+t.\] 例えば上記の例では\[\frac{52}{105}=-\frac{1}{3}+\frac{2}{5}+\frac{3}{7}.\hspace{1cm}\left(t=0\right)\]よって\[\frac{52}{105}=\frac{2}{3}+\frac{2}{5}+\frac{3}{7}-1.\]

 〔問題 $\boldsymbol{1}$〕 法 $m$,$n$ の最大公約数を $d$,最小公倍数を $l$ とすれば,\[\left\{\begin{array}{l}x\equiv a\hphantom{m}\left(\text{mod}.\ m\right),\\[1mm]x\equiv b\hphantom{m}\left(\text{mod}.\ n\right).\end{array}\right.\]が解を有するために必要かつ十分な条件は $a\equiv b\hphantom{m}\left(\text{mod}.\ d\right)$ である.解があれば,$l$ を法としてただ一つである.
 〔解〕 定理 $1.\ 14$ の初めの証明のようにする.
 〔例〕$\left\{\begin{alignat*}{2}x&\equiv4&\hphantom{m}&\left(\text{mod}.\ 15\right),\\[1mm]x&\equiv10&\hphantom{m}&\left(\text{mod}.\ 21\right).\end{alignat*}\right.$  
\begin{alignat*}{2}x=4&+15t\equiv10\hphantom{m}\left(\text{mod}.\ 21\right),\ &&\ \therefore\ \ \ 15t\equiv6\hphantom{m}\left(\text{mod}.\ 21\right),\\[1mm]&\therefore\ \ \ 5t\equiv2\hphantom{m}\left(\text{mod}.\ 7\right),\ &&\ \therefore\ \ \ t\equiv6\hphantom{m}\left(\text{mod}.\ 7\right).\\[1mm]&\therefore\ \ \ x\equiv4+15\hspace{0.7mm}\cdotp6=94\hphantom{m}&&\left(\text{mod}.\ 105\right).\end{alignat*}
 〔問題 $\boldsymbol{2}$〕 前の問題を一般化して $n$ 個の合同式\[x\equiv a_\nu\hphantom{m}\left(\text{mod}.\ m_\nu\right),\ \ \nu=1,\ 2,\ \cdots\cdots,\ n\]を考察する.解があるために必要かつ十分な条件は\[a_h\equiv a_k\hphantom{m}\left(\text{mod}.\ \left(m_h,\ m_k\right)\right)\hspace{1cm}h,\ k=1,\ 2,\ \cdots\cdots,\ n\]である.解は $m_1$,$m_2$,$\cdots\cdots$,$m_n$ の最小公倍数を法としてただ一つである.
 〔〕 条件が必要であることは明らかである.よって条件が成り立っていると仮定する.この場合かりに $a$,$b$,$c$,$\cdots\cdots$ の最小公倍数を $\left\{a,\ b,\ c,\ \cdots\cdots\right\}$ で表わすことにする.しからば問題 $1$ によって二つの合同式\[\left\{\begin{array}{l}x\equiv a_1\hphantom{m}\left(\text{mod}.\ m_1\right),\\[1mm]x\equiv a_2\hphantom{m}\left(\text{mod}.\ m_2\right)\end{array}\right.\]の解を\[x\equiv b\hphantom{m}\left(\text{mod}.\ \left\{m_1,\ m_2\right\}\right)\]のような形の合同式で表わすことができる.これと第三の合同式とを組み合わせたときに,\[\left\{\begin{array}{l}x\equiv b\hphantom{m}\left(\text{mod}.\ \left\{m_1,\ m_2\right\}\right),\\x\equiv a_3\hphantom{m}\left(\text{mod}.\ m_3\right).\end{array}\right.\]それが $\left\{m_1,\ m_2,\ m_3\right\}$ を法としてただ一つの解を有することを示そう.それができれば,以下同様に進んで問題が解決される.
 さて仮定によって $b\equiv a_1\hphantom{m}\left(\text{mod}.\ m_1\right)$,故に $b-a_3\equiv a_1-a_3\hphantom{m}\left(\text{mod}.\ m_1\right)$,したがって $b-a_3\equiv a_1-a_3\equiv0\hphantom{m}\left(\text{mod}.\ \left(m_1,\ m_3\right)\right)$,すなわち $b-a_3$ は $\left(m_1,\ m_3\right)$ で割り切れる,同様に $\left(m_2,\ m_3\right)$ でも割り切れる.したがって $\left\{\left(m_1,\ m_3\right),\ \left(m_2,\ m_3\right)\right\}$ で割り切れる.
 われわれの目的のためには $b-a_3$ が $\left(\left\{m_1,\ m_2\right\},\ m_3\right)$ で割り切れてくれればよいのであるから,\[\left(\left\{m_1,\ m_2\right\},\ m_3\right)=\left\{\left(m_1,\ m_3\right),\ \left(m_2,\ m_3\right)\right\}\]ならば十分である.幸いにしてこの等式は成り立つ($\S\ 4$,問題 $10$).

 〔注意〕 $\left(a,\ m\right)=1$ であるとき,$ax\equiv b\hphantom{m}\left(\text{mod}.\ m\right)$ の解は $\left(\text{mod}.\ m\right)$ に関して一定であるから,それを $b/a$ で表わすことがある.
 例えば $\dfrac{1}{2}\equiv4\hphantom{m}\left(\text{mod}.\ 7\right)$,$\dfrac{2}{3}\equiv5\hphantom{m}\left(\text{mod}.\ 13\right)$.
 このような記号に分数の計算法を適用することができる.
 例えば\[\begin{alignat*}{1}\frac{a}{b}+\frac{c}{d}&\equiv\frac{ad+bc}{bd},\\[2mm]\frac{a}{b}\hspace{0.7mm}\cdotp\frac{c}{d}&\equiv\frac{ac}{bd}.\end{alignat*}\hphantom{mm}\left(\text{mod}.\ m\right)\]実際 $a/b\equiv x$,$c/d\equiv y$ とすれば,規約によって $\left(b,\ m\right)=1$,$\left(d,\ m\right)=1$,\[bx\equiv a,\ \ dy\equiv c\hspace{1cm}\left(\text{mod}.\ m\right)\]ゆえに\[\begin{alignat*}{1}bd\left(x+y\right)&\equiv ad+bc,\\[2mm]bdxy&\equiv ac\end{alignat*}\hphantom{mm}\left(\text{mod}.\ m\right)\]$\left(bd,\ m\right)=1$ だから\[x+y\equiv\frac{ad+bc}{bd},\ \ xy\equiv\frac{ac}{bd}\hspace{1cm}\left(\text{mod}.\ m\right).\]






$\blacktriangleleft$ $\S\ 5.$ 合同式  $\S\ 7.$ 合同式解法の概論 $\blacktriangleright$

『初等整数論講義 第 $2$ 版』目次へ


 ページトップへ inserted by FC2 system