2024-06-02

第一章初等整數論　§3一次ノ不定方程式（前編）

前回は，ユークリッドの互除法を用いて最大公約数，最小公倍数を計算する手法を学びました．

1. 本節デ論ズルノハ

$ax+by+cz=k$

ノヤウナ，二ツ以上ノ未知數ヲ含ム一ツノ一次方程式ガ與ヘラレテ，シカモ係數 $a,b,c,k$ ガ整數デアルトキ，ソノ方程式ノ全テノ整數解ヲ求メルトイフ問題デアル．

今回はこれです．一般には $n$ を2以上の整数， $a_1,...,a_n$ を整数の定数として，

$a_1x_1+a_2x_2+\dots+a_nx_n=k$

を満たす整数の組 $(x_1,x_2,...,x_n)$ をすべて求めるということになります．高校で学ぶ $ax+by=k$ の形の整数係数方程式は， $n=2$ の場合です．

後ニ説明スルヤウニ，コノ方程式ガ整數解ヲ有スルナラバ，無數ノ整數解ガアル．

整数解を有するならば，それは無数にある，ということで，整数解が1組だけ，とか2組だけ，のようなことはないのですね．整数解が1個もないか，無限に存在するかのどちらかであるのでしょう．

コノ意味ニ於テ古來コレヲ不定方程式ト呼ンデヰタノデアルガ，代數的方程式論ニ於ケル不定ト區別スル爲ニ近時ハ整係數ノ方程式ノ整數解ヲ求メルコトヲヂオフアントスノ問題，從テソノ方程式ヲヂオフアントスノ方程式トモイフ．

解が定まらないということで「不定方程式」と呼んでいたそうです．

代数的方程式*1の「不定」とはおそらく，例えば $0x=0$ のように，任意の $x$ が方程式を満たすようなものを言うのでしょう．一次不定方程式の解は無数にあるとしても，何でもよいというわけではないため，区別するために「不定」という言葉を使わないこともあるようです．

この方程式をディオファントスの方程式というかどうかは文脈からは判断しかねますが，wikipediaによれば，ディオファントス方程式は，二次以上の方程式も指すようです．岩波の数学辞典によれば，「一般に，整数係数の多項式を0をおいた連立方程式

$f_i(x_1,...,x_n)=0\ (i=1,...,m)$

の整数解 $(x_1,...,x_n)\in\mathbb{Z}$ を求めることを，不定方程式またはDiophantus方程式を解くという．」とあります．現在ではもっと一般的なものを考察しているんですね．

このような事情があるため，ここで扱う形の不定方程式は一次不定方程式と呼ぶことにしましょう．

ヂオフアントス(Diophantus)ハ西暦約350年ノ頃アレキサンドリアニ生存シテヰタトサレテヰル．

手元の広辞苑によれば，ディオファントスは西暦250年頃のアレキサンドリアの人とあります．インターネットでも250年頃のほうが多数ですが…．こういう昔の人の生年って，どのように推定してるんでしょうね．ディオファントスのお墓に書いてあるんでしょうか．

外国人の名前や地名に下線が引いてありますが，これは単語の切れ目が分かりやすくするために引かれているもので，別段強調しているわけではないと思います．

方程式，特ニ一次方程式ノ解法ハヂオフアントスノ著書ニ始メテ載セラレタモノデアルガ，ソノ時代ヲ考ヘテ想像サレルヤウニ，主トシテ有理數特ニ整數ヲ取扱ウタモノデアル．

「初の」という意味の言葉は，現代では「初めて」と書くのが一般的であっても，当時は「始めて」と書くことがありましたので，誤記ではありません．

ディオファントスの『算術』という本ではいくつかの方程式を，正の有理数の範囲で解く方法が記されているようです．当時，無理数の存在は知られていたようですが，認められていなかったのかもしれません．

なお，『算術』の第2巻の問題8は「 $x^2+y^2=16$ を（有理数の範囲で）解け」というもので，後世のフェルマーがその写本に，「 $n$ が3以上の整数のとき， $x^n+y^n=z^n$ の整数解が存在しない」というコメントを書き添えた問題として有名です．

[定理1.7]　一次ノ不定方程式

(1)

$ax+by+cz=k$

ガ解ヲ有スルガ爲ニ必要且充分ナル條件ハ $k$ ガ $d=(a,b,c)$ デ割リ切レルコトデアル．（變數ノ數ハ任意）．

$a,b,c$ がすべて $0$ のときは，最大公約数を定義することができません．いずれかが $0$ のときは，もっと変数が少ない場合に帰着できます．そこで，いずれも $0$ でないとしましょう．

$d$ は $a,b,c$ の最大公約数なので，明らかに左辺は $d$ の倍数となります．よって $k$ が $d$ の倍数でなければ解が存在しないのは明らかです．

問題は $k$ が $d$ の倍数のとき，必ずこれを満たす $x,y,z$ が存在することを示す部分です．

最後，「変数の数は任意」と書いてあります．今回は3つで表現してありますが， $n$ 個のときも同様なのでしょう．

[注意]　變數 $x,y,z$ ニ任意ノ整數値ヲ與ヘルトキニ，一次形式 $ax+by+cz$ ガ取ルトコロノ値ヲコノ一次形式ニ由テ表ハサレル數トイフ．コノ用語ニ由レバ，上ノ定理ヲ次ノヤウニ言ヒ表ハスコトガデキル．

変数 $x_1,...,x_n$ の一次形式とは， $a_1x_1+\dots+a_nx_n$ の形の一次関数のことです．

一次形式

$f(x,y,z)=ax+by+cz$

ニ由ツテ表ハサレル數ハ $d=(a,b,c)$ ノ倍數の全體デアル．

$k$ が $d$ の倍数ならばこの一次形式によって表され，そうでないならば表すことが出来ないので， $f(x,y,z)=ax+by+cz$ によって表される数は $d$ の倍数の全体であると言えるでしょう．

[證]　 $0$ ハ勿論一次形式 $f$ ニ由ツテ表ハサレル數デアル．（例ヘバ $x=y=z=0$ 又ハ $x=b,y=-a,z=0$ ナドトスルトキ， $f=0$ ）．

どのような定数 $a,b,c$ が与えられても， $f(0,0,0)=0$ なので， $0$ は一次形式 $f$ によって表される数です．他の表し方もあります．

又 $k$ ガ $f$ ニ由テ表ハサレルナラバ $-k$ モ $f$ ニ由テ表ハサレルコト勿論デアル（變數ノ符號ヲ變ヘレバヨイ）．

$k$ が $f$ で表されるとき，

$f(x_0,y_0,z_0)=ax_0+by_0+cz_0=k$

となる $x_0,y_0,z_0$ が存在します．このとき，

$f(-x_0,-y_0,-z_0)=-(ax_0+by_0+cz_0)=-k$

なので， $-k$ も $f$ によって表されます．

サテ $f$ ニ由ツテ表ハサレル整數ノ中ノ最小ノ正ナルモノヲ $k_0$ トシテ

(2)

$ax_0+by_0+cz_0=k_0$

ト置ク．

まず $k_0$ が存在するかどうかですが， $a,b,c$ がすべて $0$ であるということはないので， $a$ が $0$ でないとすると $f(1,0,0)=a,f(-1,0,0)=-a$ のいずれかは正の数です．よって最小の正の数が存在します．

そのような $k_0$ に対して， $f(x,y,z)=k_0$ となる $x,y,z$ の組が少なくとも一つ存在する*2ので，それを $(x_0,y_0,z_0)$ とおきます．

又 $f$ ニ由ツテ表ハサレル任意ノ整數ヲ $k$ トシテ

(3)

$ax+by+cz=k$

ト置ク．然ラバ $k$ ハ $k_0$ ノ倍數デアル．

まじで．

何故ナラバ，若シモ $k$ が $k_0$ ノ倍数デナクテ

$k=qk_0+r,~\quad 0\lt r\lt k_0$

ナラバ，(2),(3)ニ由テ

$r=k-qk_0=a(x-qx_0)+b(y-qy_0)+x(z-qz_0)$

デアルカラ， $k_0$ ヨリモ小ナル正ノ整數 $r$ ガ $f$ ニ由ツテ表ハサレルコトニナル．

