初等整数論講義/第1章/合同式解法の概論

1.

$f(x)=a_{0}x^{n}+a_{1}x^{n-1}+\ldots \ldots +a_{n}$ が整係数の多項式であるとき， 合同式

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

を解くときには，各係数 $a_{\nu }$ をそれと合同なる数で置き換えて差し支えない， 特に法 $m$ で割り切れる係数を有する項は消してもよい．^[1] このような消去を行った後に $a_{0}\neq 0{\pmod {m}}$ ならば，上記の合同式を $n$次という．

法が素数なる合同式に関して次の定理が成り立つ．

定理 1.15．

法 $p$ が素数なるとき，$n$ 次の合同式

(1)

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

は $n$ よりも多くの解を有することを得ない．

解の数はもちろん $p$ を法として，互いに不合同なるものを数えていう．

［証］

合同式 (1) が解を有するとき，$x\equiv a{\pmod {p}}$ を一つの解とする． すなわち $f(a)\equiv 0{\pmod {p}}.$

さて代数的恒等式

$f(x)=(x-a)f_{1}(x)+f(a)$

において $f_{1}(x)$ は $a_{0}x^{n-1}$ を最高次の項とする整係数の多項式である． 由って合同式 (1) は

$(x-a)f_{1}(x)\equiv 0{\pmod {p}}$

と同一の解を有する．$p$ は素数であるから，この合同式は $x-a$ または $f_{1}(x)$ が $p$ で割り切れるときに限って成り立つ．

故に $x\equiv a{\pmod {p}}$ 以外の (1) の解は $n-1$ 次の合同式

$f_{1}(x)\equiv 0{\pmod {p}}$

の解でなければならぬ． 故に定理が $n-1$ 次の多項式に関して正しいならば，$n$ 次の多項式に関しても正しい．

然るに一次の合同式

$a_{0}x+a_{1}\equiv 0{\pmod {p}}\quad (a_{0},p)=1$

は $p$ を法として唯一つの解を有する(定理 1.13)． 故に定理は数学的帰納法に由って証明せられたのである．

［注意］ 

上記の定理に於いて，法 $p$ が素数であることが緊要である． 例えば $x^{2}\equiv 1{\pmod {12}}$ は $x\equiv 1,5,7,11{\pmod {12}}$ なる四つの解を有する．

合同式には解のないことがある．例えば $x^{2}\equiv 2{\pmod {3}}.$

2． 法 $m$ が合成数なるとき，合同式

(2)

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

の解法は法が素数なる場合に帰する．

先ず素数 $p$ を法とするとき，

(3)

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

の解が求められたとして，それから $p$の任意の冪を法とするときの解を求める方法を述べる．

(4)

$f(x)\equiv 0{\pmod {p^{2}}}$

の解は勿論 (3) を満足せしめるから，^[2] $x_{0}$ を (3) の解とするとき， (4) の解は

(5)

$x=x_{0}+py$

のような数の中から求められねばならぬ．これを (4) に代入すれば，

${\begin{alignedat}{2}f(x)&=f(x_{0}+py)\\&=f(x_{0})+pyf'(x_{0})+p^{2}y^{2}{\frac {f''(x0)}{2}}+\ldots \ldots \equiv 0{\pmod {p^{2}}}.\end{alignedat}}$^[3]

さて $f'(x),{\frac {f''(x)}{2}},{\frac {f'''(x)}{3!}},\ldots \ldots$ は整係数の多項式であるから，$f'(x_{0}),{\frac {f''(x_{0})}{2}},\ldots \ldots$ は整数である． ^[4] 由って上記の展開式の第三項以下は $p^{2}$ で割り切れるから， (5) の数で (4) を満足せしめるものを求めることは

$f(x_{0})+pyf'(x)\equiv 0\ {\pmod {p^{2}}}$

から $y$ を求めることに帰する．

又は仮定に由って $f(x_{0})$ は $p$ で割り切れるから，

(6)

${\frac {f(x_{0})}{p}}+yf'(x_{0})\equiv 0\ {\pmod {p}}$

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

