Bézout's identity

Bézout's identity states that for a set of distinct non zero integers A_i, there exists a linear combination of A_is equals to their GCD. It is not difficult to realize without proof if we know extended Euclidean algorithm before. Here we present an idea to solve the following problem using this lemma:

Given N distinct positive integers, find a minimal subset so that any integer in this set equals to the linear combination of the subset.

By using the lemma, it is obvious to find a subset of the set so that the GCD of it equals to the GCD of the set itself. Suppose the integers are bounded by certain value so that we can limit the number of total distinct prime factors for an integer. Suppose the upper bound is 10,000,000, at most 8 distinct prime factors are enough to factorize an integer. If we first divide the set by their GCD, we are going to find a minimal subset of relatively prime numbers instead. We can finally use Dynamic Programming to solve the problem.