(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
?>