ユークリッドの互除法で約分

昨年に引き続き，学校公開日の模擬授業を受け持った．
ネタは同じ，約分．でも，昨年やったときは50分用に作った教材を30分でやらねばならず，大変だったので，問題数を減らしてやり方も変えた．＞プリントPDF
プリントと，電卓を配布．（引率の親にもｗ）

手順はユークリッドの互除法で最大公約数GCDを求め，割ることである．
昨年までは，最初は世間一般の約分，すなわち素因数分解でやらせて，途中苦しくなってからユークリッドの互除法（語は出さずに手順のみ）を教えた．＞初めの頃
けれど，時間短縮のため今回は，はじめから互除法でやる方法を教えてスタート．
つまり，まずは，
「引いた数で割ればOK」
というもの．

やってみて気づいたのは，簡単な問題はいらなかったということ．結局それらは飛ばした．

(8) 112/126
126-112 = 14
112-14×8 = 0 より，14で割れて
126/14=9
より 8/9

(10) 2160/2340
2340-2160 = 180
2160-180×12 = 0 より，180で割れて
2340/180 = 13
より 12/13
これを素因数分解（順に割っていく）でやろうとすると，
2160/2340 = 216/234 = 108/117 =　36/39 = 12/13
と割れる数を探す連続になるけど，互除法は割れる数が一発で見つかる．

実はこの「引く」という操作は割り算の余りを求めていることに他ならない．
1回引く操作は商が1の時の余りということである．
2340-2160 = 180 は，2340÷2160 の商1 余り 180 ということ．

普通は1回引いただけでは，割れる最大数(GCD)は求まらないが，数学の教科書に出てくるくらいの易しい約分はこの程度でできてしまう場合が多い．
そもそも，この教材を作ろうと思ったきっかけは，確率の単元で大きな整数でできた分数が約分できるかどうか，生徒が迷っているときに，
「引けばわかる」
と言ってしまったこと．もちろん生徒は理解できない．＞過去の記事
教科書に出ている分数程度なら，引くだけで分かる場合が多い．

1回でダメなら，引く数（わる数）から余りを引く（余りで割る）．
つまり互いに引いて（割って）いくから互除法という．互いに割っていった時に，余りには必ず最大公約数を含むので，最後残るのが最大公約数となる．＞証明

(12) 42/24
42-24 = 18
18-12 = 6
12-6×2 = 0
より 6 で割れて，7/4


(23) 108/228
228-108×2 = 12
108-12×9 = 0
より12で割れて，9/19

(31) 4301/3553
4301-3553 = 748
3553-748×4 = 561
748-561 = 187
561-187×3 = 0
より，187 で割れて，23/19

(37) 62615533/62773913
62773913-62615533 = 158380
62615533/158380 = 395.35 だから，
62615533-158380×395 = 55433
158380-55433×2 = 47514
55433-47514 = 7919
47514-7919×6 = 0
より，7919 で割れて，7907/7927

ちなみに 7907，7919，7927 は999番目，1000番目，1001番目の素数であるから，地味に割っていくと，分子の素因数 7907 まで999個の素数を試さなければならない．
1分に1個試すと，16時間以上かかる．でも，大きな数が素数かどうかは覚えていないだろうから，末尾が5以外のすべての奇数で割ることになるだろう．すると3000回以上割り算が必要で，52時間もかかる．1日8時間やっても，1週間かかる．
ところが，互除法なら数回の割り算でできてしまう．

巨大整数の素因数分解の難しさが，インターネットの暗号の安全性につながっているくらい素因数分解は難しい．しかし，2数の最大公約数ならそれこそ，「ブログに書ける程度の計算量」である．＞ユークリッドの互除法のパワー

以前，逆数を取って帯分数にするという方法でやっている生徒がいた．これも，同じ原理である．

新教育課程では，数学 A の「整数の性質」にユークリッドの互除法が入ってくる．互除法は不定方程式がひとつの目的であろうが，この約分の指導はその単元の導入くらいには使えるとは思う．

日本人の約分のリテラシーのは，素因数分解が定着していて，互除法は世間的に知られていない．
ユークリッドの互除法を学ぶのは大学の数学科で，整数論や代数多様体などをとった者だけだろうな．
これらはとっても難しいこと（多項式の約分とか）に互除法のパワーを使うのであるが，本来は整数の約分に，もっと小中学生が使って欲しいリテラシーである．
でも，大人の99％以上は知らないので，だれも教える人がいない．

今回，ほとんど全ての生徒が学ぶ数学A に互除法が入ることによって，そうしたリテラシーに風穴が開けば良いと思っている．
日本人の誰に聞いても，「約分は引き算でしょ？」と答えるようになる時代は来るのだろうか．
しかし，約分を授業でやる先生は少ないだろうから無理かな．

ユークリッドの互除法の小中学生向けの教材といえば，
「長方形の短い辺で作る正方形を取り去ることの繰り返しで，最後に取り切った時の正方形の一辺が最大公約数」
というものがある．＞Google
そんなことまでしなくても，素因数分解によらない約分だけでも小中学校でやってもらいたいものだが，小学校の先生に互除法が知れ渡るにはあと何年かかるかな．

＞くろべえ「互除法」関連の記事