この用語はまだ監査を通っていません（未確認）。
拡張ユークリッド互除法
かくちょうゆーくりっどごじょほう 1対1で対応extended Euclidean algorithm
名詞
式と読み方
nine times seven minus two times thirty-one equals one
定義
ユークリッドの互除法の計算を使って、gcd(a, b) だけでなく ax + by = gcd(a, b) を満たす整数 x, y も求める手順のこと。互除法の各段の式を逆にたどって x, y を得る。
A version of the Euclidean algorithm that finds not only gcd(a, b) but also integers x and y with ax + by = gcd(a, b). The values of x and y come from working back through the division steps.
例文
話し言葉 Once you get a remainder of 1, work backward through the steps. That's the extended Euclidean algorithm. 余りが 1 になったら、式を逆にたどっていこう。これが拡張ユークリッド互除法だ。
書き言葉・答案 Use the extended Euclidean algorithm to find integers x and y such that 31x + 7y = 1. 互除法を用いて、31x + 7y = 1 を満たす整数 x, y の組を 1 つ求めよ。
言い間違えやすいところ
- 数A の一次不定方程式では、この手順を名前を付けずに「互除法の式を逆にたどる」形で使う。
- 求まる (x, y) は 1 組だけ。d = gcd(a, b) とすると、ほかの整数解は x を b/d ずつ、y を a/d ずつ逆向きにずらして得られる。
- 用例コーパスにも参照（CED・OpenStax・IM・CK-12・Nicholson・Levin）にも出てこない。
根拠の件数
用例コーパスで数えた件数はありません（数えない言い方か、どの取得元にも出てこなかった言い方です）。