初等整数論講義/第1章/一次合同式

1. $f(x)$ が整係数の多項式であるとき，合同式

(1)

$f(x)\equiv 0{\pmod {m}}$

を満足せしめる未知の整数 $x$ を求めることを合同式を解くという． $x_{0}$ をこの合同式の一つの解とし，$x_{1}\equiv x_{0}{\pmod {m}}$ とすれば

定理 1.11

$f(x_{1})\equiv f(x_{0})\equiv 0{\pmod {m}}$

即ち $m$ を法として $x_{0}$ と同類なる数はすべて (1) の解である．

故に合同式を解くとは，それを満足せしめる整数の類を求めることである．

由って(1)のすべての解を求めるには，$x=0,1,2,\ldots \ldots ,m-1$ なる $m$ 個の値を当てはめて見れば宜しい． （故にどのような合同式が与えられてあるとしても，手数さえ厭わねば，それを解くことは出来るのである．）

定理 1.13．

一次合同式

$ax\equiv b{\pmod {m}}$

は，$(a,m)=1$ なるときは，一つの解を有する． $(a,m)=d>1$ なるときは，$b$ が $d$ で割り切れるときに限って解を有する． その解の数は $d$ である．解の数は，$m$ を法としての類に関していう．

［証］

(一) $(a,m)=1$ の場合．$x$ に $m$ を法としての剰余系

$x_{1},x_{2},\ldots \ldots ,x_{m}$

の値を与えるときに，$ax$ の値

$ax_{1},ax_{2},\ldots \ldots ,ax_{m}$

はやはり $m$ としての剰余の一組であることは明白である．

実際，$ax_{h}\equiv ax_{k}{\pmod {m}}$ となるのは $a(x_{h}-x_{k})$ が $m$ で割り切れるときに限り， 仮定に由って $(a,m)=1$ であるから， $x_{h}\equiv x_{k}{\pmod {m}}$．それは，$h=k$ なるときに限る．

由って $b$ が如何なる整数であっても，$x_{1},x_{2},\ldots \ldots ,x_{m}$ の中の唯一つに由って

$ax\equiv b{\pmod {m}}$

が満足せしめられねばならぬ．

（二） $(a,m)=d>1$ の場合．

(1)

$ax\equiv b{\pmod {m}}$

に解があるとすれば，$ax-b=my$ であるから，$b=ax-my$ は $d=(a,m)$ で割り切れねばならぬ．$b$ が $d$ で割り切れるとすれば，

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

と置くとき，(1) は

(2)

$a'x\equiv b'{\pmod {m'}}$

に帰する（定理 1.12）． ここでは $(a',m')=1$ であるから， (2) を満足せしめる $x$ は $m'$ を法としての一つの類である． それを $x\equiv x_{0}{\pmod {m'}}$ とすれば， (2)の解は

(3)

$x=x_{0}+m't$

に由って与えられる．ここで $t$ は任意の整数である． $t$ の二つの値 $t_{1},t_{2}$ に関して，これらが $m$ を法として合同になるのは

$m'(t_{1}-t_{2})$

が m で割り切れるとき，すなわち $t_{1}-t_{2}$ が $d$ で割り切れるときに限るから， (3) に於いて $t=0,1,2,\ldots \ldots ,d-1$ なる値を与えるときに， $m$ を法としての (1) のすべての解が得られる． 即ち解の数は $d$ である．

［注意］ 

合同式(1)を解くことは不定方程式

$ax+my=b$

を満足せしめる整数 $x$ を求めることと同じである． 上記の定理 1.13は 定理 1.7と同一である．

［例］

$26x\equiv 1{\pmod {57}}$ を解くこと．

［証］

$(26,57)=1$ であるから，一つの解がある．その解を $x$ とする． $57=26\times 2+5$ を用いる為に，両辺に $2$ を掛けて

$52x\equiv 2{\pmod {57}}$

$\therefore -5x\equiv 2{\pmod {57}}$^[1]

両辺に $5$ を掛けて与えられたる合同式の両辺に加えて

$x\equiv 11{\pmod {57}}$

を得る．

即ち解があれば，それは$x\equiv 11{\pmod {57}}$ でなければならないが，解があることがわかっているから， これが即ち求める解である．

[験算]

$26\times 11=286=57\times 5+1$

