Mod Extended GCD - Maple Help

Home : Support : Online Help : Mathematics : Number Theory : Mod Extended GCD

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

 > $\mathrm{with}\left(\mathrm{NumberTheory}\right):$
 > $\mathrm{ModExtendedGCD}\left(150,0\right)$
 $\left[\right]$ (1)
 > $\mathrm{ModExtendedGCD}\left(150,5,75,25\right)$
 $\left[{0}{,}{0}\right]$ (2)
 > $\mathrm{ModExtendedGCD}\left(150,9,75,25\right)$
 $\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.