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

Parameters

Description

Examples

References

Compatibility

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 gcdn,a,b1,,bk=gcdn,a+c1b1++ckbk and ck,,c1 is lexicographically minimal.

Examples

withNumberTheory:

ModExtendedGCD150,0

(1)

ModExtendedGCD150,5,75,25

0,0

(2)

ModExtendedGCD150,9,75,25

1,1

(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

NumberTheory