gmp_gcdext

    (PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)

    gmp_gcdext — Calculate GCD and multipliers

    Açıklama

    gmp_gcdext(GMP|int|string $num1, GMP|int|string $num2): array

    Calculates g, s, and t, such that a*s + b*t = g = gcd(a,b), where gcd is the greatest common divisor. Returns an array with respective elements g, s and t.

    This function can be used to solve linear Diophantine equations in two variables. These are equations that allow only integer solutions and have the form: a*x + b*y = c. For more information, go to the » "Diophantine Equation" page at MathWorld

    Bağımsız Değişkenler

    num1

    Bir GMP nesnesi, bir tamsayı veya sayısal bir dizge.

    num2

    Bir GMP nesnesi, bir tamsayı veya sayısal bir dizge.

    Dönen Değerler

    An array of GMP numbers.

    Örnekler

    Örnek 1 Solving a linear Diophantine equation

    <?php
    // Solve the equation a*s + b*t = g
    // where a = 12, b = 21, g = gcd(12, 21) = 3
    $a = gmp_init(12);
    $b = gmp_init(21);
    $g = gmp_gcd($a, $b);
    $r = gmp_gcdext($a, $b);

    $check_gcd = (gmp_strval($g) == gmp_strval($r['g']));
    $eq_res = gmp_add(gmp_mul($a, $r['s']), gmp_mul($b, $r['t']));
    $check_res = (gmp_strval($g) == gmp_strval($eq_res));

    if (    $check_gcd && $check_res) {
    $fmt = "Solution: %d*%d + %d*%d = %d\n";
    printf($fmt, gmp_strval($a), gmp_strval($r['s']), gmp_strval($b),
    gmp_strval($r['t']), gmp_strval($r['g']));
    } else {
    echo     "Error while solving the equation\n";
    }

    // output: Solution: 12*2 + 21*-1 = 3
    ?>

    Improve This Page

    Learn How To Improve This Page • Submit a Pull Request • Report a Bug
    ＋add a note

    User Contributed Notes 1 note

    up
    1
    FatPhil
    21 years ago
    The extended GCD can be used to calculate mutual modular inverses of two
    coprime numbers. Internally gmp_invert uses this extended GCD routine,
    but effectively throws away one of the inverses.

    If gcd(a,b)=1, then r.a+s.b=1
    Therefore r.a == 1 (mod s) and s.b == 1 (mod r)
    Note that one of r and s will be negative, and so you'll want to
    canonicalise it.
    ＋add a note
    To Top