スナネコです。拡張GCDについての質問に答えます。問題: 以下のように実装された extgcdがある。 整数 が を満たし、extgcd(a, b) の返り値を としたとき、 が成り立つことを示せ。 def extgcd(a, b): # ax+by=gcd(x,y) を満たす (x,y) を返す if b == 0: return (1, 0) X, Y = extgcd(b, a % b) x = Y y = X - a // b * Y return (x, y) extgcd(a, b) が「 を満たす整数 を返すこと」の証明は省略します。最初に補題を示しておきます。 補題★: 0 で…