  Given two sets $A$ and $B$ of integers, we consider the problem of finding a
set $S \subseteq A$ of the smallest possible cardinality such the greatest
common divisor of the elements of $S \cup B$ equals that of those of $A \cup
B$. The particular cases of $B = \emptyset$ and $\#B = 1$ are of special
interest and have some links with graph theory. We also consider the
corresponding question for the least common multiple of the elements. We
establish NP-completeness and approximation results for these problems by
relating them to the Minimum Cover Problem.
