整数教材としての Euclid 互除法と連分数について ( ) ( ) ) ( )

の約数を調べ挙げるため素因数分解をしよ
整数教材としての Euclid 互
除法と連分数について
うとするだろう。奇素数 3,5, 7,11,13,17 で
次々に割ってゆき、 527  3117 を見つけ
る。 527  22.956  だから 19 までで見
つかるはずである。
次に、 1147 を 17 または 31 で割って
林
雄一郎
1147  31 37 を得る。さらに、 37 と 17
に公約数があるか否かチェックする。
17  4.123  だから奇素数 3 で 17,37 を
１
はじめに
久しぶりに高校数学「数学Ａ」に導入され
た Euclid の互除法は人類最古のアルゴリズ
ムであり、B.C.300 年頃に記された Euclid
の原論第７巻命題１に記載されている。ギリ
割り、公約数は 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 の互除法は次のようなアルゴリズ
２
Euclid の互除法について
公約数の考えは小学校５年生から学ぶ。例
えば、横 24ｃｍ、縦 18ｃｍの長方形の厚紙
がある。これを余り屑が出ないように、しか
も出来るだけ大きな正方形に分けるとき、何
センチメートルの正方形にすればいいか？
という問題を考えるとき最大公約数の考え
に自然に導かれるだろう。
ところで、例えば 527 と 1147 の最大公約
数を求めたいとする。児童らはこの２つの数
ムの形式で表される（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 の約数で
ある。
以上を例１の場合で確認してみる。
割る数、割られる数の系列  xi  は
具体的な数で互除法を実行してみる。
例１
0  x2  x1
0  x3  x2
0  x4  x3
1147,1071 の最大公約数を求める。
 x0 , x1 , x2 , x3 , x4 , x5   1147,1071, 76, 7, 6,1
互除法の操作は次の５回になる。
 
商となる数の系列 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,
m5
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  114  1  15
p2 k2  p1  15  10  1  151
p3 k3  p2  1511  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  11071  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 進数表示の桁数の５倍を超え
ない（ 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 についての１次式で表す。
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

したがって、２つの整数 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  lm1  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
３ 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  ad , b  bd とおく。
この式と⑤から
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  bt
m
y   1
m 1
pm 1  at ・・⑥
（ t : 整数）
これが⑤の一般解である。
・・⑦
とおくと
例２不定方程式
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 の例１の特殊解を求める。
k0  1, k1  14, k 2  10, k3  1, k 4  6
 xm1   km1 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

km2 
特殊解は x  155, y  166 である。
４
 
1
1
km 1
  k0 , k1 , , km1  と書く。
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] 河田敬義(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

Download Report