不定方程式 ax + by = c
整数係数の方程式 ax+by=c の整数解を求める問題です。
解が存在する条件
ax+by=c が整数解を持つ ⟺ GCD(a,b) | c（c が GCD(a,b) の倍数）
解の求め方
①まず ax+by=1 の特殊解 (x₀,y₀) を互除法から見つける
②一般解：x = x₀ + (b/d)t、y = y₀ − (a/d)t （d=GCD(a,b)、t は整数）
📘 例題①
3x + 7y = 1 の整数解を1つ求めよ。また一般解を書け。
7 = 3×2 + 1 → 1 = 7 − 3×2 → x₀=−2、y₀=1 が特殊解
一般解：x = −2 + 7t、y = 1 − 3t （t は任意の整数）
3x + 7y = 1 の整数解を1つ求めよ。また一般解を書け。
7 = 3×2 + 1 → 1 = 7 − 3×2 → x₀=−2、y₀=1 が特殊解
一般解：x = −2 + 7t、y = 1 − 3t （t は任意の整数）
📘 例題②
4x + 6y = 14 の整数解の一般解を求めよ。
GCD(4,6)=2、14÷2=7 → 両辺を2で割ると 2x+3y=7
3=2×1+1 → 1=3−2×1 → 2×(−1)+3×1=1 → 2×(−7)+3×7=7
特殊解：x₀=−7、y₀=7
一般解：x = −7 + 3t、y = 7 − 2t （t は整数）
4x + 6y = 14 の整数解の一般解を求めよ。
GCD(4,6)=2、14÷2=7 → 両辺を2で割ると 2x+3y=7
3=2×1+1 → 1=3−2×1 → 2×(−1)+3×1=1 → 2×(−7)+3×7=7
特殊解：x₀=−7、y₀=7
一般解：x = −7 + 3t、y = 7 − 2t （t は整数）
💡 ポイント
- まず GCD(a,b) が c を割り切るか確認
- 互除法を逆に辿って特殊解を見つける
- 一般解の差は必ず (b/d, −a/d) の倍数
- 正整数解や範囲指定があれば t の範囲を絞る
練習問題
- 5x + 3y = 1 の整数解を1つ求め、一般解を書け。
- 7x − 4y = 3 の整数解の一般解を求めよ。
- 3x + 5y = 11 を満たす正の整数 x, y の組をすべて求めよ。
解答・解説
- 5×2+3×(−3)=1 → 特殊解 x₀=2, y₀=−3。一般解：x=2+3t, y=−3−5t
- 7×1−4×1=3 → 特殊解 x₀=1, y₀=1。一般解：x=1+4t, y=1+7t（符号に注意：−4y の場合は y=1−(−7)t で確認）→ x=1+4t, y=1+7t
- 一般解 x=2+5t, y=1−3t（特殊解:x₀=2,y₀=1 から）。x>0, y>0 → 2+5t>0 かつ 1−3t>0 → t>−2/5 かつ t<1/3 → t=0 → (x,y)=(2,1)