Finding the size of the smallest subset with GCD = 1
This problem is equivalent to the following, and it's trivial to construct reduction both ways.

Given a list of bit vectors, find the minimum number of them such that and all of them result the $0$ bit vector. $(*)$

Then we show set cover reduces to $(*)$. By set cover, I mean given a list of sets $S_1,\ldots,S_k$, find the minimum number of sets that covers their union. 

We order the elements in the sets to be $a_1,\ldots,a_n$. Let $f(S) = (1-\chi_{a_1}(S),\ldots,1-\chi_{a_n}(S))$, where $\chi_x(S) = 1$ if $x\in S$, 0 otherwise. Note this function is a bijection so it has a inverse. 

Now, if we solve $(*)$ on $f(S_1),\ldots,f(S_k)$, and the solutions is $\{ f(S_{b_1}),\ldots,f(S_{b_m})\}$, then $\{ f^{-1}(S_{b_1}),\ldots,f^{-1}(S_{b_m})\}$ is the solution to set cover.

Thus I would think this problem is testing one's ability to prune the search space.