up previous next
GCDFreeBasis

determine coprime factor base for a set of integers or ring elements

Syntax
GCDFreeBasis(L: LIST of INT): LIST of INT
GCDFreeBasis(L: LIST of RINGELEM): LIST of RINGELEM

Description
This function returns a coprime factor base for a set of integers or ring elements from a true GCD domain. A least cardinaility base can be obtained by performing all possible GCD and exact division operations iteratively. The factor base produced produced by these functions may not be of least cardinality.

Given a set N = [ N_1,...N_k ] we seek a factor base G = [ G_1,...,G_s ] of pairwise coprime values such that each N_i is a product of powers of the G_j.

In general there many different such sets G for a given set N. Such sets are sometimes called a GCD-free bases for N.

Example
/**/  GCDFreeBasis([factorial(20), factorial(10)]);
[46189, 4, 14175]
/**/  use QQ[x,y];
/**/  GCDFreeBasis([x^2*y^4, x^3*y^6]);

See Also