1次不定方程式
アプリで開く →
進み具合を記録できるアプリ版です（ノード単位の直リンクはありません）
要点
ax+by=cが整数解を持つ条件は、gcd(a,b)がcを割り切ることである。axとbyはどちらもgcd(a,b)の倍数なので、その和も必ずgcd(a,b)の倍数になる（必要性）。逆に、互除法を逆にたどれば、gcd(a,b)そのものをax+byの形で実際に作れることが示せる（十分性）。この両方向の理解が、1次不定方程式の解の存在条件を支えている。
こんなときに使う
- ax+by=cの整数解を求める問題は、まず特殊解を1つ見つける
- 一般解は特殊解に、係数を互いに素にした量を足し引きする形で表す
手順
- 1. 互除法（またはあてずっぽう）で特殊解(x₀,y₀)を1つ見つける
- 2. 一般解は x=x₀+(b/g)t, y=y₀−(a/g)t（gはgcd(a,b)、tは整数）
例題
3x+5y=1の整数解をすべて求めよ。
解答
- 特殊解：x=2,y=−1（3・2+5・(−1)=1）。
- 一般解：x=2+5t, y=−1−3t（tは整数）。
- 検算：t=1のとき x=7,y=−4。3・7+5・(−4)=21−20=1 ○
落とし穴
- 一般解の係数（b/gとa/g）を逆にしてしまう
- 特殊解を見つける際の計算ミス
なぜ大事か
特殊解＋一般解の型
東大での出方
整数問題の基本ツール。合同式・因数分解型と並ぶ整数の三大手段の一角。
確認問題
- 2x+7y=3の整数解をすべて求めよ
前提になるノード
「整数」のノード
解説は自作です。誤りに気づいたら お問い合わせ（/contact/）から教えてください。