Пример кода

public static EuclidExtendedResult EuclidExtended(BigInteger a, BigInteger b) {
    var si2 = new BigInteger(1);
    var ti2 = new BigInteger(0);
    var si1 = new BigInteger(0);
    var ti1 = new BigInteger(1);
    while (b != 0) {
        var k = a / b;
        var si = si2 - k * si1;
        var ti = ti2 - k * ti1;
        si2 = si1;
        ti2 = ti1;
        si1 = si;
        ti1 = ti;

        var r = a % b;
        a = b;
        b = r;
    }
    return new EuclidExtendedResult { S = si2, T = ti2 };
}