以前，「2つ以上の倍数の公倍数は，最小公倍数の倍数である（定理1.3）」を証明したときにも用いた手法です． $a$ が $b$ の倍数であることを証明するには， $a$ を $b$ で割った余りが $0$ であることを示せばよい．よく使われる手法っぽいですね．

コレハ矛盾デアル．故ニ $k$ ハ $k_0$ デ割リ切レル．

$0\lt r\lt k_0$ でないのだから， $r=0$ であるしかありません．よって $k$ は $k_0$ の倍数であることが示されました．

然ルニ $a=a.1+b.0+c.0$ ハ $f$ ニ由ツテ表サレル數デアルカラ， $a$ ハ $k_0$ デ割リ切レル．

$f(1,0,0)=a$ です．さっき示した手法を用いれば， $a$ は $k_0$ の倍数です．

同様ニ $b,c$ モ $k_0$ デ割リ切レル．

$f(0,1,0)=b,f(0,0,1)=c$ ですから， $b,c$ も $k_0$ の倍数です．

即チ $k_0$ ハ $a,b,c$ ノ公約数デアルガ， $k_0$ ハ(2)ニ由テ $d=(a,b,c)$ ノ倍數(定理1.1)デアルカラ， $k_0=d$ ．

$k_0$ は $a,b,c$ の公約数なので， $d$ を $a,b,c$ の最大公約数とすると， $k_0\leqq d$ です．

定理1.1というのは「ある整数の倍数の和，または倍数の倍数は，その整数の倍数である」というものでした． $a,b,c$ は $d$ の倍数なので，(2)の左辺 $ax_0+by_0+cz_0$ は $d$ の正の倍数です．よって $k_0\geqq d$ です．

以上より， $k_0=d$ です．

故ニ $d$ ハ一次式 $f$ ニ由ツテ表ハサレル，

$d=ax_0+by_0+cz_0$

具体的にどのように表すかは分かりませんが，一次形式 $f$ によって表される最小の正の数は $d$ であることは間違いありません．

既ニ $d$ ガ $f$ ニ由テ表ハサレルナラバ， $d$ ノ任意ノ倍數ハ $f$ ニ由テ表サレル數デアル．

$d$ の倍数を $md$ としましょう．

$f(x_0,y_0,z_0)=d$ のとき， $f(mx_0,my_0,mz_0)=md$ なので，任意の $m$ に対して $md$ は $f$ によって表されます．

又逆ニ $f$ ニ由テ表サレル數ハ勿論 $d$ ノ倍數デアル（定理1.1）カラ，定理ハ證明セラレタノデアル．

$a,b,c$ は $d$ の倍数なので，定理1.1（ある整数の倍数の倍数や，倍数の和は，その整数の倍数である）より， $f$ によって表される数は $d$ の倍数です．

[注意]　上記ノ證明デハ定理1.2ノミヲ根據ニシテ§2ノ定理ヲ一ツモ用ヰナカツタ．

定理1.2というのは，整除に関する定理です． $a$ が整数で， $b$ が自然数なら，

$a=qb+r\ (0\leqq r\lt b)$

を満たす $q,r$ がただ一組存在するというものでした．

§2は最大公約数，最小公倍数に関する節であり，

「公倍数は最小公倍数の倍数（定理1.3）」
「公約数は最大公約数の約数（定理1.4）」
「2つの数の積は，その最大公約数と最小公倍数の積（定理1.5）」
「互いに素な $a,b$ に対し， $bc$ が $a$ で割り切れるなら $c$ は $a$ で割り切れる（定理1.6）」

が証明されています．確かに使わなかったですね．

由テコノ證明ノ中デ定理1.4ガ再ビ證明サレテヰル．

ほう．

即チ $k_0$ ガ $a,b,c$ ノ公約數デアルコトガ示サレ，同時ニ又(2)ニ由テ $k_0$ ガ $a,b,c$ ノ任意ノ公約數ノ倍數デアルコトガ分ルカラ， $k_0$ ハ最大公約數デアル．

$f$ によって表される最小の正の数 $k_0$ は $a$ の約数でも $b$ の約数でも $c$ の約数でもあるので， $a,b,c$ の公約数です．

$a,b,c$ の任意の公約数を $k_1$ とすると， $f(x_0,y_0,z_0)=ax_0+by_0+cz_0$ は $k_1$ の倍数です．よって $k_1\leqq k_0$ です．

$k_1=d$ とすれば $k_0=d$ が得られます．また， $d$ は任意の公約数 $k_1$ の倍数であることも同時に分かります．

確かに，証明の中で，定理1.4がそのまま得られていました．

定理1.6モ上記ノ定理カラ導カレル． $(a,b)=1$ ナラバ， $ax+by=1$ ナル整數 $x,y$ ガアルカラ， $acx+bcy=c$ ．

$a,b$ が互いに素のときは， $ax+by=1$ となる $x,y$ が必ず存在します．

これに $c$ をかけて， $acx+bcy=c$ ．

故ニ $ac$ ガ $b$ デ割リ切レルナラバ，左邊ノ二ツノ項ガ $b$ デ割リ切レルカラ， $c$ ガ $b$ デ割リ切レル．即チ定理1.6デアル．

そうですね．左辺が $b$ の倍数となるので， $c$ は $b$ の倍数です．証明できました．

次回は具体的に一次不定方程式の解を得ることを考えます．

*1:多項式を等号で結んだ形の方程式．

*2:上の話によれば無数に存在するらしい．

2024-05-10

第一章初等整數論　§2最大公約數，最小公倍數（後編）

前回は，2つの整数のユークリッドの互除法を証明しました．

$a,b$ の最大公約数を $(a,b)$ とするとき， $(a,b)=(a-qb,b)$ が成り立ちます．

これを何度も使うことによって，最大公約数を求めることができます．

$a,b$ の最大公約数 $g$ が分かれば最小公倍数 $l$ は $ab=gl$ によって求めることができます( $a,b$ が非負整数の場合)．

今回は，3つ以上の整数の最大公約数について考えます．

三ツ以上ノ整數 $a,b,c,...,l$ ノ最大公約數ヲ求メルニモ互助法ヲ應用スルコトガデキル．

$l$ は12番目のアルファベットなので，これだと12個の整数という意味に思えます．有限個ということを強調したのでしょうか．ともかく， $n$ を2以上の整数として，1以上の整数の組 $a_1,a_2,...,a_n$ の意味だと考えることにします．

今コレラノ數ノ中 $a$ ガ最モ小サイトキハ， $a$ デ $b,c,...,l$ ヲ割ツテ剰餘ヲ $b',c',...,l'$ トスル．然ラバ問題1ト同樣ニ

