PHP 5.5.16 is released

gmp_gcdext

(PHP 4 >= 4.0.4, PHP 5)

gmp_gcdextCalculate GCD and multipliers

Descrierea

array gmp_gcdext ( GMP $a , GMP $b )

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

Parametri

a

Un număr GMP sub formă de resource în PHP 5.5 și anterior, un obiect GMP în PHP 5.6 și ultrior, su un șir de caractere numeric atunci când acesta poate fi convertit într-un număr.

b

Un număr GMP sub formă de resource în PHP 5.5 și anterior, un obiect GMP în PHP 5.6 și ultrior, su un șir de caractere numeric atunci când acesta poate fi convertit într-un număr.

Valorile întoarse

An array of GMP numbers.

Exemple

Example #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($fmtgmp_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
?>

add a note add a note

User Contributed Notes 1 note

up
0
FatPhil
11 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.
To Top