ユークリッドの互除法 with GeoGebra

ユークリッドの互除法は 大きな数の最大公約数を求めるときに必須で,また古代にも関わらずその洗練されたアルゴリズムのため,多くのプログラミングの教科書に載っています.まず 自然数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)を作成しました.

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.