ベズーの等式べずーのとうごうしき

ベズーの等式とうしきとは、整数せいすう$a,b$（両方りょうほう$0$ でない）に対たいして、$ax+by=\gcd (a,b)$ を満みたす整数せいすう$x,y$ が必かならず存在そんざいする、という等式とうしきです。

手順てじゅん	内容ないよう
1	ユークリッドの互除法で $\gcd$ を求もとめる
2	互除法じょほうの式しきを下したから逆ぎゃくにたどる
3	$\gcd$ を $ax+by$ の形かたちに表あらわす

たとえば $\gcd (3,5)=1$ なので、$3x+5y=1$ を満みたす整数せいすう$(x,y)=(2,-1)$ が存在そんざいします。

ポイント 1次不定方程式ふていほうていしきの特殊とくしゅ解かいを作つくる理論りろん的てきな裏うらづけ。互除法じょほうを逆ぎゃくにたどる手続てつづきは「拡張かくちょうユークリッド互除法じょほう」と呼よばれる。