2つの数の最大公約数に関する注目トピックを速報でお届けします。関心のある方は必見です。

高校数学Aの「約数と倍数」単元で登場するユークリッドの互除法は、紀元前300年頃に記された人類最古のアルゴリズムの1つです。3桁や4桁を超える大きな数の最大公約数を求める場面において、威力を発揮します。

ユークリッドの互除法の基本原理

2つの自然数 A, B（A > B）について、A を B で割った商を q、余りを r とすると、以下の関係式が成り立ちます。

A = B × q + r

このとき、「A と B の最大公約数は、B と余り r の最大公約数に等しい」という数学的定理が互除法の根幹です。数を小さく置き換えながら割り算を繰り返すことで、巨大な素数同士の組み合わせであっても確実に最大公約数を割り出せます。

【計算実例】8633 と 2552 の最大公約数を求める手順

すだれ算では割る素数を見つけることすら困難な「8633」と「2552」の最大公約数を、ユークリッドの互除法で算出してみます。

1. 8633 ÷ 2552 = 3 余り 977（8633 = 2552 × 3 + 977）
2. 割る数 2552 を 余り 977 で割る：2552 ÷ 977 = 2 余り 598
3. 977 を 598 で割る：977 ÷ 598 = 1 余り 379
4. 598 を 379 で割る：598 ÷ 379 = 1 余り 219
5. 379 を 219 で割る：379 ÷ 219 = 1 余り 160
6. 219 を 160 で割る：219 ÷ 160 = 1 余り 59
7. 160 を 59 で割る：160 ÷ 59 = 2 余り 42
8. 59 を 42 で割る：59 ÷ 42 = 1 余り 17
9. 42 を 17 で割る：42 ÷ 17 = 2 余り 8
10. 17 を 8 で割る：17 ÷ 8 = 2 余り 1
11. 8 を 1 で割る：8 ÷ 1 = 8 余り 0

余りが0になった直前の除数（割った数）が最大公約数となります。したがって、8633 と 2552 の最大公約数は 1（互いに素） であることが確定します。