(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)
gmp_gcdext — PGCD étendu
Calcule les entiers g, s, et t, tels que
a*s + b*t = g = gcd(a,b), où gcd est le pgcd de
num1 et num2. La fonction
retourne un tableau avec les index g, s et t.
Cette fonction peut être utilisée pour résoudre des équations diophantines
linéaires à deux variables. Ces équations n'ont qu'une seule solution
entière, et elles sont de la forme : a*x + b*y = c.
Pour plus d'informations, voyez les pages
» "Diophantine Equation"
sur MathWorld, en anglais.
num1Un objet GMP, un entier, ou une chaîne de caractères numérique.
num2Un objet GMP, un entier, ou une chaîne de caractères numérique.
Un tableau de nombres GMP.
Exemple #1 Résolution d'une équation Diophantine linéaire
<?php
// Résolution de l'équation a*s + b*t = g
// où 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 "Erreur lors de la résolution de l'équation\n";
}
// Résultat : Solution : 12*2 + 21*-1 = 3
?>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.