PHP 8.4.0 RC2 available for testing

gmp_gcdext

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

gmp_gcdextВычисление НОД и множителей

Описание

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

Вычисляет величины g, s и t, в выражении a*s + b*t = g = gcd(a,b), где gcd - наибольший общий делитель. Возвращает массив, значения которого соответствуют значениям величин g, s и t.

Эта функция может использоваться для решения Диофантовых уравнений с двумя переменными. Это такие уравнения, которые имеют только целочисленные решения и имеют вид: a*x + b*y = c. За дополнительной информацией обращайтесь на » страницу "Диофантово уравнение" в MathWorld

Список параметров

num1

Объект GMP, целое число (int) или числовая строка (string).

num2

Объект GMP, целое число (int) или числовая строка (string).

Возвращаемые значения

Массив (array) GMP чисел.

Примеры

Пример #1 Решение линейного Диофантового уравнения

<?php
// Решение уравнения a*s + b*t = g
// где 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
"Ошибка во время решения уравнения\n";
}

// вывод: Решение: 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