（一）　$f'(x_{0})\not \equiv 0\ {\pmod {p}}$ なるときには，(6)は唯一の解を有する． それを

$y\equiv y_{0}\ {\pmod {p}}.$

として (5) に代入すれば， $py\equiv py_{0}\ {\pmod {p^{2}}}$ だから，

(7)

$x\equiv x_{0}+py_{0}\ {\pmod {p^{2}}}.$

を得る．すなわち(3)の一つの解 $x\equiv x_{0}\ {\pmod {p}}$ から (4)の一つの解 (7)を得るのである．

（二）　$f'(x_{0})\equiv 0{\pmod {p}}$ なるときには， (6)は ${\frac {f(x_{0})}{p}}$ が $p$ で割り切れないならば，不可能である． 若しも ${\frac {f(x_{0})}{p}}$ が $p$ で割り切れるならば，任意の $y$ に由って満足せしめられる．^[5] 由って(5)に返って考えるならば，

$x\equiv x_{0},x_{0}+p,x_{0}+2p,\ldots \ldots ,x_{0}+(p-1)p{\pmod {p^{2}}}$

が (4) を満足せしめる． 即ち (5) の形の数 $x$ は 一つも (4) の解を与えないか， 或いは又 $p^{2}$ を法として, $p$ 個の解を与えるかである．

同様に，(3)の代わりに

(8)

$f(x)\equiv 0\ {\pmod {p^{n}}}$

を考察すれば，(8)の一つの解を $x_{0}$ とするとき，

(9)

$x=x_{0}+p^{n}y$

の形の数で，

(10)

$f(x)\equiv 0\ {\pmod {p^{n+1}}}$

を満足せしめるものは，
（一）　$f'(x_{0})\not \equiv 0\ {\pmod {p}}$^[6] の場合には，$p^{n+1}$ を法として唯一つあり，
（二）　$f'(x_{0})\equiv 0\ {\pmod {p}}$ の場合には，$p^{n+1}$ を法として一つもないか，又は $p$ 個ある． $p$ 個の解があるのは $f(x_{0})\equiv 0\ {\pmod {p^{n+1}}}$^[7] で， (9)に於いて $y$ を任意に取っても， それが (10)を満足せしめるときである．

以上要約して次の定理を得る．

定理 1.16．

合同式 $f(x)\equiv 0\ {\pmod {p^{n}}}$ の解は $f(x)\equiv 0{\pmod {p}}$ の解から導かれる．

合同式 $f(x)\equiv 0\ {\pmod {p}}$ の一つの解を $x_{0}$ とするとき，

（一）$f'(x_{0})\not \equiv 0{\pmod {p}}$ ならば，$f(x)\equiv 0\ {\pmod {p^{n}}}$ の解の中に， $x\equiv x_{0}\ {\pmod {p}}$ なるものが，${\bmod {p^{n}}}$ に関して唯一つある．

（二）$f'(x_{0})\equiv 0\ {\pmod {p}}$ なる場合には，$f(x)\equiv 0{\pmod {p^{n}}}$ が $x\equiv x_{0}\ {\pmod {p^{n}}}$ なる解を有するときに，その解から $f(x)\equiv 0\ {\pmod {p^{n+1}}}$ の $p$ 個の解が派生することもあり， 或いは又 $f(x)\equiv 0\ {\pmod {p^{n+1}}}$ は $x\equiv x_{0}\ {\pmod {p^{n}}}$ なる解を有せぬこともある．^[8]

［例］

$p\neq 2$ が素数で，$a$ は $p$ で割り切れないとする．そのとき

$x^{2}\equiv a\ {\pmod {p}}$

が解を有するならば，解は二つある．それを $\pm x_{0}$ とする．

$x_{0}\not \equiv 0\ (mod.\ p),x_{0}\not \equiv -x_{0}\ {\pmod {p}}$

この場合には $f(x)=x^{2}-a,f'(x)=2x.$ 故に $f'(\pm x_{0})=\pm 2x_{0}\not \equiv 0\ {\pmod {p}}$

これは定理1.16の（一）の場合である．故に

