Smallest positive integer that is not coprime to any member of a set of integers Equivalently: given a list of numerators, find the lowest common denominator such that all the fractions formed can be simplified by cancellation.
Or: given a list of whole numbers, what's the smallest whole number that shares a common factor, greater than 1, with each of them? (Not necessarily the same factor shared with each member of the list.)
Clearly the given list cannot contain $\pm 1$ or no such number can be found! But for example, given $$\{8, 12, 45, 49\} = \{2^3, 2^2 \times 3, 3^2 \times 5, 7^2 \}$$ it is clear our desired number must include $2$ and $7$ in its prime factorisation, or else it will be coprime with $8$ and $49$. The fact $2$ is a factor guarantees a common factor with $12$ too, so we only need to ensure there is a common factor with $45 = 3^2 \times 5$ and this can be done most cheaply by incorporating a factor of $3$ in our prime factorisation. So the smallest number that does what we want is $2 \times 3 \times 7 = 42$, and indeed we find the greatest common divisors (highest common factors) are $\gcd(42, 8) = 2$, $\gcd(42, 12) = 6$, $\gcd(42, 45) = 3$ and $\gcd(42, 49) = 7$, so all greater than one. Alternatively, we observe that we can cancel down each of the fractions $\frac{8}{42} = \frac{4}{21}$, $\frac{12}{42} = \frac{2}{7}$, $\frac{45}{42} = \frac{15}{14}$ and $\frac{49}{42} = \frac{7}{6}$.
Does this procedure or function have a name? As a "lowest common non-coprime number" (though I can find no search engine hits under this name or close variants) it seems very closely related to the "lowest common multiple". Indeed, an obvious way to find a number that shares a factor with each member of the list is to just take
$$\operatorname{lcm}(8, 12, 45, 49) = 17640 = 2^3 \times 3^2 \times 5 \times 7^2$$
but this is clearly unnecessarily big. For starters, there's no need to raise the primes to a power — to ensure a common factor, each prime need only appear once. Dropping the unnecessary powers (i.e. taking the radical or square-free kernel — the largest divisor that is not, itself, divisible by a square number other than one) we get $2 \times 3 \times 5 \times 7 = 210$ but this is still not the smallest possible, since the prime factor $5$ wasn't required.
So what I want isn't the LCM, or even the radical of the LCM (or equivalently, the LCM of the radicals). In fact it's clear a good first step to simplify the problem would have been taking the radicals of all the numbers in our list, since the numbers sharing a factor with each of $\{2, 6, 15, 7\}$ are precisely the numbers sharing a factor with each of $\{8, 12, 45, 49\}$. Even then, it doesn't look like there's going to be a really neat algorithm to solve the problem. Consider:
$$\{2 \times 5, 3 \times 5, 2 \times 5\ \times 19 \} \text{ versus } \{2 \times 7, 3 \times 7, 2 \times 7 \times 19 \}$$
In the former case we can just use $5$ and a little thought shows it cannot be beaten; in the latter case, $7$ works but $2 \times 3 = 6$ is smaller. It seems we cannot avoid experimenting with different subsets of the prime factors to find the optimal answer. Nevertheless, the notion of a "lowest common non-coprime" function does seem interesting enough to crop up in some Math SE questions and I would like to know if mathematicians have given it a name, and whether there is an efficient algorithm (particularly if the list has already been given in prime-factorised form) for calculating it.
 A: [Edited]This problem is an integer linear programming problem.
