NumberTheory
ModExtendedGCD
solutions to the modulo n extended GCD problem
Calling Sequence
Parameters
Description
Examples
References
Compatibility
ModExtendedGCD(n, a, b)
n
-
positive integer
a
integer
b
sequence of integers
The ModExtendedGCD function computes the solution to the modulo n extended greatest common divisor problem.
If b is a sequence of length k, then the return value is a list c of length k of non-negative integers such that gcdn,a,b1,…,bk=gcdn,a+c1b1+⋯+ckbk and ck,…,c1 is lexicographically minimal.
withNumberTheory:
ModExtendedGCD150,0
ModExtendedGCD150,5,75,25
0,0
ModExtendedGCD150,9,75,25
1,1
Arne Storjohann. A solution to the extended GCD problem with applications. Proceedings of the 1997 International Symposium on Symbolic and Algebraic Computation (ISSAC '97), ACM Press, 1997.
The NumberTheory[ModExtendedGCD] command was introduced in Maple 2016.
For more information on Maple 2016 changes, see Updates in Maple 2016.
See Also
Download Help Document