$x^{2}\equiv a\ {\pmod {p^{n}}}$

は二つの解を有する．

例えば $x^{2}\equiv 2\ {\pmod {7}}$ の解は $x_{0}\equiv \pm 3{\pmod {7}}$． 今

$x^{2}\equiv 2\ {\pmod {49}}$

の解を求める為に $x=3+7y$ と置けば

$(3+7y)^{2}\equiv 2\ {\pmod {49}}$

から

$9+42y\equiv 2\ {\pmod {49}}$

即ち

$6y\equiv -1\ {\pmod {7}}$

故に

$y\equiv 1\ {\pmod {7}}$

従って

$x\equiv 10\ {\pmod {49}}$

今一つの解は

$x\equiv -10\equiv 39\ {\pmod {49}}$^[9]

定理1.16の（二）の部分はあまりに粗雑であるが，ここでその細論に入るのは時期尚早である． 次に最も簡単なる一例を問題として掲出する．これは初等整数論に於いても重要である． $2$ が別格の素数で，有理整数論に於ける特異点 (singular point) ともいうべきものである所に，目を止めねばならない．

命題 1．

$a\equiv 1\ {\pmod {8}}$ なるとき

$x^{2}\equiv a\ {\pmod {2^{n}}},$ 但し $n\geqq 3$

の解は四つである．その一つを $x_{0}$ とすれば，解は

$\pm x_{0},\pm x_{0}+2^{n-1}$

である．

［証］

$x=1+2y$ を奇数とすれば，$x^{2}=1+4y(y+1)$ で， $y$ または $y+1$ は偶数であるから $x^{2}\equiv 1\ {\pmod {8}}$．

故に $a\equiv 1\ {\pmod {8}}$ は $a$ が奇数なるときに問題の合同式が解を有する為に必要なる条件である．

$n=3$ ならば，この条件の下に於いて，解は $x\equiv 1,3,5,7\ {\pmod {8}}$である．^[10] 或いは $x\equiv \pm 1,\pm 1+4\ {\pmod {8}}.$

由って数学的帰納法を用いて証明をする．

指数 $n$ に関して定理は既に証明されたとすれば，指数 $n+1$ のとき解は

$\pm x_{0}+2^{n}y$ 又は $(\pm x_{0}+2^{n-1})+2^{n}y{\pmod {2^{n+1}}}$^[11]

でなければならない．その $y(y=0,$ 又は $1)$ は

(11)

$(\pm x_{0}+2^{n}y)^{2}\equiv a\ {\pmod {2^{n+1}}}$

或いは

(12)

$((\pm x_{0}+2^{n-1})+2^{n}y)^{2}\equiv a\ {\pmod {2^{n+1}}}$

から求められる．

仮定に由って，$x_{0}^{2}-a=2^{n}t.$ ゆえに (11) から

$2^{n}t\equiv 0\ {\pmod {2^{n+1}}}$^[12]

$t$ が奇数ならば，これは不可能である．^[13] また $t$ が偶数ならば， $y$ は任意であるから， ${\bmod {2^{n+1}}}$ に関しては，$y=0,1$ として $\pm x_{0}$ 及び $\pm x_{0}+2^{n}$ が解である．即ち ${\bmod {2^{n}}}$ に関する解 $\pm x_{0}$ から，$mod.\ 2^{n+1}$ に関する解が得られないか，或いは四つの解が得られる．

次に

${\begin{aligned}(\pm x_{0}+2^{n-1})^{2}&\equiv x_{0}^{2}\pm 2^{n}x_{0}+2^{2n-2}\\&\equiv x_{0}^{2}+2^{n}\ {\pmod {2^{n+1}}}\\\end{aligned}}$

（$x_{0}$ は奇数，又 $2n-2\geqq n+1$　だから^[14]）．

由って(12) から

$2^{n}t+2^{n}\equiv 0\ {\pmod {2^{n+1}}}.$^[15]

今度は $t$ が偶数ならば，これは不可能であるが^[16] ，$t$ が奇数ならば， $y$ は任意である． 故に ${\bmod {2^{n+1}}}$ に関して

