［１］ユークリッドの互除法アルゴリズムは必ず終結する．（大，小）→（小，大ー小）を繰り返せば，たとえば，

　　（１３，８）→（８，５）→（５，３）→（３，２）→（２，１）→（１，１）

のような対の列が得られる．最大公約数がどうして得られるかというと数ｄが２つの数ａとｂを割り切るならば，ｄは差ａ−ｂを割り切るし，差をとれば必ず大きい数は減少し続けるので，このアルゴリズムは必ず終結するのである．

［２］エジプト分数では最大の単位分数を繰り返し取り除くというフィボナッチのアルゴリズムは必ず終結することが知られている，

　　３／４＝１／２＋１／４

　　２／３＝１／２＋１／６

　　５／７＝１／２＋１／７＋１／１４

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【１】アルゴリズムは破綻しない・・・「エジプト式単位分数」

　分子が１である分数を単位分数と呼びます．古代エジプト人は分数を表すのに，互いに異なる単位分数の和として表しました．たとえば，５／７は

　　５／７＝１／７＋１／７＋１／７＋１／７＋１／７

ではなく，互いに異なる単位分数の和ですから，３つの単位分数を用いて

　　５／７＝１／２＋１／５／１／７０

と書くことができます．

　どんな分数でも相異なる単位分数の和として表現できることは，簡単に証明できます．それでは

(1)分数ｐ／ｑを越えない最大の単位分数を求め，ｐ／ｑから差し引き，それをｐ1／ｑ1とする

(2)分数ｐ1／ｑ1を越えない最大の単位分数を求め，ｐ1／ｑ1から差し引き，それをｐ2／ｑ2とする

(3)分数ｐi／ｑiを越えない最大の単位分数を求め，ｐi／ｑiから差し引き，それをｐi+1／ｑi+1とする

という手順を繰り返せば，つねに単位分数表示が得られるでしょうか？

　答えはyesで，このアルゴリズムは破綻しないことが知られています．もちろん，その表示の仕方はただ１通りです．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

　単位分数の和としての表現は少なくとも１つは存在するのですが，しかし，単位分数表示は１通りとは限らず，たとえば，前述の５／７は

　　５／７＝１／２＋１／７＋１／１４

　　５／７＝１／３＋１／４＋１／８＋１／１６８

のように何通りも表し方があります．

　２／（２ｎ−１）という形の分数の相異なる単位分数の和による表現では，欲張り算法により<

　２／（２ｎ−１）＝１／ｎ＋１／ｎ（２ｎ−１）

のように２個の単位分数を用いて表示できます．

　　２／３＝１／２＋１／６

　　２／５＝１／３＋１／１５

　　２／７＝１／４＋１／２８

　　２／１１＝１／６＋１／６６

　　２／２３＝１／１２＋１／２７６

はこの式に従っていますが，

　　２／９＝１／６＋１／１８

　　２／１３＝１／８＋１／５２＋１／１０４

　　２／１５＝１／１０＋１／３０

　　２／１７＝１／１２＋１／５１＋１／６８

　　２／１９＝１／１２＋１／７６＋１／１１４

　　２／２１＝１／１４＋１／４２

は欲張り算法によるものではありません．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