ExtendedeGCD

static NT ExtendedGCD(NT a, NT b, NT &alpha, NT &betta)
    {
        NT b2 = b;

        if (b == 0)
        {
            alpha = 1;
            betta = 0;

            return a;
        }

        NT alpha2 = 1, alpha1 = 0, betta2 = 0, betta1 = 1;

        while (b > 0)
        {
            NT q = a / b;
            NT r = a - q * b;

            alpha = alpha2 - q * alpha1;
            betta = betta2 - q * betta1;

            a = b;
            b = r;

            alpha2 = alpha1;
            alpha1 = alpha;
            betta2 = betta1;
            betta1 = betta;
        }

        alpha = alpha2;
        betta = betta2;

        if (alpha < 0)
            alpha += b2;

        return a;
    };