h.egcd

来自「强大的数学工具包」· EGCD 代码 · 共 36 行

                               * * * * * * *
                               *   egcd    *
                               * * * * * * *

        "extended greatest common divisor"
        SYNTAX: X = egcd(A1, A2, ..., An)

        A1, ..., An are expressions whose values are elements in Z
        or univariate polynomials over Z/pZ, GF(p^n), n>=2 and p prime
        or over number fields.

        X is assigned the greatest common divisor of A1, ..., An.
        egcd computes the cofactors X1, ..., Xn , with
                X = X1*A1 + ... + Xn*An.

        In AV the cofactors are stored (see "?avfunc").

        Warning: If p > 2^30, the primality of p is not tested.
        

        Example 1: (correct)

                egcd(a1, (2*5-75), 234 + 23)


        Example 2: (incorrect)

                egcd(2/3,14)

_ERR_NR_015


        Example 3: (correct)

                egcd(MOD(x^2 + 2*x + 1), MOD(x + 1))