$(a,b,c,...,l)=(a,b',c',...,l').$

うーん． $(a_1,a_2,...,a_n)=g$ として，この中の最小値は $a_1$ であるとしてよいです．

整除の原理より， $2\leqq k\leqq n$ なるすべての $k$ について， $a_k=a_1q_k+r_k\ (0\leqq r_k\lt a_1)$ となる $q_k,r_k$ が唯一つ存在します．このとき，

$(a_1,r_2,r_3,...,r_n)=g'$ として， $g=g'$ を示せばよいです．

$a_1,a_2,...,a_n$ は $g$ の倍数なので， $r_k\ (k=2,3,...,n)$ は $g$ の倍数です．よって $g$ は $a_1,r_2,...,r_n$ の公約数なので， $g$ は $g'$ の約数であり， $g\leqq g'$ であることが分かります．

また， $a_1,r_2,...,r_n$ は $g'$ の倍数なので， $a_k\ (k=2,3,...,n)$ は $g'$ の倍数です．よって $g$ は $a_1,a_2,...,a_n$ の公倍数なので， $g'$ は $g$ の約数であり， $g'\leqq g$ であることが分かります．

以上より， $g=g'$ です．

剰餘ノ中ニ $0$ ガアレバソレヲ $(\quad)$ ノ中カラ省イテヨイ．

$0$ の約数は $0$ 以外の任意の整数なので， $(a_1,r_2,r_3,...,r_n)$ と， $a_1,r_2,r_3,...,r_n$ の $0$ 以外の整数のみの最大公約数は，一致するはずです．

サテ $(a,b',c',...,l')$ ニ同樣ノ操作ヲ行フ．

同様の操作というのは，このうちの最小値を $m$ として，それ以外の剰余をとるということです．

ソノトキ除數ニスル最小數ハ $b',c',...,l'$ ノ中デ，ソレハ $a$ ヨリモ小デアル．

$r_2,r_3,...,r_n$ は $a$ で割ったときの余りだったので， $a$ より小さいです．

コノ操作ヲ繼續スレバ，毎回(　)内ノ最大數ガ減少スルカラ，次第ニ剰餘0ガ出テ來テ，竟ニハ括弧内ニ唯一ツノ數ガ殘ル．

この操作を継続して行うと，割る数がだんだん小さくなっていく，ということでしょうね． $a_1,a_2,...,a_n$ の最小値を $m$ とすれば， $m$ 回以内の操作で唯一の数が残ることでしょう．

ソレガ即チ $(a,b,c,...,l)$ デアル．

pythonでは次のようになるでしょうか．Aは自然数を要素に持つ配列です．

def func(A):
    m=min(A)
    R=[a%m for a in A]+[m]
    F=list(filter(None,R))
    if len(F)==1:
        return F[0]
    else:
        return func(F)

剰餘ハ絶對的最小剰餘ヲ取ルガヨイ．

ムムム，普通の剰余ではなく絶対的最小剰余なんですね．

絶対的最小剰余とは，次のようなものでした．

整数 $a$ と自然数 $b$ について，

$a=qb+r,~|r|\leqq\dfrac b2$

となる整数 $q,r$ が存在する．この $r$ を絶対的最小剰余という．

$a$ が $\dfrac b2$ の奇数倍であるときは $q,r$ は2組考えられますが，どちらにせよ $|r|=\dfrac b2$ です．

普通の剰余に比べて，絶対的最小剰余を採用すると，割る数が急速に小さくなっていきます．例えば $21$ と $13$ の最大公約数を求めるとき，普通の剰余を用いると

$(21,13)=(13,8)=(8,5)=(5,3)=(3,2)=(2,1)=(1,0)=1$

のように $6$ 回の整除が必要ですが，絶対的最小剰余なら

$(21,13)=(13,-5)=(5,-2)=(2,1)=(1,0)=1$

のように $4$ 回で済みます．

先程の剰余をとるところを，絶対的最小剰余をとるように変更すれば，次のようになるでしょうか．

def func(A):
    m=min(A)
    R=[min(a%m,m-a%m) for a in A]+[m]
    F=list(filter(None,R))
    if len(F)==1:
        return F[0]
    else:
        return func(F)

[例]　 $(629,391,255)=(119,-119,255)=(119,17)=17$ ．

絶対的最小剰余の絶対値は，割る数の半分以下になるのがよいですね．

[問題2.]　三ツ以上ノ整數ノ最小公倍數ヲ求メルトキ，ソレラノ整數ノ一部分ヲソノ最小公倍數デ置キ換エテヨイ．例ヘバ $a,b,c,...,k$ ノ最小公倍數ハ， $a,b$ ノ最小公倍數 $m$ ト $c,...,k$ ノ最小公倍數ニ等シイ．

当たり前に使っているような気がします． $24,36,50$ の最小公倍数を求めるとき， $24,36$ の最小公倍数は $72$ なので， $72,50$ の最小公倍数を求めればよい，と考えるようなことですね．

[解]　 $a,b,c,...,k$ ノ最小公倍數ヲ $l$ トシ， $m,c,...,k$ ノ最小公倍數ヲ $l'$ トスレバ， $l$ は $a,b$ ノ公倍數デアルカラ， $m$ ノ倍數デアル（定理1.3）．

$n$ 個（ $n\geqq 3$ ）の自然数の組 $a_1,a_2,...,a_n$ の最小公倍数を $l$ とし， $m$ を $a_1,a_2$ の最小公倍数とし， $m,a_3,...,a_n$ の最小公倍数を $l'$ とします．

$l$ は $a_1,a_2,...,a_n$ に共通する倍数のうち最小のものなので， $a_1,a_2$ の公倍数です．定理1.3は「2つ以上の整数の公倍数は，最小公倍数の倍数である」というものでしたから，これを適用して $l$ は $m$ の倍数です．

$l$ ハ固ヨリ $c,...,k$ ノ倍數デアルカラ $l$ ハ $m,c,...,k$ ノ公倍數，從テ $l'$ ノ倍數デアル．

「固より」は「もとより」と読み，「もともと」「いうまでもなく」のような意味です．

$l$ は結局 $m,a_3,...,a_n$ の倍数ということが分かり，これらの公倍数です．再び定理1.3を用いれば， $l$ は $l'$ の倍数であることが分かります．

又 $l'$ ハ $m$ ノ倍數，從テ， $a,b$ ノ倍數，従テ $a,b,c,...,k$ ノ公倍數，從テ $l$ ノ倍數デアル．

定義を使っているだけですね．最後はみたび定理1.3を使っています．

コノヤウニ $l$ ハ $l'$ ノ倍數， $l'$ ハ $l$ ノ倍數デアルカラ $l=l'$ ．

$l\geqq l'$ であり， $l'\geqq l$ であるから， $l=l'$ です．この証明法，何度目か分かりませんがよく出てくる気がします．

二ツノ整數ノ最小公倍數ハ定理1.5ニ由テ最大公約數カラ求メラレル．

定理1.5とは， $a,b$ の最小公倍数を $l$ ，最大公約数を $m$ とするとき， $ab=lm$ であるという定理です．

由テ上記問題ノ定理ヲ應用シテ任意數ノ整數ノ最小公倍數ガ求メラレル．

$a_1,a_2,...a_n$ の最小公倍数 $L$ を求めたいとします．

$a_1,a_2$ の最大公約数 $l$ をユークリッドの互除法で求めると，最小公倍数 $m$ は $m=\dfrac{a_1a_2}l$ です．このとき， $m,a_3,...,a_n$ の最大公約数は $L$ となります．これで， $n$ 個の数の最大公約数を求める問題から， $n-1$ 個の数の最大公約数を求める問題になりました．

これを何度も使えば，最小公倍数を求めることができます．pythonでは，次のように書けるでしょう．Aは自然数からなる配列です．

def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
def lcm(A):
    ans=1
    for a in A:
        ans=ans*a//gcd(ans,a)
    return ans

3つの自然数の組 $a,b,c$ の最小公倍数を $l$ ，最大公約数を $m$ とするとき， $abc=lm$ は必ずしも成り立たないことに注意します*1．

*1:例えば， $1,2,2$ の最大公約数は $1$ で，最小公倍数は $2$ ．

2024-04-10

第一章初等整數論　§2最大公約數，最小公倍數（中編2）

前回は，2つの正の数の積は，その正の最小公倍数と，最大公約数の積であること[定理1.5]と， $a,b$ が互いに素で $bc$ が $a$ の倍数ならば， $c$ は $a$ の倍数であること[定理1.6]を証明しました．

今回は，実際に最小公倍数と最大公約数を求める方法についてです．

實際ニ，與ヘラレタル（正ノ）整數ノ最大公約數，又ハ最小公倍數ヲ求メル方法ハ周知デアルガ，コノ際，念ノ爲ニソノ理論的ノ根據ヲ叩イテオクノモ無用デハアルマイ．

最大公約数を求めるには，ユークリッドの互除法を用いるか，2つ以上の整数を素因数分解して指数部分の最小値を見ていくかすればよいです．

最大公約数の筆算（すだれ算）というのもあります．例えば， $12,24,48$ の最大公約数は次のように共通の約数でどんどん割っていって，割れなくなったら $3\times 2\times 2$ とするものです．これも，どうやら素因数分解の一意性を根拠にしているようです．

2つの数の最大公約数が分かれば，定理1.5から最小公倍数を求めることができます．

[問題1]　 $(a,b)=(a-qb,b)$

$a,b$ の最大公約数は， $a-qb,b$ の最大公約数に等しい，という有名な定理です．

[解]　 $m$ ヲ $a,b$ ノ最大公約數トスレバ， $m$ ハ $a-qb$ ノ約數，従テ $a-qb,b$ ノ公約數，従テ $(a-qb,b)$ ノ約數デアル．(定理1.4)

定理1.1*1より， $a-qb$ は $m$ の倍数となります．よって $m$ は $a-qb,b$ の公約数です．定理1.4*2より，これは $a-qb,b$ の最大公約数の約数です．

又 $a-qb=a'$ トスレバ， $a=a'+qb$ デアルカラ，同樣ニ $(a',b)$ ハ $(a,b)$ の約數デアル．

$m'$ を $a',b$ の最大公約数とすれば， $m'$ は $a'+qb$ の約数なので， $a'+qb,b$ の公約数です．よって $(a,b)$ の約数です．

コノヤウニ $(a,b)$ ト $(a',b)$ トハ各ガ他ノ約數デアルカラ，相等シイ．

「各」は「おのおの」の意味です．これで $(a,b)=(a',b)$ がめでたく証明できました．

手元の学習参考書には，最後の部分は「 $m\leqq m'$ かつ $m'\leqq m$ なので， $m=m'$ である」とあります．これもいいですね．

特ニ $a$ ヲ $b$ デ割ツタ剰餘ヲ $c$ トスレバ， $(a,b)=(b,c)$ ．

剰余には，最小正剰余*3と，絶対的最小剰余というものがありました．どちらの定義でも $a=bq+c$ が成り立つので， $(a,b)=(b,c)$ が成立します．

又 $b$ ヲ $c$ デ割ツタ剰餘ヲ $d$ トスレバ， $(b,c)=(c,d)$ ．

$d=b-qc$ となる $q$ が存在するので，確かにそうです．

コノヤウニ進ンデ行ケバ $a\gt b\gt c\gt d\gt....$ デアルカラ竟ニハ剰餘ガ $0$ ニナル．

$a,b$ が非負整数で， $a\geqq b$ のとき，非負整数列 $\{a_n\}$ を次のように定めます．ただし， $a\neq 0$ とします．

$a_0=a,a_1=b$
$a_n$ が $0$ でないとき， $a_{n+1}$ は $a_{n-1}=qa_n+a_{n+1},~0\leqq a_{n+1}\lt a_n$ を満たす唯一の整数
$a_n$ が $0$ のとき， $a_{n+1}$ 以降は定義しない

このとき $a_n\gt 0$ ならば $0\leqq a_{n+1}\lt a_n$ が成り立つので，確かに $a_1\gt a_2\gt \dots$ となり，数列 $\{a_n\}\ (n\geqq 1)$ は狭義単調減少です．また非負整数列でもあるので，添え字が $b$ 増加するまでには，つまり $n\leqq b+1$ の範囲には $a_n=0$ となる $n$ が存在します．

今 $c$ ガ $d$ デ割リ切レルトスレバ， $(c,d)=(d,0)=d$ 即チ $d=(a,b)$ .

$0$ でない任意の整数は $0$ の約数なので， $a_n=0$ のとき， $a_{n-1}$ が最大公約数になります．

コレガユウクリッドノ互除法デアル．

pythonで書いてみると次のようになります． $a,b$ は $a\geqq b\geqq 0$ を満たす整数で， $a\neq 0$ とします．

def func(a,b):
    if b==0:
        return a
    else:
        return func(b,a%b)

mathモジュールをインポートしてから

math.gcd(a,b)

でも十分です*4．

$a\gt b\gt 0$ のとき，整除を何回すればよいかについて考えてみます．最悪なケースは余りがなかなか小さくなっていかないとき，つまり商が常に1のときでしょう．例えば $(21,13)$ のときは， $(21,13)=(13,8)=(8,5)=(5,3)=(3,2)=(2,1)=(1,0)=1$ のように $6$ 回の整除をする必要があります．これは $(22,13)=(13,9)=(9,4)=(4,1)=(1,0)=1$ の $4$ 回よりも多いですね．

$f_0=1,f_1=1,f_{n+2}=f_{n+1}+f_n\ (n\geqq 0)$

で定まる数列 $\{f_n\}$ を定義して， $a_n=0$ となる $n\ (n\geqq 2)$ を $N$ とおきます． $2\leqq n\leqq N$ のとき $a_{n-2}\gt a_{n-1}$ より $a_{n-2}$ を $a_{n-1}$ で割った商は $1$ 以上なので，

$a_{n-2}\geqq a_{n-1}+a_n$

です． $a_N=0$ なので， $f_{n+2}=f_{n+1}+f_n$ と合わせて帰納的に考えると， $1$ 以上 $N$ 以下のすべての $n$ について

$a_{N-n}\geqq f_n$

が成り立ちます． $n=N$ とすると $a\geqq f_N$ が得られます．

つまり $N-1$ 回目の整除でユークリッドの互除法が終わるとしたら $a\geqq f_N$ であるということです．数列 $\{f_n\}$ に現れる整数であって， $a$ 以下の最大のものを $f_m$ とすれば， $N\leqq m$ が成り立ちます． $m\geqq 1$ のとき，

$f_m\geqq\left(\dfrac 32\right)^{m-1}$

であることが数学的帰納法によって分かるので， $m\leqq 1+\log_{\frac 32}a$ です． $\lfloor\log_{\frac 32}a\rfloor$ 回以内の整除で，ユークリッドの互除法が終わると言えるでしょう．

*1: $a_1,a_2,...,a_n$ が $b$ の倍数ならば， $x_1a_1+x_2a_2+\dots+x_nb_n$ は $b$ の倍数である．

*2: $a,b$ の任意の公約数は， $a,b$ の最大公約数の約数である．

*3:ここでは $0$ も含めていると思われる．

*4: $a=b=0$ のときはエラーを吐かず， $0$ が返ってくる．

2024-03-31

第一章初等整數論　§2最大公約數，最小公倍數（中編）

前回は，2つ以上有限個の，0でない整数の公倍数は最小公倍数の倍数であること[定理1.3]と，2つ以上有限個の，すべてが0ではない整数の公約数は，最大公約数の約数であること[定理1.4]を証明しました．

それでは読んでいきましょう．

次ノ定理ハ二ツノ整數 $a,b$ ニ關スルモノデアル．

これまでは2つ以上でしたが，ちょうど2つに限定した話になるようです．

[定理1.5]　 $a,b$ ノ最小公倍數ヲ $l$ ，最大公約數ヲ $m$ トスレバ，

$ab=lm$

（但 $a\gt 0,b\gt 0,l\gt 0,m\gt 0$ ．トスル．）

有名な定理です．例えば，ユークリッドの互除法を用いて2つの数の最大公約数を求めることができるので，これを用いて最小公倍数を求めることができます．

この定理も，素因数分解の一意性によらずに証明できるようです．

[證]　 $l$ ハ $a,b$ ノ公倍數デアルカラ

(1)

$l=ab'=ba$

トスル．

$l=ab'=ba'$ の誤植でしょう． $l=ab'=ba'$ となる $a',b'$ が存在する，ということです．

サテ $ab$ ハ勿論 $a,b$ ノ公倍數デアルカラ， $ab$ ハ $l$ ノ倍數デアル（定理1.3）．

定理1.3は，「公倍数は，最小公倍数の倍数である」というものです．確かに $ab$ は $l$ の倍数です．

由テ

(2)

$ab=dl$

トスル．

$ab$ は $l$ の倍数なので，これを満たす $d$ が存在します．

(1)カラ $l$ ニ代入シテ

(3)

$a=da',b=db'$

ヲ得ル．故ニ $d$ ハ $a,b$ ノ公約數デアル．

たとえば， $ab=dl$ に $l=a'b$ を代入して計算すると， $a=da'$ が得られます．同様に $b=db'$ が得られます． $d$ は $a$ の約数でもあり， $b$ の約数でもあるので， $a,b$ の公約数です．

あとは，これが最大の公約数であることを示せばよいです．

由テ $m=de$ トスル（定理1.4）．

定理1.4は，「公約数は，最大公約数の約数である」というものでした． $d$ は $m$ の約数なので，このような $e$ （ただし， $e\geqq 1$ ）が存在します． $e=1$ を示せばよいです．

然ルニ $a,b$ ハ $m$ デ割リ切レルカラ(3)ニ於テ $a',b'$ ハ $e$ デ割リ切レル．

$m$ が $a$ の約数であることから $a=ma''$ となる $a''$ が存在するので，(3)より $ma''=da'$ です．ここで $m=de$ なので， $ea''=a'$ です．よって $a'$ は $e$ で割り切れます．

$b'$ についても同様です．

由テ $a'=ea'',~b'=eb''$ トシテ(1)ニ代入スレバ

$l=ab''e=ba''e$ ．

代入するとこのようになります．

若シモ $e\gt 1$ ナラバ， $l/e\lt l$ ガ $a,b$ ノ公倍数ニナル．コレ不合理デアル．故ニ $e=1$ ，従テ $m=d$ ．

背理法を使っているようですが，使わなくてもいけそうです．

上の式から $e$ は $l$ の約数です． $\dfrac le=ab''=ba''$ より $\dfrac le$ は $a,b$ の公倍数なので， $\dfrac le\geqq l$ です．よって $e\leqq 1$ なので， $e=1$ です．

故ニ(2)カラ $ab=lm$ ．

うーむ．公約数や公倍数を弄繰り回しているだけで証明できてしまうのですね．

$a,b,c,...$ ノ最大公約數ヲ $(a,b,c,...)$ ナル記號デ表ハスコトニスル．

もちろん，有限個の整数の組の場合です．

$(5,-10,20)=5,~(0,57)=57,~(1,-1)=1$

のようになります．

$a,b,c,...$ ガ $\pm 1$ 以外ノ公約數ヲ有セヌトキニハ，略シテ $a,b,c,...$ ハ公約數ヲ有セヌトイフ．コノ場合ニハ $(a,b,c,...)=1$ ．

略しすぎな気もしますが，それだけ「 $\pm 1$ 以外の公約数を有しない」という場合が出てくるのでしょうね．

ともあれ， $\pm 1$ は任意の整数の約数であるので， $\pm 1$ は必ず公約数になります．これら以外の公約数が存在しないなら，最大公約数は $1$ です．

特ニ二ツノ整數 $a,b$ ガ公約數ヲ有セヌトキニハ， $a,b$ ヲ互ニ素トモイフ．

お馴染み，互いに素です．「公約数を有しない」は，「公約数が $\pm 1$ のみである」の略だったので，「2つの整数の最大公約数が $1$ のとき」と言い換えてもよいでしょう．

次ノ定理ハシバシバ引用サレルモノデアルカラ特ニ大切デアル．

[定理1.6]　 $(a,b)=1$ デ，且 $bc$ ハ $a$ デ割リ切レルナラバ， $c$ ガ $a$ デ割リ切レル．

素因数分解を考えれば当たり前な気もしますが，これを用いて素因数分解の一意性を証明するのだ，と聞いたことがあります．どうやら，整数や素数の定義によっては，これが成り立たないこともあるようなのです．

現在は整数として有理整数のみを考えているのですが，他の整数ではどうなるか楽しみですね．

[證]　假定ニ由テ $(a,b)=1$ デアルカラ， $a,b$ ノ最小公倍数ハ $ab$ デアル（定理1.5）．

定理1.5とは， $ab=lm$ というものでした． $l$ が $a,b$ の最小公倍数， $m$ が $a,b$ の最大公約数ですね．いま $m=1$ なので， $l=ab$ です．

然ルニ假定ニ由テ $bc$ ハ $a$ ノ倍數，従テ $a,b$ ノ公倍數デアルカラ $bc$ ハ $ab$ ノ倍数デアル（定理1.3）．

$bc$ は $a$ の倍数でもあり， $b$ の倍数でもあるので， $a,b$ の公倍数です．

定理1.3とは，「公倍数は最小公倍数の倍数である」というものでしたから， $bc$ は最小公倍数 $ab$ の倍数です．

故ニ $\dfrac{bc}{ab}=\dfrac ca$ ハ整數，即チ $c$ ハ $a$ デ割リ切レル．

$c$ が $a$ の倍数であることを示すには， $bc$ が $ab$ の倍数であることを示せばよい，ということでした．確かに $b$ の情報をどこかに入れなければならないので，当然と言えば当然だったかもしれません．

2024-03-29

第一章初等整数論　§2最大公約數，最小公倍數（前編）

前回は整除法について確認しました．整数 $a$ と正整数 $b$ に対して，

$a=bq+r,~0\leqq r\lt b$

を満たす整数 $q,r$ が一意に定まります． $r\gt 0$ のとき， $r$ を最小正剰余というのでした．また，

$a=bq+r,~|r|\leqq\dfrac b2$

を満たす整数 $q,r$ が存在します*1．このときの $r$ を絶対的最小剰余というのでした．

では読んでいきましょう．

1.　二ツ以上ノ整數 $a,b,...$ ニ共通ナル倍數（例ヘバ積 $ab...$ ナド）ヲソレラノ整數ノ公倍數トイフ．

お馴染みの公倍数の定義が述べられています．

§1では $0$ の倍数についてのみ定義していませんでしたから，ここでの $a,b,...$ は $0$ でない整数ということなのでしょう*2．

また，無限個の整数の組に $0$ でない共通の倍数が必ず存在すると言い切るにはちょっと怖いので，有限個の整数の組だと解釈しておきます．つまり，次のようになります．

$n$ を2以上の整数とする． $n$ 個の $0$ でない整数の組 $a_1,~a_2,~\dots,~a_n$ に，共通の倍数が存在する．これを公倍数という．

有限個からなる $0$ でない整数の任意の組について，公倍数は必ず存在します．例えば $0$ や， $a_1a_2\cdots a_n$ がそうです．

$0$ ハ公倍數デハアルガ，ソレヲ除ケバ，公倍數ノ中ニ最モ小（絶對値ニ於テ）ナルモノガアル．ソレヲ最小公倍數トイフ．

$a_1,~a_2,~\dots,~a_n$ のいずれも $0$ でなかったので， $a_1a_2\cdots a_n$ は $0$ ではありません．したがって $0$ でない公倍数が少なくとも1つ存在します．公倍数のうち絶対値が最小のものを最小公倍数という，ということです．

それだと $4$ と $6$ の最小公倍数は $\pm 12$ ってことになりますね．まじか！近くに具体例がないので，不安に駆られます．辞典の類を確認してみます．

手元の「数学小辞典　第2版」には「二つ以上の数の公倍数のうちで最も小さいもののこと．」（負の数や $0$ が考慮されていない）とあります．

また手元の「岩波数学辞典　第4版」には「いくつかの，どれかは $0$ ではない整数 $a_1,~a_2,~\dots,~a_n$ の共通な約数を公約数，共通な倍数を公倍数という．…正の公倍数のうちで最小のものを最小公倍数という．」（そもそも $0$ の倍数が定義されていない）とあります．この「最小の正整数」の方が馴染みがあります．

この最小公倍数の定義の差異についてはちょっとチェックしておくことにしましょう．

二ツ以上ノ整數 $a,b,...$ ニ共通ナル約數（例ヘバ $1$ ナド）ヲソレラノ整數ノ公約數トイフ．

お馴染みの公約数の定義です．約数の定義によれば， $0$ の約数は $0$ 以外のすべての整数なので，今回は $a,b,...$ として $0$ も許されます．

また，ここでも一応有限個の整数の組ということにしておきましょう．つまり，

$n$ を2以上の整数とする． $n$ 個の $0$ でない整数の組 $a_1,~a_2,~\dots,~a_n$ に，共通の約数が存在する．これを公約数という．

$1$ （と $-1$ ）は任意の整数の約数なので，有限個からなる整数の任意の組について公約数は存在します．

公約數ハ絶對値ニ於テ $a,b,...$ ヨリモ大ナルコトヲ得ナイカラ（ $a,b,...$ ガスベテ $0$ ナル場合ヲ除ケバ），ソノ中ニ最モ大ナルモノガアル．ソレヲ最大公約數トイフ．

定理1.1の前に「 $|a|\lt |b|$ で $a$ が $b$ の約数であるときは， $a=0$ ．」というものがありました． $a$ が $b$ の約数であるとき，この対偶をとると，

$a\neq 0$ ならば， $|a|\geqq|b|$ である．

となります．だから， $a$ が $0$ でないとき， $a$ の約数の絶対値は $|a|$ 以下です．よって $a_1,~a_2,~\dots,~a_n$ がいずれも $0$ でないとき，これらの公約数の絶対値は $\min\{|a_1|,~|a_2|,~\dots,~|a_n|\}$ 以下です．

公約数の数は有限個であることからこの中に最大値が存在します．これが最大公約数です．こちらは最小公倍数とは違って，正のもののみを指しているように読めます．

$a_1,~a_2,~\dots,~a_n$ に $0$ も $0$ でない整数も含まれているときは， $0$ でない整数のみをとってきます．このような整数が2つ以上あるときは，これらの最大公約数を求めれば，任意の整数は $0$ の約数なので，それが $a_1,~a_2,~\dots,~a_n$ の最大公約数ということになります．1つしかないときは，その数の絶対値が最大公約数です．

$a_1,~a_2,~\dots,~a_n$ がすべて $0$ のときは，任意の整数が $0$ の約数であることから最大公約数は存在しません．

本節デハ最大公約數及ビ最小公倍數ニ關スル基本的ノ定理ヲ述ベル．

節のタイトルにありますもんね．

事實トシテハ周知デアラウガ，往々無證明デ受ケ入レラレテヰルヤウデモアルカラ，コノ際反省ヲシテ見ルノモ無用デハアルマイ．

「反省」とは普通の捉え方を振り返って，それでよいか考えることです．

$a_1,~a_2,~\dots,~a_n$ の最大公約数は， $a_1,~a_2,~\dots,~a_n$ を素因数分解して，その指数部分の最小値を見ればよい，というような考え方は，中学・高校では証明なしで扱われているように思えます*3．こういうのもきちんと証明してみようというのです．

理論上デハ，最小公倍數ヲ先ニスル方ガ簡明デアル．

ほほう．

[定理1.3]　二ツ以上ノ整數ノ公倍數ハ最小公倍數ノ倍數デアル．

たとえば， $4,6$ の最小公倍数は $\pm 12$ ですが，公倍数 $\dots,{-36},-24,-12,0,12,24,36,\dots$ はすべて $12$ の倍数であるというのです．なんか当たり前だと思うのですが，なぜ当たり前かと言われると，素因数分解の一意性を根拠にしている気がします．

「最小公倍数」と言っているので，ここでの「2つ以上の整数」というのは「2つ以上有限個の，0でない整数」ということだと解釈します．

[證]　 $a,b,c,...$ ノ最小公倍數ヲ $l$ トシ $(l\gt 0)$ ， $m$ ヲ任意ノ公倍數トスル．

必要なものを文字で置いていきます． $l\gt 0$ という文言が見えますね．やはり，最小公倍数は正負どちらも入るので，ここでは正のものをとってきている，という解釈が正しいのでしょう．

ともかく，ここから $m$ が $l$ の倍数であることを証明すればよいです．

サテ

（定理1.2）

$m=ql+r,\quad 0\leqq r\lt l$

トスレバ

$r=m-ql$

デ， $m$ モ $l$ モ $a$ ノ倍數デアルカラ， $r$ ハ $a$ ノ倍數デアル（定理1.1）．

定理1.2というのは整除法のことで， $a$ は任意， $b\gt 0$ ならば， $a=bq+r,0\leqq r\lt b$ となる $q,r$ がただ一組存在する，というものです．

$r=0$ なら $m$ が $l$ の倍数であることが言えるので，一歩前進した感じがします．

また定理1.1というのは， $a_1,~a_2,~\dots,~a_n$ が $b$ の倍数ならば， $a_1x_1+a_2x_2+\dots+a_nx_n$ は $b$ の倍数であるというものです．今回は， $n=2$ ， $a_1=m,a_2=l$ ， $x_1=1,x_2=-q$ の場合ということです．

同様ニ $r$ ハ $b,c,...$ ノ倍數デアル．

上の議論は $a$ に限らず， $b$ でも $c$ でも成り立ちます．

即チ $r$ ハ $a,b,c,...$ ノ公倍數デアル．

まさに公倍数の定義に従っています．

$l$ ハ $a,b,c...$ ノ公倍數ノ中デ， $0$ ヲ除イテ最小絶對値ノモノデ， $r\lt l$ デアルカラ， $r=0$ ．即チ $m=ql$ ．

ここで最小公倍数の「最小である」という性質を使うのですね． $l$ が正の最小公倍数のとき， $0\lt r\lt l$ の範囲に公倍数はありません．うまいなあ．

これで素因数分解の一意性に依拠せずに，「公倍数は最小公倍数の倍数である」ことが示されました．

[定理1.4]　二ツ以上ノ整數ノ公約數ハ最大公約數ノ約數デアル．

例えば $36,48$ の最大公約数は $12$ ですが，他の公約数 $-12,-6,-4,-3,-2,-1,1,2,3,4,6,12$ はすべて $12$ の約数となっています．これがどんな場合にも成り立つと主張しています．

ここでも，「2つ以上の有限個の整数で，すべて $0$ ということはない」と解釈しておきます．

$a,b,c,...$ ノ最大公約數ヲ $m$ トシ， $d$ ヲ任意ノ公約數トスル．

必要なものを文字で置いていきます．こちらには $m\gt 0$ の文言はありません． $m$ は正の数であることは定義に従うからです．

然ラバ $d$ ガ $m$ ノ約數デアルトイフノハ， $m$ ト $d$ トノ最小公倍數ガ $m$ デアルトイフニ同ジイ．

「同じい」は現代では「同じだ」と言い換えられてしまうことが多い言葉です．

$d$ が $m$ の約数であるということは， $m$ と $d$ の（正の）最小公倍数が $m$ に一致するということと同値である，ということですね．

いちおう，説明してみます． $d$ が $m$ の約数のとき， $m=dq$ となる $q$ が存在します． $d$ と $dq$ の正の最小公倍数は $dq$ で，これは $m$ に等しいです．

逆に $m$ と $d$ の最小公倍数が $m$ のとき， $m$ は $d$ の倍数であり，これは $d$ は $m$ の約数であることと同じ意味です．

最小公倍数の話に持っていこうとしているみたいですね．

今 $l$ ヲ $m$ ト $d$ トノ最小公倍數トスル．

$m$ も $d$ も $0$ でない（ $0$ は約数にならない）ので，最小公倍数が存在します．これを $l$ とおいて， $l=m$ を示そうというのでしょう．

サテ假定ニ由テ $a$ ハ $m$ ノ倍數デアリ又 $d$ ノ倍數デアルカラ， $a$ ハ $m,d$ ノ公倍數，従テ $l$ ノ倍數デアル．（定理1.3）．

$m,d$ の公倍数 $a$ は最小公倍数 $l$ の倍数であることは，先程示した[定理1.3]によっています．

同様ニ $b,c,...$ モ $l$ ノ倍數デアル．

$a$ に限らず， $b,c$ でも同様の議論ができますから，その通りです．

故ニ $l$ ハ $a,b,c,...$ ノ公約数デアル．

まさに公約数の定義です．

故に $l\leqq m$ ．

$m$ は公約数のうち最大のものだったので， $l\leqq m$ です．

然ルニ $l$ ハ $m$ ノ倍数デアルカラ $l\geqq m$ ，故ニ $l=m$ ．

「然るに」は「それにもかかわらず」という意味の言葉です．

$m$ と $d$ の最小公倍数を $l$ としたので， $l$ は $m$ の倍数です．

$l\leqq m$ かつ $l\geqq m$ なので， $l=m$ が言えたわけですが，狐につままれた気持ちです．ともかくこれで公約数の方も，素因数分解の一意性によらずに証明することが出来ました．

*1: $b$ が偶数で， $a$ が $\dfrac b2$ の奇数倍のときは一意でないが，それ以外の場合は一意．

*2: $0$ の倍数は $0$ のみであると定めれば矛盾なく定義できると思うが，最小公倍数は存在しなくなる．

*3:素因数分解ができるのか，できたとして一意なのか，というところが怪しい（らしい）．

2024-03-13

第一章初等整數論　§1整數ノ整除（後編）

前回は $a$ の倍数の和や， $a$ の倍数の倍数は， $a$ の倍数であることを証明しました．

次ノ定理ハ基本的デアル．

[定理1.2]　 $a$ ハ任意ノ整數デ， $b\gt 0$ ナラバ，

$a=bq+r,0\leqq r\lt b$

ヲ滿足セシメル整數 $q,r$ ガ唯一組ニ限テ存在スル．

除法の原理ですね．例えば $a=13,b=4$ とすると

$13=4q+r, 0\leqq r\lt 4$

を満たす $q,r$ の組は $q=3,r=1$ の唯一つです．これを小学校の算数以来，「 $13$ を $4$ で割ったときの商は $3$ で，余りは $1$ である」と表現してきました．

$a$ が負の数でも同様に商や余りを定義することができます． $a=-13,b=4$ とすると

$-13=4q+r, 0\leqq r\lt 4$

を満たす $q,r$ の組は $q=-4,r=3$ です．

無数の計算練習によって， $a,b$ が与えられたとき，このような $q,r$ の組は一通りであることはほとんど実感できていますが，証明できるようです．

[證]　 $b$ ノ倍數ヲ

$\ldots\ldots,{-3b},{-2b},{-b},0,b,2b,3b,\ldots\ldots$

ノヤウニ大サノ順序ニ並ベルト，ソレラノ中ニハ絶對値ニ於テ如何程デモ大キイモノガアルカラ，實數 $x$ ノ全範圍ガ

$qb\leqq x\lt (q+1)b$

ノヤウナ無数ノ區間ニ分タレル．

実数を互いに交わらない半開区間に分けたようです．例えば $b=4$ なら，

$\ldots\ldots-8\leqq x\lt-4,-4\leqq x\lt 0,0\leqq x\lt 4,4\leqq x\lt 8,8\leqq x\lt 12,\ldots\ldots$

のように分けたような感じでしょう．

$a$ ハコレラノ區間ノ中ノ唯一ツニ属スルカラ

$qb\leqq x\lt(q+1)b$

ニナルヤウナ $q$ ガ存在スル．

唯一つに属する，というのがミソですね．

然ラバ

$a-bq=r$

ト置クトキ，

$0\leqq r\lt b.$

まったくその通りですね．実際， $13$ を $4$ で割った商と余りを求めるときは， $4q\leqq 13\lt 5q$

すなわち $\dfrac{13}4$ 以下で最大の整数 $q$ を求め， $r=13-4q$ として余りを求めています．操作的な証明ですね．

しかし実数を無数の区間に分けるのではなく，整数を無数の区間に分けるのではいけなかったのでしょうか？

いや，これによって実数にも商と余りが定義できるようになるのでしょうか．うーん．

$q,r$ ガ唯一組ニ限テ存在スルコトモ明白デアルガ，念ノ爲ニ證明スレバ次ノ通リ．

確かに，他の $q$ （ $\dfrac ab$ 以下で最大の整数でない $q$ ）であって，

$a=bq+r,0\leqq r\lt b$

である $r$ が存在しないことを明確に証明してはいませんでした．

若シモ

$a=qb+r,\qquad 0\leqq r\lt b$

$a=q'b+r',\qquad 0\leqq r'\lt b$

トスレバ

$(q-q')b=r'-r$

即チ $r'-r$ ハ $b$ デ割リ切レル．

一意性の証明の際は，「二つあるとして考えてみたけど，やっぱり一つだったよ」の形の証明が有効です． $a$ を消去してみると $r-r'$ が $b$ の倍数であることが言えます．ふむふむ．

然ルニ假定ニ由テ $|r'-r|\lt b$ ．故ニ $r'-r=0$ ，従テ $q-q'=0$ ．即チ $q=q',r=r'$ ．

前編で証明した定理「 $|a|\lt |b|$ で $a$ が $b$ で割り切れるときは， $a=0$ である．」を早速使っています．もっと言い換えると， $-b\lt a\lt b$ の範囲に $b$ の倍数は $0$ しかないので， $a=0$ です．

めでたくこれで唯一であることも言えました．除法の原理が証明できました！

整数 $a$ と正整数 $b$ が与えられたら， $a=bq+r,0\leqq r\lt b$ を満たす $q,r$ が一意に定まります．これを求める演算を整除法，剰余付き除法などと言うようです．

[例]　 $b=12$ トスレバ，

$a=50$ ノトキ， $q=4,r=2.$

$a=-50$ ノトキ， $q=-5,r=10.$

$a=-5$ ノトキ， $q=-1,r=7.$

例示ですね．他にも， $a=5$ なら $q=0,r=5$ となりますし， $a=12$ なら $q=1,r=0$ となります．

定理1.2ニ於テ $r=0$ ナルトキガ，即チ $a$ ガ $b$ デ割リ切レル場合デアル．

$r=0$ ならば $a=bq$ だし， $a=bq$ であるなら $r=0$ なので，疑いありません．

$r\gt 0$ ナルトキニハ， $r$ ヲ「 $b$ ヲ法トシテノ $a$ ノ最小正剰餘」トイフ．

「あまり」が $0$ でないときは，「最小正剰余」というようです．「余」は「餘」の略字みたいです．

又 $q$ ハ $\dfrac ab$ ヨリモ大デナクテ，ソレニ最モ近イ整数デアル．

$\dfrac ab$ より大でない，ということは $\dfrac ab$ 以下ということです．つまり

$q\leqq\dfrac ab$ を満たす最大の整数ということです．

一般に實數 $x$ ヨリモ大ナラザル最大ノ整数ヲ $[x]$ デ表スコトガアル（ガウスノ記號）．

ガウス記号です．床関数 $\lfloor x\rfloor$ と呼ばれることもあるでしょう．床関数はwikipediaによれば1962年に導入されたそうなので，この本には登場していません．

然ラバ $q=\left[\dfrac{a}{b}\right]$ ．

商 $q$ は $a,b$ が決まれば一意に決まるので，これを表す記号があるのは大きいですね．ちなみにpythonなどのプログラミング言語では， $q$ はa//bで， $r$ はa%bで表します．

しかし頑なに「 $q$ を商， $r$ を余りという」みたいな文言が出てこないですね．もしかしたら，特に名前はついていなかったのかもしれません．

若シモ $a/b$ ヨリ大キクテモ，小サクテモ，ソレニ最モ近イ整數ヲ $q$ トスルナラバ

$\left|\dfrac ab-q\right|\leqq\dfrac 12$ ．

これまでの $\left[\dfrac{a}{b}\right]$ に等しい $q$ とは異なるようです．

どんな実数も，何かの整数から $\dfrac 12$ より大きくは離れていませんから，それはそう，ということになります．実数を覆いつくすように

$\ldots\ldots,~{-\dfrac 12\leqq x\leqq\dfrac 12},~\dfrac 12\leqq x\leqq\dfrac 32,~\dfrac 32\leqq x\leqq\dfrac 52,\ldots\ldots$

のような閉区間に分割して考えれば， $\dfrac ab$ はこのいずれかには属すので，そこに含まれる整数を $q$ とした，ということでしょう．

整数からの距離が $\dfrac 12$ より小さいと隙間ができてしまうので， $\dfrac 12$ が実数を覆いつくすことができる最小の数です．

ソノトキ $a-bq=r$ トオケバ， $|r|\leqq\dfrac b2$ ．

これは計算しただけです．

$\left|\dfrac ab-q\right|=\dfrac{|a-bq|}b=\dfrac{|r|}b\leqq\dfrac 12$

なので，

$|r|\leqq\dfrac b2$

が得られます．当然 $r$ は整数です．

故ニ

$a=bq+r,~|r|\leqq\dfrac b2$

ニナルヤウナ $q,r$ ハ必ズアルガ，コノ場合ニハ $q,r$ ガ二組生ズルコトモアル．

さきほど最小正剰余を考えたときは $q,r$ がただ一組でしたが，今回は一組とは限りません．それは $\dfrac ab$ に最も近い整数が2つ存在するときです．たとえば $\dfrac 52$ は $2$ とも $3$ とも距離が等しく， $q$ としてどちらも取り得ます．

ソレハ $b$ ガ偶數デ， $a$ ガ $\dfrac b2$ ノ奇數倍ナル場合デアル．

$\dfrac ab=\dfrac c2$ であり， $c$ が奇数となる場合なので，まあそうでしょう． $a=\dfrac{bc}2$ で， $b$ が奇数だとすると $bc$ も奇数なので $a$ が整数であることに反します．よって $b$ は偶数でなければならず，このとき $a=\dfrac b2\cdot c$ なので $\dfrac b2$ の整数倍です．

$a=(2h+1)\dfrac b2$ ナラバ， $q=h,r=\dfrac b2;$ 又ハ $q=h+1,r=-\dfrac b2$ ．

$a=bh+\dfrac b2$ のとき， $q=h$ としても $q=h+1$ としても $|r|\leqq\dfrac b2$ です．

上記ノヤウニ， $|r|\leqq\dfrac b2$ ナル $r$ ヲ「 $b$ ヲ法トシテノ $a$ ノ絶對的最小剰餘」トイフ．

絶対的最小剰余．最小正剰余の場合は $|r|\leqq b$ だったので， $r$ の絶対値が小さくなっています．その代わりに $r$ として負の値が出てきたり，唯一性が失われたりしています．特に $r=0$ の場合が除外されているわけではないので， $r=0$ のときも $r$ を絶対的最小剰余と言う，ということなのでしょう．

[例]　 $b=12$ ノトキ，

$a=70$ ナラバ， $q=6,~r=-2.$

$a=-67$ ナラバ， $q=-6,~r=5.$

$a=30$ ナラバ， $q=2,r=6$ 又ハ $q=3,r=-6.$

例が載っています． $q$ は $\dfrac ab$ に最も近い整数をとっていけばよいので， $\dfrac{70}{12}=\dfrac{35}6=5.833\dots$ より $q=6$ で， $r=a-bq=-2$ です．

また $\dfrac{-67}{12}=-5.583\dots$ より $q=-6$ で， $r=a-bq=5$ です．

$\dfrac{30}{12}=\dfrac 52=2.5$ より $q=2,3$ で， $r=a-bq=6,-6$ です．

2024-03-01

第一章初等整數論　§1整數の整除（前編）

序文によれば，有理整数（有理数であって，整数であるもの）だけで考察できるのが，第一章なのでした．

1.　本章デハ整數ノ整除，倍數，約數ナドニ關スル最モ卑近ナル理論ヲ述ベル．

整除というのは，いわゆる「割り切れる」というやつです．倍数，約数はさすがに分かります．序文は漢字かな交じりだったのに，本文は漢字カナ交じりなんですね．

中ニハ周知ノ事項モアラウガ，一應根本カラ系統的ニ考察ヲシテオク必要ガアル．

それはそうですね．

本章デハ文字ハ必ズ整數ヲ表ハスノデアルカラ，一一ソレヲ斷ラナイ．

文字は必ず整数． $a$ とか $b$ とかのラテンアルファベットのことであって，ひらがなやカタカナのことではないでしょう．

尤モ整数トイウノハ

$\ldots\ldots{-3},-2,-1,0,1,2,3,\ldots\ldots \$

等，正及ビ負ノ整數ト $0$ トヲ總括シテ言フノデアル

$0$ から始まって， $1$ ずつ増やしていくと $0,~1,~2,~3,\dots$ となり，減らしていくと $0,~{-1},~{-2},~{-3},\dots$ となるのでした．よく知っている整数を具体的に述べています．

整數ノ和，差及ビ積ハ整數デアルガ，商ハ特別ナル場合ノ外ハ整數デナイ．

整数の和，差，積は整数です．ここでは認めてしまって先を急ぎます．

商が整数になったり整数にならなかったりするのは，具体例を示してしまえばよいですね．たとえば $2$ を $1$ で割ると $2$ となってこれは整数ですが， $1$ を $2$ で割ると $\dfrac 12$ となって，これは整数ではありません．

商 $a/b$ ガ整数 $q$ ニ等シイトキ，即チ

$a=bq\ (b\neq 0)$

ノトキ， $a$ ハ $b$ デ割リ切レルトイフ．

むむむ，違和感のある文です．「 $a$ は $b$ で割り切れる」は， $a,b$ に関する条件なのに，「 $a=bq\ (b\neq 0)$ 」は $a,b,q$ に関する条件です．後半は，「 $a=bq\ (b\neq 0)$ となる $q$ が存在するとき」という感じでしょうか．述語論理に毒されすぎでしょうか…

ともかく， $a/b$ が整数なら， $a$ は $b$ で割り切れるのでした． $6$ は $2$ で割り切れます，なぜなら $6/2=3$ だからです．みたいな意味ですね． $\dfrac ab$ と $a/b$ は同じ意味です．

又 $a$ ヲ $b$ ノ倍數， $b$ ヲ $a$ ノ約數トイフ．

まったくその通りです．先の例でいえば， $6/2=3$ なので $6$ は $2$ の倍数だし， $2$ は $6$ の約数です．

コノ定義ニ由レバ， $0$ ハ任意ノ整數 $b$ （但 $b\neq 0$ ）ノ倍數デアル．

$0$ でない任意の整数 $b$ に対し， $\dfrac 0b=0$ です． $0$ は整数なので確かに $0$ は任意の（ $0$ でない）整数の倍数だと言えますし，任意の（ $0$ でない）整数は $0$ の約数だと言えます．

$0$ は $0$ の倍数でしょうか．それは定義されていないので何とも言えません．定義する必要があるときに定義すればよいでしょう．

又 $|a|\lt|b|$ デ $a$ ガ $b$ デ割リ切レルトキハ， $a=0$ ．（ $\left|\dfrac ab\right|\lt1$ ガ整數デアルカラ，ソレハ $0$ ，從テ $a=0$ ．）

んん，一気に複雑になった気がします．大雑把に言えば， $a,b$ が正の整数のとき， $b$ より小さい整数 $a$ が $b$ の倍数になるのは， $a=0$ のときしかありえない，と言っているようです．

証明はカッコ内にありますね． $\dfrac{|a|}{|b|}=\left|\dfrac ab\right|\lt 1$ だから $-1\lt\dfrac ab\lt 1$ です． $\dfrac ab$ は整数なので $\dfrac ab=0$ です．よって $a=0$ です．

次の問題は「数学オリンピック事典」という本に載っていた問題です．

$11x+1$ が $x^2+3$ の倍数となるような正の整数 $x$ をすべて求めよ．

$x$ が大きいとき $11x+1\lt x^2+3$ となるので， $x$ の範囲を絞り込めそうです*1．

$11x+1$ は $0$ にならないので， $11x+1\geqq x^2+3$ でなければなりません．つまり $1\leqq x\leqq 10$ であることが必要です．このとき $11x+1$ が $x^2+3$ の倍数となるような $x$ を調べ上げれば， $x=1,5$ であることが分かります．

こんな感じで， $a$ が $b$ の倍数であるとき， $|b|$ が $|a|$ より小さくなるような $b$ が有限個しかないときは，時間さえかければ解決するはずです．

[定理1.1]　或ル整數ノ倍數ノ和，又ハ倍數ノ倍數ハソノ整數ノ倍數デアル．一般ニ $a_1,a_2,\cdots,a_n$ ガ $b$ ノ倍數ナラバ，

$a_1x_1+a_2x_2+\dots+a_nx_n$

ハ $b$ ノ倍數デアル．

$a$ の倍数同士の和や， $a$ の倍数の整数倍は， $a$ の倍数です．当然な気がしてきます．定義に従って証明します．

[證]　 $\dfrac{a_1x_1+a_2x_2+\ldots+a_nx_n}b=\dfrac{a_1}bx_1+\dfrac{a_2}bx_2+\ldots+\dfrac{a_n}bx_n$

デ，假定ニ由テ右邊ハ整数ノ和デアルカラ．

ある数 $a$ が $b$ の倍数であるかどうかは， $\dfrac ab$ が整数であるかどうかを見ればよいのでした．ここでは

$\dfrac{a_1x_1+a_2x_2+\ldots+a_nx_n}b$

が整数であるかどうかが問題です．分配法則によって

$\dfrac{a_1x_1+a_2x_2+\ldots+a_nx_n}b=\dfrac{a_1}bx_1+\dfrac{a_2}bx_2+\ldots+\dfrac{a_n}bx_n$

とできます．ここで右辺に現れる $\dfrac{a_1}b,~\dfrac{a_2}b,~\dots,~\dfrac{a_n}b$ は整数であり，整数の積や和は整数であるので， $\dfrac{a_1x_1+a_2x_2+\ldots+a_nx_n}b$ も整数です．

*1:これが逆だと絞り込めず，無数の $x$ についての探索になってしまう．このようなときは別の手段に頼ることになるだろう．