$\pm (x_{0}+2^{n-1})$ 及び $\pm (x_{0}+2^{n-1})+2^{n}$

なる四つの解が得られる．

由って定理は証明せられた．

この問題では $f(x)=x^{2}-a,f'(x)=2x$ で，すなわち定理1.16 の(二）の場合であるが， ${\bmod {2^{n}}}$ に関する解

$\pm x_{0}$ 又は $\pm x_{0}+2^{n-1}$

の中の一方からは ${\bmod {2^{n+1}}}$ に関する解が得られないで，他の一方からは二つずつの解が派生して，解の数がいつも四つになるのである．

3.

一般の法に関する合同式の解は法が素数冪なる場合に帰する．

定理 1.17．

法 $m$ を素数冪に分解して

(13)

$m=p^{a}\cdot q^{b}\ldots \ldots$

とするとき，

(14)

$f(x)\equiv 0\ {\pmod {p^{a}}}$

(15)

$f(x)\equiv 0\ {\pmod {q^{b}}}$

$\ldots \ldots \ldots \ldots \ldots \ldots \ldots$

がそれぞれ $\nu ,\nu ',\ldots \ldots$ 個の解を有するとすれば，

(16)

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

は $\nu \nu '\ldots \ldots$ 個の解を有する．それらは

(17)

${\begin{cases}x\equiv \alpha {\pmod {p^{a}}}\\x\equiv \beta {\pmod {q^{b}}}\\\ldots \ldots \ldots \ldots \ldots \ldots \end{cases}}$

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

［証］

$x$ が (16) の解ならば， 勿論 (14), (15), $\ldots \ldots$ の解であるから， (17) を満足せしめる． 逆に (17) を満足せしめる $x$ は (14), (15), $\ldots \ldots$ を満足せしめるから， (16)を満足せしめる^[17]

［例］

$x^{2}\equiv 1{\pmod {3}}$ は二つの解 $\alpha =\pm 1{\pmod {3}}$ を有する. また $x^{2}\equiv 1{\pmod {4}}$ は二つの解 $\beta =\pm 1{\pmod {4}}$ を有する．

故に

$x^{2}\equiv 1{\pmod {12}}$

は四つの解を有する．それらは

${\begin{cases}x\equiv 1{\pmod {3}}\\x\equiv 1{\pmod {4}}\end{cases}}{\begin{cases}x\equiv 1{\pmod {3}}\\x\equiv -1{\pmod {4}}\end{cases}}{\begin{cases}x\equiv -1{\pmod {3}}\\x\equiv 1{\pmod {4}}\end{cases}}{\begin{cases}x\equiv -1{\pmod {3}}\\x\equiv -1{\pmod {4}}\end{cases}}$

から求められる，即ち

$x\equiv 1,x\equiv 7,x\equiv 5,x\equiv 11\ {\pmod {12}}$

である．

1. officious:$\forall x\ px\equiv 0\ (mod.\ p)$， また $ax^{n}=(a'+mp)x^{n}$ と分解できるのであれば，$ax^{n}=(a'+mp)x^{n}=a'x^{n}+p(mx^{n})\equiv a'x^{n}$.
2. officious: $f(x)\equiv 0\ {\pmod {p^{2}}}$ ならば $\exists xf(x)=p^{2}x,f(x)=p(px),$ すなわち $f(x)\equiv 0{\pmod {p}}$
3. officious: テイラー級数：

   $f(x)=\sum _{n=0}^{\infty }{\frac {f^{(n)}(a)}{n!}}(x-a)^{n}$

   の別表現

   ${\begin{alignedat}{2}f(x+\Delta )&=\sum _{n=0}^{\infty }{\frac {f^{(n)}(x)}{n!}}\Delta ^{n}\\&=f(x)+f'(x)\Delta +{\frac {f''(x)}{2!}}\Delta ^{2}+{\frac {f'''(x)}{3!}}\Delta ^{3}+\ldots \end{alignedat}}$

   において $x=x_{0},\Delta =py$ を代入する.