このようにして $26x-57y=1$ を解くまでもなく，$x=11$ を得たのである． 実際は上記のようにして $26x-57y=1$ の解を求めるのが近道である． 即ち一つの解が $x=11,y=5$ であるから，一般の解は $x=11+57t,y=5+26t$ である．^[2]

読者は自ら任意の合同式を提出して解いて見るが宜しい．このような練習が整数論を理解するのに必要である．

2. 次の定理も後に引用されるものである．（補遺 5 参照)

定理 1.14^[3]．

$m_{1},m_{2},\ldots \ldots ,m_{k}$ が二つずつ互いに素で，$a_{1},a_{2},\ldots \ldots ,a_{k}$ は任意の整数であるとき

(4)

${\begin{cases}x\equiv a_{1}&{\pmod {m_{1}}}\\x\equiv a_{2}&{\pmod {m_{2}}}\\\ldots \ldots \ldots \\x\equiv a_{k}&{\pmod {m_{k}}}\end{cases}}$

を満足せしめる $x$ は $M=m_{1}m_{2}\ldots \ldots m_{k}$ を法として唯一つ存在する．

［証］

第一の合同式を満足せしめる $x$ は

(5)

$x=a_{1}+m_{1}t$

である．それが第二の合同式をも満足せしめるのは

$a_{1}+m_{1}t\equiv a_{2}{\pmod {m_{2}}}$

即ち

(6)

$m_{1}t\equiv a_{2}-a_{1}{\pmod {m_{2}}}$

なるときである．仮定に由って $(m1,m2)=1$ であるから (6) の解は

$t=t_{0}+m_{2}s$

のような，$m_{2}$ を法としての一類である． これを (5) に代入すれば，

$x=a_{1}+m_{1}t_{0}+m_{1}m_{2}s$

即ち

$x\equiv a_{1}+m_{1}t_{0}{\pmod {m_{1}m_{2}}}$^[4]

である．この一つの合同式で (4)の最初の二つの合同式を置き換えてよい． 由ってこれを(4)の第三の合同式と組みあわせて同様の方法を行うことが出来る． 次第にこのようにして竟に(4)と等値なる

$x\equiv x_{0}{\pmod {M}}$

を得る．

或いは又ガウスが Disquisitiones に述べたように，すべての ${\bmod {}}$を 対称的に取り扱う方法もある．

前のように

$M=m_{1}m_{2}\ldots \ldots m_{k}$

とし，

(7)

$M=m_{1}M_{1}=\ldots \ldots =m_{k}M_{k}$

と置いて

(8)

$M_{n}t_{n}\equiv 1{\pmod {m_{n}}},(n=1,2,\ldots \ldots ,k)$

なる $t_{n}$ を求める．

然らば(4)の解は

$x\equiv a_{1}M_{1}t_{1}+a_{2}M_{2}t_{2}+\ldots \ldots +a_{k}M_{k}t_{k}{\pmod {M}}$

実際、(8) に由って、右辺の第一項 $a_{1}M_{1}t_{1}\equiv a_{1}{\pmod {m_{1}}}$^[5] で， 第二項以下は(7)に由って $M_{2},M_{3},\ldots \ldots ,M_{k}$ が $m_{1}$ で割り切れるから， $x\equiv a_{1}{\pmod {m_{1}}}$． $m_{2},\ldots \ldots ,m_{k}$ に関しても同様であるから， (4)は満足せしめられる．

(4)の解が ${\bmod {M}}$ に関して唯一つに限ることは始めから明白である． $x,x'$ を(4)の解とすれば $x\equiv x'{\bmod {m_{1}}},\ldots \ldots ,{\bmod {m_{k}}}$ だから， $x-x'$ は $m_{1},m_{2},\ldots \ldots ,m_{k}$ で割り切れ， 従ってそれらの最小公倍数なる $M$ で割り切れる． 即ち $x\equiv x'{\pmod {M}}$．

上記の解では、$M_{1},M_{2},\ldots \ldots ,M_{k}$，従って $t_{1},t_{2},\ldots \ldots ,t_{k}$ が $a_{1},a_{2},\ldots \ldots ,a_{k}$ に関係なく定められる．$M_{n}t_{n}$ は即ち $a_{1},a_{2},\ldots \ldots ,a_{k}$ の中で $a_{n}$ だけが $1$ で， その他は $0$ なる場合に於ける(4)の解であって， それらの一次的結合として，任意の $a$ に関する(4)の解が得られるのである．

