|
gmp_gcdext
Calculate GCD and multipliers
(PHP 4 >= 4.0.4, PHP 5)
Calculates g, s, and t, such that
This function can be used to solve linear Diophantine equations in two
variables. These are equations that allow only integer solutions and have the form:
Parameters
ExamplesExample 792. Solving a linear Diophantine equation<?php Code Examples / Notes » gmp_gcdextfatphil
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. |
Change Languagegmp_abs gmp_add gmp_and gmp_clrbit gmp_cmp gmp_com gmp_div_q gmp_div_qr gmp_div_r gmp_div gmp_divexact gmp_fact gmp_gcd gmp_gcdext gmp_hamdist gmp_init gmp_intval gmp_invert gmp_jacobi gmp_legendre gmp_mod gmp_mul gmp_neg gmp_nextprime gmp_or gmp_perfect_square gmp_popcount gmp_pow gmp_powm gmp_prob_prime gmp_random gmp_scan0 gmp_scan1 gmp_setbit gmp_sign gmp_sqrt gmp_sqrtrem gmp_strval gmp_sub gmp_testbit gmp_xor |