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 $\gcd \left(n\,a\,b_1\,\dots \,b_k\right)\=\gcd \left(n\,a\+c_1{b}_1\+\cdots \+c_k{b}_k\right)$ and $c_k\,\dots \,c_1$ is lexicographically minimal.

$\mathrm{with}\left(\mathrm{NumberTheory}\right)\:$

$\mathrm{ModExtendedGCD}\left(150\,0\right)$

$\mathrm{ModExtendedGCD}\left(150\,5\,75\,25\right)$

$\left[0\,0\right]$

$\mathrm{ModExtendedGCD}\left(150\,9\,75\,25\right)$

$\left[1\,1\right]$

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.