［例］

$m_{1}=3,m_{2}=5,m_{3}=7$ とすれば $M=105$^[6]

$M_{1}=35,M_{2}=21,M_{3}=15$

$t_{1}=-1,t_{2}=1,t_{3}=1$

$M_{1}t_{1}=-35,M_{2}t_{2}=21,M_{3}t_{3}=15$

ゆえに

$x\equiv a_{1}{\pmod {3}},\equiv a_{2}{\pmod {5}},\equiv a_{3}{\pmod {7}}$

の解は

$x\equiv -35a_{1}+21a_{2}+15a_{3}{\pmod {105}}$．

例えば， $3$ で割れば $1$ が残り， $5$ で割れば $2$ が残り， $7$ で割れば $3$ が残るような数 $x$ は

$x\equiv -35\cdot 1+21\cdot 2+15\cdot 3=52$

或いは一般に

$x\equiv 52{\pmod {105}}$．

［注意］ 

上記の解法を部分分数への分解に応用することができる． 既約分数 ${\frac {x}{M}}$ の分母 $M$ を二つずつ互いに素なる因数 $m_{1},m_{2},\ldots \ldots ,m_{k}$ に（例えば素数冪に）分解し， $x$ を $m_{1},m_{2},\ldots \ldots ,m_{k}$ で割った剰余を $a_{1},a_{2},\ldots \ldots ,a_{k}$ とすれば，

$x=a_{1}M_{1}t_{1}+a_{2}M_{2}t_{2}+\ldots \ldots +a_{k}M_{k}t_{k}+Mt$

から

${\frac {x}{M}}={\frac {a_{1}t_{1}}{m_{1}}}+{\frac {a_{2}t_{2}}{m_{2}}}+\ldots \ldots +{\frac {a_{k}t_{k}}{m_{k}}}+t.$

例えば上の例では

${\frac {52}{105}}=-{\frac {1}{3}}+{\frac {2}{5}}+{\frac {3}{7}}.\quad (t=0)$

由って

${\frac {52}{105}}={\frac {2}{3}}+{\frac {2}{5}}+{\frac {3}{7}}-1$.

命題 1．

法 $m,n$ の最大公約数を $d$，最小公倍数を $l$ とすれば，

${\begin{cases}x\equiv a&{\pmod {m}}\\x\equiv b&{\pmod {n}}\end{cases}}$

が解を有する為に必要且つ充分なる条件は $a\equiv b{\pmod {d}}$ である． 解があれば，$l$ を法として唯一つである．

［解］

定理1.14の始めの証明のようにする．^[7]

［例］

${\begin{cases}x\equiv 4&{\pmod {15}}\\x\equiv 10&{\pmod {21}}\end{cases}}$

$x=4+15t\equiv 10{\pmod {21}},\therefore 15t\equiv 6{\pmod {21}},$

$\therefore 5t\equiv 2{\pmod {7}},\therefore t\equiv 6{\pmod {7}}.$

$\therefore x\equiv 4+15\cdot 6=94{\pmod {105}}$

命題 2．

前の問題を一般化して $n$ 個の合同式

$x\equiv a_{\nu }{\pmod {m_{\nu }}},\nu =1,2,\ldots \ldots ,n$

を考察する． 解があるために必要且つ充分なる条件は

$a_{h}\equiv a_{k}{\pmod {(m_{h},m_{k})}}\quad h,k=1,2,\ldots \ldots ,n$

である．解は $m_{1},m_{2},\ldots \ldots ,m_{n}$ の最小公倍数を法として唯一つである．

［証］

条件が必要であることは明らかである． 由って条件が成り立っていると仮定する．この場合仮に $a,b,c,\ldots \ldots$ の最小公倍数を $\{a,b,c,\ldots \ldots \}$ で表すことにする． 然らば問題1に由って二つの合同式

${\begin{cases}x\equiv a_{1}&{\pmod {m_{1}}},\\x\equiv a_{2}&{\pmod {m_{2}}}\end{cases}}$

の解を $x\equiv b{\pmod {m1,m2}}$ のような形で合同式で表すことができる．これと第三の合同式とを組み合わせたときに，

