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.
gmp_gcdext
(PHP 4 >= 4.0.4, PHP 5, PHP 7)
gmp_gcdext — Calculate GCD and multipliers
Descrierea
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
-
num1 -
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.
-
num2 -
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($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
?>
add a note
User Contributed Notes 1 note
FatPhil ¶
21 years ago
