1次不定方程式 ax+by=c
着眼点特殊解を1つ見つけて引き算し、「a(\cdots)=b(\cdots) で a,b が互いに素」から一般解を出す。
- 特殊解 (x_0,y_0) を見つける（代入 or 互除法）
- 元の式と引いて a(x-x_0)=-b(y-y_0)
- a,b が互いに素なので x-x_0 は b の倍数：x=x_0+bk,\ y=y_0-ak（k は整数）
c が \gcd(a,b) の倍数でなければ整数解はない。
例題
1
11x+7y=1 のすべての整数解を求めよ。
解答
11\cdot2+7\cdot(-3)=1 なので特殊解 (2,-3)。
引いて 11(x-2)=-7(y+3)。11と7は互いに素なので x-2=7k。このとき y+3=-11k。
答 x=7k+2,\ y=-11k-3（k は整数）
引いて 11(x-2)=-7(y+3)。11と7は互いに素なので x-2=7k。このとき y+3=-11k。
答 x=7k+2,\ y=-11k-3（k は整数）
2
3x+5y=40 を満たす正の整数の組 (x,y) をすべて求めよ。
解答
特殊解 (5,5)。3(x-5)=-5(y-5) より x=5k+5,\ y=-3k+5。
x>0 より k>-1、y>0 より k<\dfrac53。よって k=0,1。
答 (x,y)=(5,5),(10,2)
x>0 より k>-1、y>0 より k<\dfrac53。よって k=0,1。
答 (x,y)=(5,5),(10,2)
注意一般解の x と y で k の係数の符号を逆にし忘れるミス。最後に k=1 を代入して元の式を満たすか確かめる。
確認問題
1
11x+7y=5 の整数解は？
答え
特殊解 (3,-4)（33-28=5）。x=7k+3,\ y=-11k-4