の約数を調べ挙げるため素因数分解をしよ 整数教材としての Euclid 互 除法と連分数について うとするだろう。奇素数 3,5, 7,11,13,17 で 次々に割ってゆき、 527 3117 を見つけ る。 527 22.956 だから 19 までで見 つかるはずである。 次に、 1147 を 17 または 31 で割って 林 雄 一 郎 1147 31 37 を得る。さらに、 37 と 17 に公約数があるか否かチェックする。 17 4.123 だから奇素数 3 で 17,37 を 1 はじめに 久しぶりに高校数学「数学A」に導入され た Euclid の互除法は人類最古のアルゴリズ ムであり、B.C.300 年頃に記された Euclid の原論第7巻命題1に記載されている。ギリ 割り、公約数は 1 しかないことを知り、 31 が最大公約数であると判断するだろう。 以上の操作で必要な割り算の回数は、合計 6 2 2 10 回 となる。 一方、Euclid の互除法を使った場合は シャ数学はバビロニア数学のように代数が 発達していなかったから図形の辺の長さで 1147 2 527 93 表されている。この互除法は連分数の考え方 527 5 93 62 と同じであり、また数の連分数展開から無理 93 1 62 31 62 2 31 数への理解が一層深まるのである。 本稿では、Euclid の互除法と不定方程式、 連分数と関連する幾つかのトピックスを紹 介し、 「整数の性質」の単元にかかわる整数 論の話題を提供し、高校数学における発展的 な整数教材について考察する。 計 4 回の割り算で済み、互除法の効率の良 さを納得することになる。 整数 a , b の最大公約数 gcd a, b を求め る Euclid の互除法は次のようなアルゴリズ 2 Euclid の互除法について 公約数の考えは小学校5年生から学ぶ。例 えば、横 24cm、縦 18cmの長方形の厚紙 がある。これを余り屑が出ないように、しか も出来るだけ大きな正方形に分けるとき、何 センチメートルの正方形にすればいいか? という問題を考えるとき最大公約数の考え に自然に導かれるだろう。 ところで、例えば 527 と 1147 の最大公約 数を求めたいとする。児童らはこの2つの数 ムの形式で表される(Knuth,1972) 。 二つの整数 a, b a b に対して E1. a を b で割り、余り r 0 r b とする E2. r 0 ならば終了し、 b gcd a, b r 0 ならば E3.に行く E3.代入操作 a b, b r E1.に戻る 2-1 E1~E3 の各操作では常に最大公約数 a は有理数とする。 a を b で割り、商を k0 b 余りを x2 とおく。 a x0 , b x1 とする。以 が保存される。 gcd a, b gcd b, r 下、互除法の操作 E1~E3 を続ける。 x1 x2 0 だから、この操作は m (証) gcd a, b d とおき、 回で終了し、アルゴリズムは停止する。 a da , b db a, b は互いに素とする。こ 約数になる。もし d の約数でなければ a, b a x0 k0 x1 x2 b x1 k1 x2 x3 x2 k2 x3 x4 の公約数となり矛盾する。E1 の操作で商を ・・・・・・・・・ のとき a , b の任意の公約数 s 1 は d の xm 2 km 2 xm 1 xm 0 xm xm 1 xm 1 km 1 xm xm 1 0 q とすれば、 d は b, a bq r の約数だから gcd b, r の約数である。 gcd xi 1 , xi gcd xi , xi 1 一方、 gcd b, r は b, r の約数だから、 i 1, 2, , m 1 xm gcd a, b bq r a , b の公約数となり、 d の約数で ある。 以上を例1の場合で確認してみる。 割る数、割られる数の系列 xi は 具体的な数で互除法を実行してみる。 例1 0 x2 x1 0 x3 x2 0 x4 x3 1147,1071 の最大公約数を求める。 x0 , x1 , x2 , x3 , x4 , x5 1147,1071, 76, 7, 6,1 互除法の操作は次の5回になる。 商となる数の系列 k j 1147 1 1071 76 1071 14 76 7 は k0 , k1 , k2 , k3 , k4 1,14,10,1, 6 76 10 7 6 7 1 6 1 6 6 1 これらの数の生成にはどういうカラクリが 潜んでいるだろうか?という疑問が湧いて くるだろう。それを考察してみる。 gcd 1147,1071 1 2-2 このとき次式が成り立つ。 まず a , b を xi i 2,3, m で表わ すことを考える。 gcd 1147,1071 gcd 1071, 76 gcd 76, 7 gcd 7, 6 1 以上を一般的に表現する。整数 a, b を考え、 2 これを用いると a x0 b x1 qn xn qn 1 xn 1 ・・・② k0 x1 x2 と予想できる。 k0 k1 x2 x3 x2 1 k0 k1 x2 k0 x3 1 k0 k1 k2 x3 x4 k0 x3 ①、②を数学的帰納法で証明する。 k0 k2 k0 k1k2 x3 1 k0 k1 x4 n 1 のとき 各段階の xn の係数を pn とおく。 a k0 x1 x2 p1 x1 p0 x2 k x x q x q x b 1 2 3 2 2 1 3 p0 1, p1 k0 p2 1 k0 k1 p1k1 p0 成り立つ。 p3 k0 k2 k0 k1k2 n 1 まで仮定して 1 k0 k1 k2 k0 p2 k2 p1 a pn 1 pn 2 xn 1 q b n 1 qn 2 xn pn 2 kn 1 xn xn 1 p n 1 xn qn 1 qn 2 ・・・・ pn となり は次の漸化式を満たす。 pn pn 1kn 1 pn 2 pn 1kn 1 pn 2 xn pn 1 xn 1 qn 1kn 1 qn 2 xn qn 1 xn 1 p x pn 1 xn 1 n n qn xn qn 1 xn 1 これを用いると a x0 pn xn pn 1 xn 1 ・・・① と予想できる。 また、 よって、成り立つ。 b x1 k1 x2 x3 なお、 n m のとき xm 1 0 だから k1 k2 x3 x4 x3 a pm xm , b qm xm 1 k1k2 x3 k1 x4 例えば a 1147, b 1071 の場合、 各段階の xn の係数を qn とおく。 k0 1, k1 14, k2 10, k3 1, k4 6 q0 0, q1 1, m5 p0 1, p1 k0 1 q2 k1 q1k1 q0 p2 p3 p4 p5 q3 k1k2 1 q2 k2 q1 ・・・・ qn は次の漸化式を満たす。 qn qn 1kn 1 qn 2 3 p1k1 p0 114 1 15 p2 k2 p1 15 10 1 151 p3 k3 p2 1511 15 166 p4 k4 p3 166 6 151 1147 q0 0, q1 1, q2 k1 14 q3 q2 k2 q1 14 10 1 141 n 2 のとき、 x2 x0 k0 x1 q1 x0 p1 x1 q1a p1b q4 q3 k3 q2 141 1 14 155 以上から、次式が予想される。 q5 q4 k4 q3 155 6 141 1071 1147 x0 k0 x1 x2 11071 76 1 1071 x1 k1 x2 x3 14 76 7 ①、②を行列で表す。 7 x3 k3 x4 x5 1 6 1 a pn q b n 6 x4 k4 x5 6 1 gcd x0 , x1 gcd 1147,1071 1 gcd x2 , x3 gcd 76, 7 xn pn pn 1 a xn 1 qn qn 1 b 1 qn 1 pn 1 a n 1 qn pn b gcd x3 , x4 gcd 7, 6 gcd x4 , x5 gcd 6,1 1 x5 pn qn n qn 1a pn 1b 1 qn a pnb は次式を満たす。 xn 1 qn 1a 1 pn 1b ・・・④ n pn 1 n 1 ・・・③ qn 1 n 1 のとき、 p1 k0 , p0 q1 1, q0 0 p0 k0 q0 1 い方の数の 10 進数表示の桁数の5倍を超え ない( Lame の定理) 。 1 1 0 これは数列 x0 , x1 , xm を Fibonacci 数列 と比較することで証明できる。そのために補 n 1 のとき成り立つと仮定する。 pn 1 p k pn 2 n 1 n 1 qn 1 qn 1kn 1 qn 2 pn qn kn 1 2-4 n 2-5 Euclid の互除法の除算の回数は小さ (証) p 1 q1 pn 1 xn qn 1 xn 1 逆行列をとって③を用いる。 gcd x1 , x2 gcd 1071, 76 pn , qn xn qn 1a pn 1b (証) 76 x2 k2 x3 x4 10 7 6 2-3 n pn 1 qn 1 pn 1 pn 1 qn 1 qn 1 題を一つ必要とする。 補題 Fibonacci 数列 f k において pn 1 qn 1 f5 p 1 10 p が成り立つ。 pn 2 n 1 qn 2 例えば、 xn を a , b についての1次式で表す。 f 6 f5 f 4 f 4 2 f3 f 2 n 1 のとき x1 0 x0 1 x1 から x1 q0 x0 p0 x1 q0 a p0 b 3 f 3 2 f 2 5 f 2 3 f1 8 f1 5 f 0 13 101 4 (証)Fibonacci 数列の一般項は l j 1 xm j 1 km j 1 xm j xm j 1 1 fk k 1 k 1 5 l j l j 1 f j 1 f j f j 2 したがって、2つの整数 a, b a b で 1 5 / 2, 1 5 / 2 これに k 5 p 1 を代入 f 5 p 1 Euclid の互除法の回数 m が m 5q 1 とする。このとき、 3 5 5 p 3 5 5 p 2 5 2 5 5 11.090 11 b x1 lm1 f m f5q 1 10q log10 b q が成り立つ。 この対偶は log10 b q ならば、 m 5q と 5 0.090 3 5 3 5 11p 2 5 2 5 p このとき右辺は 10 以上となることが分 よって、 f 5 p 1 なる。よって、互除法の回数は 5 log10 b で かる。 押さえられる。 まず、 p 0 のときは明らか。 ただし、 x は x を超える最小の整数で p 0 のとき成り立つと仮定する。 あり、 x log10 b ならば b の 桁数を表す。 3 5 3 5 11p 1 2 5 2 5 3 5 3 5 3 5 11 11p 10 2 5 2 5 2 5 p p 1 11 10 10 3 Euclid 互除法と不定方程式 3-1 そこで、 xi i 0,1, 2, m を逆順に l j と定め、 f j log10 1234 log10 1.234 3 4 例 不定方程式 ax by d ・・⑤ の一般解を考える。 ⑤が解をもつためには d が gcd a, b と比較する。 l0 xm f1 1 xm 1 xm , km 1 1 より l1 xm 1 km 1 xm l0 1 f 0 f1 f2 l2 xm 2 km 2 xm 1 xm l1 l0 の倍数となることが必要十分である。 いま、 d gcd a, b とする。 Euclid の互除法を用いて 2-4 の④式が求 f 2 f1 f3 められたとする。 そこで、 l j f j 1 と仮定する。数学的帰納 xm d gcd a, b 法で示す。 1 qm 1a 1 m m 1 a ad , b bd とおく。 この式と⑤から 5 pm 1b a x 1 qm 1 m b y 1 m 1 pm 1 これから a x0 b x 1 k 1 k1 1 km 1 1 xm 0 ・ 1 0 1 0 1 0 0 xm d 0 0 a, b は互いに素だから x 1 qm 1 bt m y 1 m 1 pm 1 at ・・⑥ ( t : 整数) これが⑤の一般解である。 ・・⑦ とおくと 例2 不定方程式 1147 x 1071 y 1 の 一般解を求める。 m 5, p4 166, q4 155 a 1147, b 1071 を⑥に代入すれば a b d 0 d 0 a x y a b z w b 1 となり 一般解は x 155 1071t , y 166 1147t 3-2 d ax by x y z w なお、次のように行列を使って特殊 解を求める方法がある(岩堀、1983) 。 1 a x0 k0 x1 x2 から a x0 k0 x b 1 1 1 x1 0 x2 1 ・・⑧ ここで x1 k1 1 x2 同様に x2 1 0 x3 x2 k2 x3 1 1 1 km 2 1 k k0 1 m 1 0 1 0 1 1 0 1 0 1 0 1 0 1 km 1 1 km 2 1 k0 ki 1 1 x3 、 ・・・、 0 x4 1 1 0 1 0 1 1 k 1 k 0 i i ⑧を用いて 2-1 の例1の特殊解を求める。 k0 1, k1 14, k 2 10, k3 1, k 4 6 xm1 km1 1 xm が成り立つ。 xm 1 0 0 だから ⑧は 6 a x0 x 1 k0 2 k0 x b x1 x1 k1 3 x2 x y 0 1 0 1 0 1 1 6 1 1 1 10 0 1 0 1 1 14 1 1 0 1 1 10 1 1 1 6 1 11 14 15 k0 0 1 141 151 1 6 155 166 155 166 * * k0 1 k1 k2 x4 x3 1 k1 1 k2 1 km2 特殊解は x 155, y 166 である。 4 1 1 km 1 k0 , k1 , , km1 と書く。 Euclid 互除法と連分数 これは 2-1 で扱った互除法の商系列の 4-1 Euclid 互除法の式から連分数展開 表現と同じである。 が出てくる。 1147 1,14,10,1, 6 1071 上の例では 2-1 の例 1 の 1147,1071 の互除法の各 なお、有理数は有限の連分数展開で表さ 式変形を再度記すと れる。逆も成り立つ。 無理数の連分数展開はどうなるか? 1147 1 1071 76,1071 14 76 7 76 10 7 6, 7 1 6 1 例えば、 2 を連分数展開は 2 1 これを連分数に展開すると 1147 76 1 1 1 7 1071 1071 14 76 1 1 14 1 1 1 1 6 10 7 1 1 14 10 1 2 2 1 1 1 1 1 2 2 1 1 1 2 1 2 1, 2, 2, となり、無限の連分数展開となる。 1 1 6 実は、任意の無理数は無限連分数に展開さ れる。逆も成り立つ。 2 1, 2, 2, 1, 2 ということは 一般の a , b の場合は 2 が無理数であることの証左である。 7 1 5 4-2 の連分数展開を考える。 2 2 この数は黄金比と呼ばれ、 1 0 を満たす正の解である。式変形すると BE 1 1 ば 1 1 1 1 1 1 1 1 1 1 1 1,1, 次に、線分同士の互除法を考える。 BE AE 1 BP AE BT BP 1 PT BP QT PT 1 UT これを連分数で表すと以下のような無限 辺の長さ 1 の正五角形 ABCDE におい 連分数になる。 点 A から線分 BE に BE BP 1 BE 1 1 AE AE AE BP 1 1 1 1 1 1 1 1 BP 1 1 PT PT UT 垂線を下した点を F とすれば 5 BE 2 cos BP 5 BE AB より AB BP AB AE 1 1 5 2 正五角形の作図はこの比を使ってできる。 p0 p1 1 pn pn 1 pn 2 を満たす 数列 1,1, 2,3,5, に関連している。 EF cos 1 となり BE の長さは黄金 BE 黄金比は Fibonacci 数列の漸化式 5 ここで BE とおけ 比になる。 1 て、AEB 1 BE 1 BE よって、 は無理数となる。 BE BP PE BP AE BP 1 参考文献 A [1] 岩堀長慶:2次行列の世界、岩波書店 [2] 河田敬義(1992):数論、岩波書店 P B T [3] Knuth(1972):The Art of Computer E Programming,VolumeⅠ U [4] 根上生也(2012):数学活用、啓林館 S Q [5] 林 雄一郎(2012):RSA 暗号と素因数 分解、数実研第 81 回研究会 R [6] 林 C 雄一郎(2014):高校数学における発 展的オプション教材の意義について、北海道 D 情報大学紀要第 25 巻第 2 号 8
© Copyright 2024