(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.
num1
Un objet GMP, un entier,
ou un chaîne de caractères qui peut être interprété comme un nombre suivant la même logique
que si la chaîne était utilisée dans gmp_init() avec détection automatique de la base (c'est-à-dire lorsque base est égal à 0).
num2
Un objet GMP, un entier,
ou un chaîne de caractères qui peut être interprété comme un nombre suivant la même logique
que si la chaîne était utilisée dans gmp_init() avec détection automatique de la base (c'est-à-dire lorsque base est égal à 0).
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.