UserManual

gcd

The module provides functions related to the greatest common divisors of integers.

Functions

gcd(a,b)

Return the greatest common divisor of 2 integers a and b.
If one of the arguments is negative, then the result may be negative.

binarygcd(a, b)

Return the greatest common divisor of 2 integers a and b by binary gcd algorithm.

extgcd(x,y)

Return the greatest common divisor d of two integers x and y and u, v such that d = x * u + y * v. The returned value is a tuple (u, v, d).

lcm(a,b)

Return the least common multiple of 2 given integers a and b. If both entries are zero, then it raises an exception.

gcd_of_list(integers)

Return a list [d, [c1, ..., cn]] for the given list integers=[x1, ..., xn] such that
d = c1 * x1 + ... + cn * xn,
and of course d is the greatest common divisor of them.

coprime(a, b)

Return True if a and b are coprime, False otherwise.

pairwise_coprime(int_list)

Return True if all integers in int_list are pairwise coprime, False otherwise.


Last-modified: 2005-12-18 (Æü) 17:35:57