 NumberTheory - Maple Programming Help

# Online Help

###### All Products    Maple    MapleSim

Home : Support : Online Help : Mathematics : Number Theory : NumberTheory/ModExtendedGCD

NumberTheory

 ModExtendedGCD
 solutions to the modulo n extended GCD problem

 Calling Sequence ModExtendedGCD(n, a, b)

Parameters

 n - positive integer a - integer b - sequence of integers

Description

 • 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 $\mathrm{gcd}\left(n,a,{b}_{1},\dots ,{b}_{k}\right)=\mathrm{gcd}\left(n,a+{c}_{1}{b}_{1}+\cdots +{c}_{k}{b}_{k}\right)$ and ${c}_{k},\dots ,{c}_{1}$ is lexicographically minimal.

Examples

 > with(NumberTheory):
 > ModExtendedGCD(150, 0);
 $\left[\right]$ (1)
 > ModExtendedGCD(150, 5, 75, 25);
 $\left[{0}{,}{0}\right]$ (2)
 > ModExtendedGCD(150, 9, 75, 25);
 $\left[{1}{,}{1}\right]$ (3)

References

 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.

Compatibility

 • The NumberTheory[ModExtendedGCD] command was introduced in Maple 2016.
 • For more information on Maple 2016 changes, see Updates in Maple 2016.

 See Also