第一章初等整數論　§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$ 以上なので，