4. 今より展開される議論では $\equiv 0\ {\pmod {p}}$ の合同式の等式変形に帰着する．したがって，$f(x)$ が高々 n 次の多項式として係数　${\frac {f''(x)}{2!}},{\frac {f'''(x)}{3!}},\ldots \ldots$ が整数でなければ $n!$ を両辺にかければよい．
5. officious: 仮定より $f'(x_{0})\equiv 0{\pmod {p}}$ であり，かつ ${\frac {f(x_{0})}{p}}$ が $p$ で割り切れるのならば $f(x_{0})\equiv 0{\pmod {p}}$ である．すなわち $0+y\cdot 0\equiv 0\ {\pmod {p}}$．
6. officious: (6) に対応する式を導出するために，$f(x_{0})+p^{n}yf'(x)\equiv 0\ {\pmod {p^{n+1}}}$ において両辺を $p^{n}$ で割ると 定理1.12(の一般例）により法は $p$ となる．
7. officious: ${\pmod {p^{n}}}$ では？
9. officious: 同じく $x=-3+7y$ とおいて $42y\equiv 7\ {\pmod {49}},6y\equiv 1\ {\pmod {7}},y\equiv 6\ {\pmod {7}}$ したがって $x=-3+7\cdot 6=39$
10. すぐ上を参照すれば $x$ が奇数であれば $x^{2}\equiv 1\ {\pmod {8}},\therefore x=1,3,5,7$． または，節前半の議論を参照し $x^{2}\equiv 1\ {\pmod {2}}$ の解は $x\equiv 1\ {\pmod {2}}$ ， $x^{2}\equiv 1\ {\pmod {2^{2}}}$ は ${\frac {f(x_{0})}{p}}\equiv 0\ {\pmod {p}}$ により $x\equiv 1,3\ {\pmod {2^{2}}}$． これを経て$x^{2}\equiv 1\ {\pmod {2^{3}}}$ は同じく${\frac {f(x_{0})}{p}}\equiv 0\ {\pmod {p}}$ で $x\equiv 1,3,5,7{\pmod {2^{3}}}$ を得る． これをさらに繰り返すと以下の議論がわかりやすい．
11. 指数 $n$ について成立を仮定しこの解を $x_{0}$ とすると，指数$n+1$ の解 $x$ も 指数 $n$ について成立する（節前半，式 (3) と 式 (4) の議論を参照）から $x=x_{0}+2^{n}y$ とおける．
12. officious: $2^{n}t+2^{n+1}(y^{2}\pm x_{0}y)\equiv 0\ {\pmod {2^{n+1}}}$
13. officious: $t=2m+1$ とおくと $2^{n}\equiv 0{\pmod {2^{n+1}}}.$ これを満たす $n$ は存在しない.
14. officisous:$x_{0}$ が奇数のとき，これを $x_{0}=2m+1$ とおくと，$\pm 2^{n}x_{0}=\pm 2^{n}(2m+1)=\pm \{(m\cdot 2^{n+1})+2^{n}\}=\pm 2^{n}$． また $2^{n}-(-2^{n})=2^{n+1}$ より，$2^{n}\equiv -2^{n}\ {\pmod {2^{n+1}}}$ から $\pm$ を外してもよい．
15. officious: $\{(\pm x_{0}+2^{n-1})+2^{n}y\}^{2}\equiv a{\pmod {2^{n+1}}}$ より $(\pm x_{0}+2^{n-1})^{2}+2^{n+1}\cdot y(\pm x_{0}+2^{n-1})+2^{n+1}\cdot y^{2}-a\equiv 0\ {\pmod {2^{n+1}}}$， $x_{0}^{2}+2^{n}+\color {blue}2^{n+1}\cdot (\pm x_{0}+2^{n-1})+\color {blue}{2^{n+1}\cdot y^{2}}$$-a\equiv 0\ {\pmod {2^{n+1}}}$，ここで青字部分は消去される．これに $x_{0}^{2}-a=2^{n}t$ を代入する．
16. officious: $t=2m$ とおくと $2^{n}\equiv 0\ {\pmod {2^{n+1}}}$ これを満たす n は存在しない．

---