用語集
ベズーの等式べずーのとうしき
最終確認日:
gcd(a, b) = d の とき、 a x + b y = d を 満たす 整数 x, y が 存在 するという等式。
最終確認日:
gcd(a, b) = d の とき、 a x + b y = d を 満たす 整数 x, y が 存在 するという等式。
ベズーの等式とは、整数（両方 でない）に対して、 を満たす整数 が必ず存在する、という等式です。
| 手順 | 内容 |
|---|---|
| 1 | ユークリッドの互除法で を求める |
| 2 | 互除法の式を下から逆にたどる |
| 3 | を の形に表す |
たとえば なので、 を満たす整数 が存在します。
ポイント 1次不定方程式の特殊解を作る理論的な裏づけ。互除法を逆にたどる手続きは「拡張ユークリッド互除法」と呼ばれる。