香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp 情報数学１ 第1-2章 最大公約数とユークリッドの互除法 香川大学工学部 富永浩之 tominaga@eng.kagawa-u.ac.jp

概 要 ■ 最大公約数の性質 ■ ユークリッドの互除法の漸化式と計算過程 ■ 互除法の剰余列とアルゴリズム 概 要 ■ 最大公約数の性質 整除関係 互いに素 公約数 公倍数 GCD LCM ■ ユークリッドの互除法の漸化式と計算過程 gcd(a,b) 初期条件 漸化式 ■ 互除法の剰余列とアルゴリズム 剰余列 機械性と停止性 手続と算法 ■ 互除法の効率性と最小剰余による改良 最小剰余 ■ 互除法の図形的意味とブレントの算法 二コマコスの算法 ブレントの算法

第01節 [1] 公約数と公倍数 6の約数 ±1, ±2, ±3, ±6 1は全ての約数 6の約数 ±1, ±2, ±3, ±6 1は全ての約数 6の倍数 0, ±6, ±12, ±18, ‥ 0は全ての倍数 12と18の公約数 1, 2, 3, 6 10と15の公倍数 0, 30, 60, 90, ‥ 最大公約数 GCD [Greatest Common Divisor] gcd(a,b) gcd(12,18)＝6 最小公倍数 LCM [Least Common Multiple] lcm(a,b) lcm(10,15)＝30 ・ 約数と倍数は符号付で考えることがある ・ 公約数の約数は公約数、公倍数の倍数は公倍数

第01節 [2] 整除関係と互いに素 整除関係 a｜b bがaで割り切れる aがbの約数、bがaの倍数 1≪3≪6≪12≪0 互いに素 a⊥b aとbのGCDが1 整数の性質を調べる上での基本の場合 余因数 a,bに対し、GCDで割った整商 gcd(a,b)＝d とおくと a’＝a/d, b’＝b/d a＝a’d, b＝b’d かつ a’⊥b’ 整数の様々な性質の証明に用いる

第02節 [1] 最大公約数の性質 <1> gcd(a,b) ＝ gcd(b,a) 交換律 <2> gcd(-a,b) ＝ gcd(a,b) 符号無視 <3> gcd(a,1) ＝ 1 1は全ての約数 <4> gcd(a,0) ＝ a 0は全ての倍数 (a＞0) <5> gcd(ka,kb) ＝ k×gcd(a,b) 共通因数の括出し (k＞0) <5>’ gcd(ab,b) ＝ b 整除関係 (b＞0) <6> gcd(a,b) ＝ gcd(a-b,b) 差への還元 <6>’ gcd(a,b) ＝ gcd(a%b,b) 剰余への還元 (b≠0) <5> gcd(42,30)＝gcd(6×7,6×5)＝6×gcd(7,5)＝6×1＝6 <6> gcd(42,15)＝gcd(27,15)＝gcd(12,15) ＝gcd(15,12)＝gcd(3,12)＝3

第02節 [2] 目の子の筆算によるGCDの計算 2 | 84 60 2 | 42 30 3 | 21 15 ーーーーーー × 7 5 2 | 84 60 2 | 42 30 3 | 21 15 ーーーーーー × 7 5 12 ⊥ gcd(84,60) ＝ gcd(42,30)×2 ＝ gcd(21,15)×2×2 ＝ gcd( 7, 5)×3×2×2 ＝ 1×3×2×2 ＝ 12 ・ GCDの性質<5> 共通因数の括出し を利用している ・ 筆算は、式変形の本質的な部分のみを抜き出している ・ 目の子(人間の直感)で、共通因数を見つけている ・ 小さい数には有効だが、大きい数には歯が立たない ・ 機械的な処理手順ではないので、プログラムとして書きにくい ・ 全ての数で順に割り切れるか調べる方法は、効率が非常に悪い

第03節 [1] 最小公倍数の性質 <1> a⊥b のとき lcm(a,b) ＝ a×b <2> 余因数の括出し lcm(a,b) ＝ a’×b’×gcd(a,b) <3> 共通因数の括出し lcm(ka,kb) ＝ k×lcm(a,b) <4> 積の公式 a×b ＝ gcd(a,b)×lcm(a,b) ・ LCMは、2数の積をGCDで割って求めることができる ・ 実際の計算では、オーバーフローを防ぐため、 一方をGCDで割ってから、他方を掛ける ・ 正整数の組 a,b に対し、GCDとLCMの値が分かれば、 一方 a から他方 b が一意に求められる

