8.42.22 gmp_gcdext()PGCD étendu

gmp_gcdext calcule les entiers g, s, et t, tels que a*s + b*t = g = gcd(a,b) , où gcd est le pgcd de a et b . 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.

Résolution d'une équation Diophantine linéaire

// 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