1.The extension to k ≥ 2 integers: if gcd(a1, . . . , ak ) = d, then there exist integers x1, . . . , xk such that 2. Prove Theorem 7.11 (the correctness of the Extended Euclidean algorithm) by...

1.The extension to k ≥ 2 integers: if gcd(a1, . . . , a^k
) = d, then there exist integers x1, . . . , xk such that

2. Prove Theorem 7.11 (the correctness of the Extended Euclidean algorithm) by induction on n: show that for arbitrary positive integers n and m with n ≤ m, extended-Euclid(n, m) returns three integers x, y,r such that r = gcd(n, m) = xn + ym.