第04節 [1] ユークリッドの互除法の定義 gcd(a,b) ＝ { a ; b＝0 { gcd(b,a%b) ; else 古代ギリシャの数学者ユークリッドが発見(?) 世界最古の算法(アルゴリズム) ‥機械的な計算手順 gcd(a,b) ＝ { a ; b＝0 { gcd(b,a%b) ; else gcd(51,36)＝gcd(36,15)＝gcd(15,6)＝gcd(6,3)＝gcd(3,0)＝3 gcd(3,5)＝gcd(5,3)＝gcd(3,2)＝gcd(2,1)＝gcd(1,0)＝1 初期条件 性質<4> gcd(a,0)＝a より 漸化式 性質<6>’ gcd(a,b)＝gcd(a%b,b) より 性質<1> gcd(a%b,b)＝gcd(b,a%b) より

第06節 [1] 互除法の図形的意味 gcd(8,6)＝2 lcm(3,2)＝6 gcd(17,7)＝gcd(7,3)＝gcd(3,1)＝1 8×6の長方形を覆う、 最大の正方形のタイルは 2×2 ⇒ GCD 3×2のタイルを並べて、 覆える最小の正方形は 6×6 ⇒ LCM 長方形から最大サイズ (短辺)の正方形を 取れるだけ除く ⇒ <6>’ 縦横を置き換えて、 同様に繰り返す ⇒ <4> 残余がなくなれば、 そのサイズがGCD ⇒ <1> gcd(17,7)＝gcd(7,3)＝gcd(3,1)＝1

第04節 [2] ユークリッドの互除法の計算過程 k a b q r 0 48 ÷ 34 ＝ 1 ‥ 14 gcd(48,34) ------------------------------ 0 48 ÷ 34 ＝ 1 ‥ 14 gcd(48,34) 1 34 ÷ 14 ＝ 2 ‥ 6 ＝ gcd(34,14) 2 14 ÷ 6 ＝ 2 ‥ 2 ＝ gcd(14, 6) 3 6 ÷ 2 ＝ 3 ‥ 0 ＝ gcd( 6, 2) 4 2 0 ＝ gcd( 2, 0) 4回の再帰呼出 ＝ 2

第05節 [1] 互除法の剰余列 計算 gcd(48,34)＝gcd(34,14)＝gcd(14,6)＝gcd(6,2)＝gcd(2,0)＝2 剰余列 48, 34, 14, 6, 2, 0 0で終わる有限の数列 34, 48, 34, 14, 6, 2, 0 a＜b のときは b, a と入替え 回 1 2 3 4 5 20 11 9 12 8 13 7 6 14 15 16 17 18 19 10

第05節 [2] 互除法の剰余列の漸化式 gcd(a,b) の計算における剰余列 N(k) の定義 初期条件 N(0) ＝ a, N(1) ＝ b ; 与数 漸化式 N(k) ＝ N(k-2) % N(k-1) ; k≧2, N(k-1)＞0 終了条件 N(p+1) ＝ 0 ; 列長 p+2 剰余条件より 狭義単調減少 N(1)＞N(2)＞‥＞N(p)＞N(p+1)＝0 GCDの性質より gcd(a,b)＝gcd( N(k), N(k+1) )＝N(p) while ( b != 0 ) { t = b; b = a%b; a = t; } n[0] = a; n[1] = b; k = 1; while ( n[k] != 0 ) { k++; n[k] = n[k-2] % n[k-1]; }

第05節 [2] アルゴリズムの条件 ● 機械性 ‥ 手続 [procedure] ・ 個々の処理が厳密に定義されていて、機械的に実行できる ・ 同じ入力に対し、いつ誰が計算しても、同じ出力となる ● 停止性 ‥ 算法 [algorithm] ・ 有限な入力に対し、有限回のうちに手順が必ず終了する ・ 真の乱数は、アルゴリズムでは作れない(疑似乱数) ・ 機械的であるが止まらない手続が存在する(無限ループ) ・ 止まるか止まらないか未だに分からない手続きも存在する ■ 互除法がアルゴリズムであること ○ 機械性 数学的な漸化式で定義されている ○ 停止性 剰余列が狭義単調減少で必ず0で終了する

第06節 [2] 最小剰余による効率化 ● 互除法の計算回数の最悪ケース ● 互除法の漸化式を効率化 整商が1しか立たず、大きな剰余が残ると、計算が進まない すなわち、 N(k)＝N(k-1)%N(k-2)＝N(k-1)-N(k-2) のとき これは、フィボナッチ数列を逆順にした数列 ● 互除法の漸化式を効率化 剰余列の次項を最小剰余で考え、性質<2>より符号無視 正剰余で次項が除数の1/2超のとき、最小剰余では1つ飛越し 正 13, 8, 5, 3, 2, 1, 0 4回 13 ÷ 8 ＝ 1 ‥ +5 最小 13, 8, 3, 1, 0 2回 13 ÷ 8 ＝ 2 ‥ -3 【例題】 621, 323, (298), 25, (23), 2, 1, 0

第07節 [1] ニコマコスの算法 ● ニコマコスの算法 ● ブレントの算法 ・ ユークリッドの互除法より以前に用いられた算法 ・ a＞b のとき gcd(a,b)＝gcd(b, a-b) とする ・ 負荷の高い除算の代わりに、減算を使った漸化式を考える ・ a,bの桁数が異なると、大量の減算が必要となり、効率的でない ・ 除算の実装は、実際には二進数の減算の繰返しなので、 うまく改良できれば効率化できるかも ● ブレントの算法 ・ 二進数同士のGCDを高速に行う算法 ・ 2で割る(最下位桁の0を取り除く)ことと減算だけを使う ・ gcd(a,b)＝gcd(a',b')×2↑e とし、奇数となる gcd(a',b') に着目

第07節 [2] ブレントの算法 ・ 事前処理として、下位桁の共通の0を取り除く(2↑eで割る) ・ さらに一方のみの0も取り除く(2は共通因数にならないので無視) ・ 大きい方から小さい方を引く(ニコマコスの算法) ・ 差が0(両者が一致)になれば、直前の値がGCD'になっている ・ 上位桁というより下位桁から減らしていく方法 ・ 1回の減算で必ず1桁以上が減るので、log2(a) の計算量となる ・ 負荷の高い除算を使わないので、ビットレベルの実装を工夫すれば、 ユークリッドの互除法よりも高速 164 10101000[2] ⇒ 101010 ⇒ 10101 ⇒ 10101 ⇒ 10101 ⇒ 10010 ⇒ 1001 ⇒ 110 ⇒ 11 二進数 前処理 移動 減算 移動 減算 移動 一致 00 4× 3 ＝ 12 二進数 前処理 減算 移動 一致 10000100[2] ⇒ 100001 ⇒ 100001 ⇒ 1100 ⇒ 11 ⇒ 11 ⇒ 11 ⇒ 11 ⇒ 11 132

第00節 [1] ユークリッドの不定方程式 ユークリッドの一次不定方程式 23x－10y＝-2 を満たす具体解を1つ求めよ。 整除演算 23÷10＝2‥3 より、 23x－10y＝10(2x－y)＋3x と式変形し、 z＝2x－y とおいて変数変換を行い、小さな係数の方程式 10z＋3x＝-2 に帰着させる。 ユークリッドの互除法のように、 この操作を続け、一方の係数が1となる自明な方程式の 具体解(他方の解は0)を求める。変数変換を逆算しながら、各変数を求めていく。 整除演算 [ 10÷3＝3‥1 ] より、 [ 10z＋3x＝3(3z＋x)＋z ] と式変形し、 [ w=3z＋x ] とおいて変数変換を行い、 小さな係数の方程式 [ 3w＋z＝-2 ] に帰着させる。 ここで、 zの係数が1となり、自明な具体解 w＝ [ 0 ], z＝ [ -2 ] を得る。 変数変換の式を逆算し、 x= [ w－3z ], y＝ [ 2x－z ] から、 具体解 x＝ [ 6 ], y＝ [ 14 ] を得る。 与式を図形の方程式とみると、具体解は、直線 L : 23x－10y＝-2 上の 格子点(XY座標がともに整数の点)になっている。 直線の傾きを考えると、xが10増えれば、yは23増えるという関係になっている。 よって、他の具体解として、 x＝ [ 16 ], y＝[ 37 ] や、 x＝ [ 26 ], y＝ [ 60 ] が挙げられる。