ユークリッドの互除法とプログラム
岡田俊一 2016/06/30
数学科教科法 A の模擬授業で「整数の性質」で”ユークリッドの互除法と不定方程式”を済ませました。
二つの数の GCM を求める一般的な方法は、共通な素因数がなくなるまで割り続ける、そして割った数をすべて掛
け合わせて GCM（最大公約数）を求めます。しかし共通の素数が大きな数になる場合には、ユークリッドの互除
法という”神の解法”があります。
＃ここで生徒に互除法の素晴らしさに感激をして欲しいところです。
●高校でのプログラムの扱い
平成 24 年の新課程になってから数学 A でユークリッドの互除法が登場したのですが、旧課程で学んだ現在の大
学 3 年生の数学 B の選択領域数値計算とコンピューのタのいろいろなアルゴリズムでも実は登場していました。
ただ、ほとんどの高校が大学入試と関連の深い数列・ベクトルを履修するために、新課程では惜しまれることな
く忘れ去られました。
アルゴリズムの理解は、情報科に期待をされているのですが、情報の科学アルゴリズムとプログラムで数ページ
に登場する程度です。
現場でのプログラム教育については、
小学校のプログラミング必修化は本当に必要かというサイトで次のように触れられています。
こうした動きには英語必修化同様、当然「時期尚早」との異論も出ている。03 年に必修科目とされた高校の「情
報」も、なかなか教える人材を手配できないため、「街の PC 教室以下」ともいわれる低レベルにあえぐ学校も
多い。私が見聞した実際の授業でも、単に Word や Excel などのソフトの使い方を教えるにとどまったり、SNS
でのリテラシービデオを見せて学ばせるといった、ややお粗末な内容が多かった。事実上、受験向け科目に振り
替えられるケースも見受ける。（中略） 高校でのプログラミングだが、現在は選択科目の中に含まれるため、
学んでいる生徒は全体の 2 割。しかし、20 年度以降の新学習指導要領では必修科目の学習項目に入れる方針だ。
ICT が日常的に使われ機器環境が整いつつありますが、最近の学生の機器利用のスキルは、スマホの普及によっ
て逆にパソコンの能力が落ちています。
授業の最初にアンケートを採りますが高校時代の情報科の内容はあまりにも幅広く、学習内容が数学のように系
統だっていませんし基本的な操作の習得にもばらつきがあります。
数学科教育の関わる学生には、新課程では基本的なプログラムやアルゴリズムは知って欲しいし、理系のコース
であればできれば情報科の教科内容との連携を願っています。
ここでユークリッドの互除法のプログラムを考えてみます。▼
●十進 basic で組む
アルゴリズムを理解しフローチャートにします。
x/y の整数除算の余り r は、
r=x-y*int(x/y)
で求められます。n88 系の basic で教材を作らざるを得なかっ
た団塊世代の数学科教師であれば、十進 basic は、そのまま
使えます。旧課程の数 B で採用している言語でも採用されて
います。
さまざまな言語がありますが、インタプリッタ言語でフリー
ソフトで usb メモリの中に入れてそのまま」動きます。初め
て言語に接する高校生には最適と思います。
フローチャートと a,b,x.y の数字の動きを理解し、次のソー
スコードを、basic.exe を実行した画面に打ち込みます。
! ユークリッドの互除法
INPUT PROMPT "a=":a
INPUT PROMPT "b=":b
LET x=a
LET y=b
10 LET r=x-y*INT(x/y)
IF r<>0 THEN
LET x=y
LET y=r
GOTO 10
ELSE
PRINT "最大公約数";y
END IF
END
実行画面です。（右）
●excel の VBA で組む
同じように VBA で十進 basic のプログラムを組み替えてみます。同じように対応させました。
VBA の起動はリボンの”開発”をクリックします。リボンに”開発”がない場合には、ファイル→オプション→
リボンのユーザー設定→開発にチェックを入れます。開発→Visual Basic→挿入→標準モジュール でプログラ
ムの挿入画面が出ます。
ここに次のテキスト部分を打ち込み（コピペでもかまいません）ます。
' 互除法
Sub ユークリッドの互除法()
Cells.Clear
Cells(1, 1) = "a="
Cells(2, 1) = "b=" ' cells(2,1)と range("a2")とは同じ
Cells(1, 2) = InputBox("a を入れて下さい")
Cells(2, 2) = InputBox("b を入れて下さい")
x = Cells(1, 2)
y = Cells(2, 2)
Label10:
r = x - y * Int(x / y)
If r <> 0 Then
x = y
y = r
GoTo Label10
Else
Cells(3, 1) = "最大公約数"
Cells(3, 2) = y
End If
End Sub
打ち込んだ後実行した画面です。
保存をするときには、拡張子を xlms にしてください。
このプログラムはダウンロード（クリック）できます。
ダウンロードされたら、execl を実行し、開発→マクロで互除法の互除法を実行してみてください。
パソコン環境によっては、マクロを有効にしますかなどの表示が出るかもしれません。そのまま実行をしてくだ
さい。
十進 basic に比べ手順が厳格で慣れるまでエラーコード
がよく出ます。入出力さえ理解すれば、豊富な関数群もあ
りますし、数学の問題をロジックに理解するツールとして、
十進 basic や VBA は有効です。
これからの若い数学科教師にはマスターして欲しいツー
ルです。
© Copyright 2025 ExpyDoc
