1 次 不定方程式いちじふていほうていしき

1次不定方程式ふていほうていしき $ax+by=c$ の整数せいすう解かいが存在そんざいする必要十分条件ひつようじゅうふんじょうけんは、$\gcd (a,b)$ が $c$ を割わり切きることです。1組くみの特殊とくしゅ解かい$(x_0,y_0)$ が見みつかれば、すべての整数せいすう解かいは次つぎのように表あらわせます。

記号きごう	内容ないよう
$d=\gcd (a,b)$	$a,b$ の最大公約数さいだいこうやくすう
特殊とくしゅ解かい	$(x_0,y_0)$ を1組くみ見みつける
一般いっぱん解かい	$x=x_0+\frac{b}{d}k, y=y_0-\frac{a}{d}k$

たとえば $3x+5y=1$ は特殊とくしゅ解かい$(2,-1)$ から、$x=2+5k, y=-1-3k$（$k$ は整数せいすう）と全ぜん解かいが書かけます。

試験しけんでは まずユークリッドの互除法を逆ぎゃくにたどって特殊とくしゅ解かいを1組くみ求もとめるのが定石じょうせき。係数けいすう$\frac{b}{d},\frac{a}{d}$ を $d$ で割わり忘わすれないこと。