拡張ユークリッド互除法の証明について問題ですが。。。2つの正整数A、B(A>B)に対して、Ax+By=GCD(A、B)なる整数x、yを求める手続きにユークリッドのアルゴリズムがある。GCD(A、B)はAとBの最大公約数を表す。次の手続きExEuclid(A、B)は、ユークリッドのアルゴリズムをプログラムにしたものである。1: ExEuclid( A, B) {2: /* A > B > 0 */3: a, b = A, B;4: x', x = 0, 1;5: y', y = 1, 0;6: while (b != 0) {7: q = a div b;8: r = a mod b;9: a, b = b, r;10: x', x = (P), x';11: y', y = (Q), y';12: }13: return x, y;14: }(1)上記の(P), (Q)部に適切な式を入れよ。(P: x - qx'; Q: y - qy' )(2)ループの先頭、つまり6行目を実行する直前で、以下の条件が常に成り立つことを証明せよ。 Ax + By = a, Ax' + By' = b, GCD(a, b) = GCD(A, B)(3)上記のプログラムが停止し、正しい答えを返す(つまり13行目を実行する際に、Ax + By = GCD(A, B)が成り立つこと)を証明せよ。第一問は自力で解きましたが、あとの2つ証明問題は分かりません、どう証明すればいいのかが分かりません。皆様の力を貸してください!よろしくお願いします。