質問: 定理2の証明お願いします
回答: ベズーの補題(Bézout's lemma)という名前が付いています。検索するときに参考になれば。 証明 (<=) 今 a*x+b*y = 1 (1) が成立していると仮定する. d = gcd (a, b), a' = a / d, b' = b / d とおけば, a*x + b*y = d * (a'*x + b'*x) となり, (1)式の左辺は d の倍数になる。 そこで, d != 1 と仮定すると, (ここで a != b は a と b が等しくないことを表す) |a*x+b*y| = d*|a'*x + b'*x| >= d != 1 即ち a*x+b*y != 1 となって (1) に矛盾. したがって d = 1, 即ち a と b は互いに素である. (=>) 除算アルゴリズムを a, b に逐次適用してゆくと, a = b * q_1 + r_1, (1 <= r_1 < b) b = r_1 * q_2 + r_2, (1 <= r_2 < b) r_1 = r_2 * q_3 + r_3, (1 <= r_3 < b) ... r_(k-2) = r_(k-1) * q_k + r_k, (1 <= r_k < r_(k-1)) r_(k-1) = r_k * q_(k+1) + r_(k+1), (r_(k+1) = 0) となるような q_i, r_i が存在する. ここで r_k = gcd (a, b)となることに注意. これをユークリッドの互除法(Euclidean algorithm)という. このとき, r_1 = a - b* q_1, r_2 = -a * q_2 + b * (1 + q_1 * q_2) ... となり, 一般には r_i = a*x_i + b*y_i と書ける. (r_(i+1) = r_(i-1) - r_i * q_(i+1) から帰納法で証明できる.) このとき, 漸化式 x_(i+1) = x_(i-1) - q_(i+1) * x_i y_(i+1) = y_(i-1) - q_(i+1) * y_i が成り立ち, 最終的に gcd (a, b) = r_k = a*x_k + b*y_k が得られる. 今 gcd (a, b) = 1 であるから, a*x_k + b*y_k = 1 となる. 即ち a*x + b*y = 1 となるような整数の組 (x, y) (=(x_k, y_k)) が存在する. ■