最大公約数と互除法
最大公約数は、整数問題の土台です。 互除法を使えると、計算が速くなり、整数解の問題にもつながります。
定義（基本形）
2つの整数 \(a,b\) の最大公約数を \(\gcd(a,b)\) と書きます。
互除法の基本は \(a=bq+r\)（\(0\le r<b\)）のとき \(\gcd(a,b)=\gcd(b,r)\) です。
簡単な例
\(\gcd(84,30)\) を求めます。
\[
84=30\times 2+24,
\quad
30=24\times 1+6,
\quad
24=6\times 4+0
\]
最後の 0 の直前の余りが 6 なので、\(\gcd(84,30)=6\) です。
使いどころ
- 分数の約分
- 一次不定方程式の可解条件の確認
- 互いに素かどうかの判定
よくある失敗
- 余りの順序を逆に書いてしまう
- 最後の余り 0 を答えにしてしまう
- 負の数をそのまま入れて混乱する
最大公約数は正で考えるので、負号は先に外して進めると安全です。
次に学ぶ内容
- 一次不定方程式 \(ax+by=c\)
- 合同式での逆元
- 中国剰余定理