Let the prime factors be ${ p_i | i=1\ldots n }$, and the radicals of the input numbers be $Rad(n_k) = \prod_{i\in S_k} p_i$. The problem is then finding
\begin{equation}
\min \sum_i x_i \log p_i
\end{equation}
given the constraints $x_i \in {0,1}$ and $\sum_{i\in S_k} x_i \geq 1$.
A: I think this should be NP-hard, even if the prime factorisation is given.
The idea here is that given an instance of the (NP-hard) set cover problem with $n$ sets $S_1,\ldots,S_n\subset U$, you can reduce it to this problem by choosing $n$ primes $p_1,\ldots,p_n$ between $2^n$ and $2^{n+1}$, and allocating one prime to each set. Now encode each element $x\in U$ by $f(x)=\prod_{i:x\in S_i}p_i$.
A minimal set cover corresponds to a minimal-cardinality set of primes whose product has a common factor with $f(x)$ for each $x$. Also, the bounds on the primes mean that the set with minimal product (which is what you need for your problem) must also be a minimal-cardinality set.
The difficulty here is finding a suitable set of primes in polynomial time. There is certainly an algorithm to do this in polynomial expected time - pick numbers in range at random and use a polynomial-time primality test. The prime number theorem implies there are enough primes in range that you find $n$ of them after an expected polynomial number (in $n$) of tries. Whether there is a deterministic algorithm to find such a set (even assuming, say, generalised Riemann hypothesis) I don't know.
A: This is a wrong answer, but a better greedy algorithm than the greedy algorithms provided so far.
If $P$ is your set of primes, and $N_1,\dots,N_k$ are the sets of prime factors for each number, then define, for $p\in P$: $$m_p=|\{i\mid p\in N_i\}|$$ Then find $p_0\in P$ which minimizes $v_p=\frac{\log p}{m_p}.$
Then remove the numbers divisible by $p_0,$ and start again.
So, for example, $\{3\cdot 7,5\cdot 7,2\}$ we get $m_2=1,m_3=1,m_5=1,m_7=2.$ $p_0=7$ minimizes, and we are left with the set $\{2\}.$ We get the answer $14.$
Essentially, $v_p=\frac {\log p}{m_p}$ is the “price per unit” of choosing $p$ as the first factor.
This kind of greedy algorithm usually doesn’t work in all cases, but at least it does better than giving the wrong “value,” minimizing $\log p$ (or equivalently, just minimizing $p.$) Minimizing $\log p$ is like minimizing the cost without looking at how many units it buys.

A simple example where my algorithm doesn’t work is $\{2\cdot 7,5\cdot 7\},$ which gives $10$ when $7$ is the answer.
Another example where my algorithm doesn’t work:
$$\{3,5\}\cup \left(3\cdot 7\cdot\{p_1,\dots,p_n\}\right)\cup \left(5\cdot 7\cdot\{p_1,\dots,p_n\}\right)$$
where the $p_i>7$ are distinct primes.
$m_7=2n, m_3=m_5=n+1,$ and for large enough $n,$ $$\frac{\log 7}{2n}<\frac{\log 3}{n+1}.$$ $n\geq 8$ is enough to fail.

The key reason the greedy algorithm doesn’t work is that at the next step, the value of the primes changes.
Also, when the $N_i$ are small, we have fewer options to choose from. It might be better to find a minimum-sized $N_i,$ and find the prime in that $N_i$ which minimizes the cost. In particular, then, when some $N_i$ are singletons, we get those elements immediately, as in my complicated counterexample.
But it still doesn’t solve the case $\{2\cdot7,5\cdot7\}.$
If $p_1<p_2<p_3,$ my algorithm gives the wrong answer for $\{p_1p_3,p_2p_3\}$ when $p_1^2<p_3<p_1p_2.$ The “smallest primes” greedy algorithm gives the wrong answer whenever $p_1p_2>p_3.$ So there is a slight improvement in this case.

Maybe slightly better: For $i=1,\dots,k$ let $p_i\in N_i$ minimize $v_{p_i}$ in $N_i.$ Let $s_i$ be the second best $v_{q_i}$ in $N_i,$ or $+\infty$ if $N_i$ has only one element. Then pick the $p_i$ which maximizes $s_{i}-v_{p_i}.$
That is, pick an element from a set where the cost increase goes up the most if we don't select $p.$
Then $\{p_1\cdot p_3,p_2\cdot p_3\}$ gives $p_3$ first if $\log p_2-\log(p_3)/2 >\log(p_3)/2-\log p_1$ or if $p_1p_2>p_3.$

This algorithm fails with $$\{2\cdot 31,3\cdot 31,5\cdot 31\},$$ since $\log(31)/3-\log(2)<\log(5)-\log(31)/3,$ so my greedy algorithm chooses $31$ first.
A: I think that a modified Sieve of Eratosthenes works, if you assume that you already know what the prime numbers are. Instead of applying it to the natural numbers, apply it to the set of integers under analysis.
If any of the numbers in the set have $2$ as a factor, record $2$ in a save list and remove all members of the set that are $\equiv 0 \bmod 2$.
If any of the remaining numbers in the set have $3$ as a factor, note $3$ in the save list and remove all members of the set that are $\equiv 0 \bmod 3$.
Repeat for each successively larger prime. You will eventually remove every number in any finite set, and you will have a finite list of saved primes.
Edits in response to comment by OP:
Multiply the members of the list to obtain a product.
Next determine the gcd of the set of numbers, and compare it with the product just obtained.
The smaller of the product and the gcd is at least a very good candidate for the smallest number not coprime to any member of the original set. If I can tighten this up further, I will add more.
