ユークリッドの互除法は　大きな数の最大公約数を求めるときに必須で，また古代にも関わらずその洗練されたアルゴリズムのため，多くのプログラミングの教科書に載っています．まず 自然数aとbの最大公約数を(a,b)と表します．例えば(4,12)=4, (6,8)=2 などです．これを使うと，ユークリッドの互除法は次の様に書けます．

a,b,q,rが自然数の時　 (#) a=bq+r 　　ならば 　　(a,b)=(b,r)

教科書では r は余りとしていますが (#)の式さえ成り立てば大丈夫です．これは小学生でも分かる様に図形でも説明できますが，なぜか数研出版の教科書では図形的説明がありません．（東京書籍や啓林館にはあります).そこで　GeoGebra やMathematica という数学ソフトで　ユークリッドの互除法の図形的説明のアプリを作ってみました．

下の図をご覧ください．これはGeoGebra のワークシートから取りました．　　一行目の 「572=2*209+154 →(572,209)=(209,154) 」ですが，これを図形的に言うと「横572,縦209の長方形を敷き詰めることのできる正方形は，横209,縦154の長方形を敷き詰められる．またこの逆も成り立つ」ということです．これを何度も繰り返すことによって (572,209)=11となります．即ち 1辺が11の正方形で下の長方形は敷き詰められて，かつそれより大きい正方形では敷き詰められないということです．

上に上げた長方形表示を「動的に(即ち自由に2つの数を入れられる」求めるワークブック(Geogebra)を作成しました．

• GeoGebra のサイトなら，何もインストールしないでも　見れます．ただし，細かい操作はできません．動作も重いです．

• ワークシートをDownloadすれば，動作も軽いし細かい操作も可能です．但し Geogebra(無料) が必要です．私の愛用しているのは Classiｃ5 ですが，Classic6 や GeoGebra スイートでも大丈夫と思います．個人的には Classic6や スイートはWeb 向き(タブレットなど)だと感じています．
• 同じ様なアプリは Mathematica というソフトで以前作りました．Mathematica の方がプログラミングが楽なのですが，図の拡大ができないので，GeoGebra でもう一度作りました．
• ユークリッドの互除法は，連分数(continued fraction)ととても似ています．ご興味の有る方は，そちらもご覧ください．　　（2023年8月26日　生越　茂樹)

Contents

1.GeoGebra site	Geogebra　public site
2.Work sheet Download	EuclideanAlgorithm.ggb
GeoGebra Download	GeoGebra Download

トップページへ戻る	Email me
by 生越　茂樹(Ogose Shigeki).	All rights reserved.