整数解の基本
整数解の問題は、実数の方程式とは見方が違います。 割り切れ方、偶奇、余りの情報を使うのが基本です。
基本形
代表例は一次不定方程式 \(ax+by=c\)（\(a,b,c\) は整数）です。
この式が整数解を持つのは、\(\gcd(a,b)\mid c\) のときです。
簡単な例
\(6x+9y=30\) を考えます。
\(\gcd(6,9)=3\) で、\(3\mid 30\) なので整数解があります。 3 で割って \(2x+3y=10\) とすると、たとえば \((x,y)=(2,2)\) は解です。
使いどころ
- 方程式が整数で解けるかの判定
- 解の候補を合同式でしぼるとき
- 場合分けの前に不可能な形を消すとき
よくある失敗
- 実数で解けたから整数でも解けると思う
- 可解条件 \(\gcd(a,b)\mid c\) を見落とす
- 1つ見つけた解を一般解に広げない
次に学ぶ内容
- 互除法で一般解を出す方法
- 合同式を使った絞り込み
- 無限降下法