第一章初等整數論　§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$ ．