${\begin{cases}x\equiv b&{\pmod {\{m_{1},m_{2}\}}},\\x\equiv a_{3}&{\pmod {m_{3}}}\end{cases}}$

それが $\{m_{1},m_{2},m_{3}\}$ を法として唯一つの解を有することを示そう．それが出来れば，以下同様に進んで問題が解決される．

さて仮定に由って $b\equiv a_{1}{\pmod {m_{1}}}$， ゆえに $b-a_{3}\equiv a_{1}-a_{3}{\pmod {m_{1}}}$， 従って $b-a_{3}\equiv a_{1}-a_{3}\equiv 0{\pmod {(m_{1},m_{3})}}$， 即ち $b-a_{3}$ は $(m_{1},m_{3})$ で割り切れる， 同様に $(m_{2},m_{3})$ でも割り切れる．従ってｓ $\{(m_{1},m_{3}),(m_{2},m_{3})\}$ で割り切れる．

吾々の目的の為には $b-a_{3}$ が $(\{m_{1},m_{2}\},m_{3})$ で割り切れてくれればよいのであるから，

$(\{m_{1},m_{2}\},m_{3})=\{(m_{1},m_{3}),(m_{2},m_{3})\}$

ならば十分である．幸いにしてこの等式は成り立つ (問題.10)．

〔注意〕

$(a,m)=1$ なるとき，$ax\equiv b{\pmod {m}}$ の解は ${\bmod {m}}$ に関して一定であるから， それを ${\frac {b}{a}}$ で表すことがある．

例えば ${\frac {1}{2}}\equiv 4{\pmod {7}}$，${\frac {2}{3}}\equiv 5{\pmod {13}}$．

このような記号に分数の計算法を適用することができる． 例えば

${\frac {a}{b}}+{\frac {c}{d}}\equiv {\frac {ad+bc}{bd}}{\pmod {m}}$

${\frac {a}{b}}\cdot {\frac {c}{d}}\equiv {\frac {ac}{db}}{\pmod {m}}$

実際，${\frac {b}{a}}\equiv x,$ ${\frac {c}{d}}\equiv y$ とすれば，規約に由って $(b,m)=1,(d,m)=1$．

$bx\equiv a,dy\equiv c{\pmod {m}}$

故に

$bd(x+y)\equiv ad+bc{\pmod {m}}$^[8]

$bdxy\equiv ac{\pmod {m}}$

$(bd,m)=1$ だから

$x+y\equiv {\frac {ad+bc}{bc}},xy\equiv {\frac {ac}{db}}{\pmod {m}}$

1. officious: $52x\equiv 2{\pmod {57}}$， $(57-5)x\equiv 2{\pmod {57}}$， 一方，$57x\equiv 0{\pmod {57}}$， 両辺を引いて $-5x\equiv 2$
2. officious: $26x-57y=1$ に $x=11+57t$ を代入して $y$ を得る．
3. officious: 「中国の剰余定理」
4. officious: $a_{1},a_{2}$ が $t_{0}$ に反映されている．
5. officious:$\because M_{1}t_{1}\equiv 1{\pmod {m_{1}}}$
6. officious:特にこの場合は「百五減算」として和算においても知られていた．
7. officious: $x\equiv a(mod.\ m),x\equiv b(mod.\ n)$において、$\exists t_{1}:x-a=mt_{1},$ すわなち $x=a+mt_{1}$ これを他式に代入、$a+mt_{1}\equiv b(mod.\ n),\exists t_{2}:a+mt_{1}-b=nt_{2}$, すなわち最終的に $a-b=(-t_{1})m+nt_{2}$, 前節までにもみたように $a,b$ を定数とするとき、式 $ax+by$ の $x,y$ をいかように変化させても、$ax+by$ は $gcd(a,b)$ の整数倍の刻みでしか値をとらないし、 $gcd(a,b)$の整数倍の中で必ず解を持つ（等式を満たす $x,y$ の組が存在する．） すなわちもとに戻って、$a-b=(-t_{1})m+nt_{2}$ を満たす$t_{1},t_{2}$ が存在する必要十分条件は、$a-b$ が $gcd(m,n)$ の整数倍であること、すなわち $a\equiv b{\pmod {gcd(m,n)}}$ である．
8. $d\cdot bx\equiv da,b\cdot dy\equiv bc,$ 辺々加えて $dbx+bdy\equiv da+bc$

---