（2）编程实现计算Bezout（贝祖）等式的算法（定理1.3.7）,即对于两个正整数a, b,可计算出整数s, t使得式s·a+t·b = (a, b)成立。C或C++实现

Bezout's Identity，也称为中国剩余定理（Chinese Remainder Theorem，CRT）的一个简化版本，可以用于找到两个正整数a和b的最大公约数gcd(a, b)的表示。这个定理表明，如果a和b互质（即gcd(a, b)=1），那么存在整数x和y满足ax + by = 1，而对于任意其他整数m，总能找到相应的整数s和t使得sa + mt = m模ab同余。

在C或C++中，我们可以使用扩展欧几里得算法（Extended Euclidean Algorithm）来计算 Bezout 系数 s 和 t。这个算法不仅返回最大公约数，还同时返回了两个数的一组Bézout系数，使得s*a + t*b = gcd(a, b)。

以下是C++的基本实现：

#include <iostream>
using namespace std;

// 求解最大公约数和Bézout系数
pair<int, pair<int, int>> extendedEuclid(int a, int b) {
    if (b == 0) {
        return {a, {1, 0}};
    }
    auto [d, x1, y1] = extendedEuclid(b, a % b);
    return {d, {y1, x1 - (a / b) * y1}};
}

int main() {
    int a, b;
    cout << "请输入两个正整数a和b: ";
    cin >> a >> b;

    // 验证是否互质
    if (gcd(a, b) != 1) {
        cout << "输入的a和b不是互质的，无法直接应用Bézout定理。" << endl;
        return 0;
    }

    auto [g, bezout] = extendedEuclid(a, b);
    cout << "gcd(a, b) = " << g << endl;
    cout << "存在s=" << bezout.first << "和t=" << bezout.second.first << "满足sa + bt = gcd(a, b)" << endl;

    return 0;
}