gmp_gcdext

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

gmp_gcdextCalcula MDC e multiplicadores

Descrição

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

Calcula g, s, e t, de forma que a*s + b*t = g = gcd(a,b), onde gcd é o máximo divisor comum (MDC). Retorna um array com os respectivos elementos g, s e t.

Esta função pode ser usada para resolver equações lineares de Diophantine com duas variáveis. São equações que permitem somente soluções com inteiros e têm a forma: a*x + b*y = c. Para mais informações, acesse a página » "Equação de Diophantine" (em inglês) na MathWorld.

Parâmetros

num1

Um objeto GMP, um int ou uma string numérica.

num2

Um objeto GMP, um int ou uma string numérica.

Valor Retornado

Um array de números GMP.

Exemplos

Exemplo #1 Resolvendo uma equação linear de Diophantine

<?php
// Soluciona a equação a*s + b*t = g
// onde a = 12, b = 21, g = MDC(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 = "Solução: %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
"Erro ao solucionar a equação\n";
}

// saída: Solução: 12*2 + 21*-1 = 3
?>

add a note add a note

User Contributed Notes 1 note

up
0
FatPhil
20 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