gmp_gcdext

(PHP 4 >= 4.0.4, PHP 5, PHP 7, PHP 8)

gmp_gcdextPGCD étendu

Description

gmp_gcdext(GMP|int|string $num1, GMP|int|string $num2): array

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.

Liste de paramètres

num1

Un objet GMP, un entier, ou une chaîne de caractères numérique.

num2

Un objet GMP, un entier, ou une chaîne de caractères numérique.

Valeurs de retour

Un tableau de nombres GMP.

Exemples

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

add a note

User Contributed Notes 1 note

up
1
FatPhil
21 years ago
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.
To Top