ユークリッドの互除法ゆーくりっどのごじょほう

ユークリッドの互除法じょほうとは、2つの自然しぜん数すう$a,b$（$a>b$）の最大公約数さいだいこうやくすうを、$a$ を $b$ で割わった余あまり $r$ を使つかって $\gcd (a,b)=\gcd (b,r)$ と置おき換かえる操作そうさをくりかえすアルゴリズムです。

ステップ	計算けいさん
1	$\gcd (252,105)$：$252=105\cdot 2+42$
2	$\gcd (105,42)$：$105=42\cdot 2+21$
3	$\gcd (42,21)$：$42=21\cdot 2+0$
結果けっか	余あまり $0$ の直前ちょくぜんの割われる数$21$

たとえば $\gcd (252,105)=21$ です。素因数そいんすう分解ぶんかいしにくい大おおきな数かずでも速はやく求もとまります。

試験しけんでは 大おおきな数かずの最大公約数さいだいこうやくすうや、$ax+by=\gcd$ の特殊とくしゅ解かいを求もとめるときに使つかう。余あまりが $0$ になる「直前ちょくぜんの割われる数かず」が答こたえ。