ユークリッドの互除法
ユークリッドの互除法
最大公約数を求めるには素因数分解を行えばよいが， $1961$ のように大きな数を素因数分解するのは難しい（ $1961=37\cdot53$ ）．
素因数分解しにくい大きな数の最大公約数を求めるには，次の定理を使うと良い．
ユークリッドの互除法
2つの自然数 $a,b$ において， $a$ を $b$ で割った余りを $r$ とすると，
$a$ と $b$ の最大公約数は， $b$ と $r$ の最大公約数と等しい
すなわち
\[\text{gcd}(a,b)=\text{gcd}(b,r)\]が成り立つ．
暗記ユークリッドの互除法
ユークリッドの互除法を証明せよ．
例として1071と1029の最大公約数を求めてみよう．
1071を1029で割ると，商は1余りは42，すなわち
\[1071=1029\cdot1+42\]となるので，1071と1029の最大公約数は，1029と42の最大公約数と等しい． ここで得られた，1029と42に関して，再び割り算を行うと
\[1029=42\cdot24+21\]となるので，1029と42の最大公約数は，42と21の最大公約数と等しい．同様にして
\[42=21\cdot2+0\]となるので，42と21の最大公約数は21であることがわかる．すなわち，1071と1029の最大公約数は21である．
ユークリッドの互除法の利用
なし