ユークリッドの互除法
ゆーくりっどのごじょほう ／ 互除法 1対1で対応Euclidean algorithm
名詞
式と読み方
if a equals b q plus r, then the gcd of a and b equals the gcd of b and r
定義
2 つの自然数の最大公約数を、割り算を繰り返して求める方法。a を b で割った余りを r とすると a と b の最大公約数は b と r の最大公約数に等しいことを使い、余りが 0 になるまで続ける。
A method for finding the greatest common divisor of two positive integers by repeated division: replace the pair (a, b) with (b, r), where r is the remainder of a divided by b, until the remainder is 0.
例文
話し言葉 Let's run the Euclidean algorithm: 252 divided by 105 is 2 with a remainder of 42, so now we look at 105 and 42. 互除法を使おう。252 ÷ 105 は 2 余り 42 だから、次は 105 と 42 を考える。
書き言葉・答案 Use the Euclidean algorithm to find gcd(1071, 462). 互除法を用いて、1071 と 462 の最大公約数を求めよ。
言い間違えやすいところ
- 「互除法」だけでは英語の名前にならない。Euclidean algorithm と言う。
- Levin（6.2）は最大公約数を gcd(a, b) と書く。
- 互除法の式を下から逆にたどると、ax + by = gcd(a, b) の整数解が 1 つ見つかる（一次不定方程式を解くときに使う。エントリ extended-euclidean-algorithm）。