ユークリッドの互除法

今日は中学生とその保護者を対象に学校を見せて，ついでに模擬授業ということで，くろべえは数学の授業担当．
タイトルは「式と計算」．
1週間前に授業のタイトルを係りに伝えなければならなかったが，もちろんやることはまったく決まっていないので，できるだけ生徒が集まらないように（笑），いかにもつまらなさそうなタイトルを考える．
で結局，内容を決めたのは，昨夜20時ごろ．それから教材を作っていたら22時ごろになってしまった．
ところが当日，「数学」というだけで集まった生徒がなんと16人も！・・・かわいそうに
家庭科室からはいいにおいが・・・
タイトルを見て「式と計算って何をやるのかな？」と思った中学生には迷惑な話で，タイトルとはまったく無関係な，ひたすら約分（爆）
はじめは簡単な
$\frac{24}{32}$
のようなものから20問．


だんだん素因数が多くなったり，7や11 や 13 でしか割れない，苦しい数にしていくこと20問．
ケータイの電卓も使っていいよということで．
自分も手計算で挑戦．くろべえの2倍くらいのスピードで答えを書く子もいた．

さて，苦しみの頂点に達するころ，ユークリッドの互除法を伝授．（互助法じゃないよ）

これは基本的に引き算である．
正しくは割り算の余りであるが．
すごく簡単に約分（最大公約数）ができるのに，学校では教えていない．
引き算を繰り返して最後に0になる直前の最も小さい数が最大公約数．
（割り算の余りを互いに求めて，割り切れる直前の数が最大公約数）

$\frac{24}{32}$ は 32-24=8, 24-8×3=0 だから 24も32も　8 で割れる．（8が最大公約数）

$\frac{4536}{3024}$
これは数がでかいだけで小さい数に素因数分解されるから，素因数分解でもやりやすい．
4536=2 2 2 3 3 3 3 7
3024=2 2 2 2 3 3 3 7
より $\frac{3}{2}$ だが，素因数分解の労力ときたら・・・
ユークリッドの互除法
4536-3024=1512
3024-1512×2=0
より分母分子は 1512 で割れて 3/2．一撃！

$\frac{1001}{1729}$
素因数分解を試みて 7 で割れる（涙）のに気づいて
$\frac{143}{247}$ かな？
実はこの2数はさらに 13 でも割れて
$\frac{11}{19}$　・・・ひー．わかんねぇよ！
ユークリッドの互除法なら
1729-1001=728
1001-728=273
728-273×2=182
273-182=91
182-91×2=0
より分母分子は 91 で割れて　11/19．

$\frac{3960091}{3968039}$
というバカヤローな約分もちょろい．
もうこれらの素因数分解は手作業ではあきらめるしかない．
3968039-3960091=7948
3960091-7948×498=1987
7948-1987×4=0
より分母分子は 1987 で割れて
$\frac{1993}{1997}$
ユークリッドの互除法では最大公約数が求まるので，この分数はこれ以上約分できないわけだが，ためしにどうなるかユークリッドの互除法をやってみる．
1997-1993=4
1993-4×498=1
より，共通に割る数 1 と確認できて，
1993/1997
は確かにこれ以上約分できない．

約分を話題にしているが，実際は最大公約数を求めている．
ユークリッドの互除法は簡単に2数の最大公約数を求める手順であるが，学校では教わらない．
教わるのは，大学の数学科の整数論だろう．数学科では整数だけではなく，他にもいろいろ理論的なことに使うからで，その点もすごく強力なツールである．
普通は割り算は，電卓などで小数 3960091/3968039=0.9979969 がわかればじゅうぶんであるし，数学の問題で巨大な分数を約分することはまずないから，学校では教えないのだと思う．
素因数分解を知っていれば十分という考えである．

でも小さい数でも知っているとスピードが全然違うんだなー．

$\frac{168}{192 }$くらいでも素因数分解する前に，引いてみる．
192-168=24
で
24 ×7=168 だから 24 で割れることがわかる．

ということで，今日参加した16人の中学生と7人の保護者，約分や最大公約数でちょっと得した気分になってもらった．

素因数分解がむずかしくても，最大公約数はちょろい．＞>Yahoo!知恵袋

約分には，逆数をとって，帯分数にしていくという方法もある．この場合，最後に分子が 1 になったときの分母で約分ができる．
これもやってみれば，同じ原理であることがわかる．

＞追記「ユークリッドの互除法の証明」