How many relatively prime 4-tuples are there? Given a set of $n$ distinct integers $S = \{a_1,a_2,...., a_n\}$, count how many ways $4$ integers from the set $S$ can be chosen such that their GCD is equal to $1$.
 A: Suppose you know the set $P$ of primes that divide $a_1 a_2 \ldots a_n$.  Let $M(t)$ be the number of elements of $S$ divisible by $t$.  Note that the number of (unordered) $4$-tuples from $S$ that are all divisible by $t$ is ${M(t) \choose 4}$.  Then your answer is
$$ \sum_{A \subseteq P} (-1)^{|A|} {M(\prod A) \choose 4}$$
where $\prod A$ is the product of the primes in $A$.
For example, if $S = \{1,2,\ldots, 12\}$, $P = \{2,3,5,7,11\}$, but the only cases where $M(\prod A) \ge 4$ are $$\matrix{A = \emptyset, & M(1) = 12\cr
A = \{2\}, & M(2) = 6\cr A = \{3\}, & M(3) = 4}$$
and so your answer is $${12 \choose 4} - {6 \choose 4} - {4 \choose 4} = 479$$
This will not be an efficient algorithm in general: besides the difficulty of factoring, there may be lots of primes, and a huge number of subsets of these primes to consider.
A: Here's a reinterpretation of the Google translation of the relevant section of that page (http://e-maxx.ru/algo/inclusion_exclusion_principle):
We solve the inverse problem—count the number of "bad" quadruples, i.e. quadruples in which all the numbers are divisible by some $d > 1$.
We use the inclusion-exclusion formula, adding the number of quadruples, dividing by the divisor d(but possibly divisible, and a larger divisor):
$$\text{# of bad quadruples} = \sum_{d \geq 2} (-1)^{\text{deg}(d) -1} \cdot f(d),$$
where $\text{deg}(d)$ is the number of prime divisors of $d$ and $f(d)$ is the number of quadruples divisible by d.
To calculate $f(d)$, you simply count the number of multiples of $d$, and use the binomial coefficient to count the number of ways to choose a set of four of them.
Thus, this formula counts the number of quadruples divisible by a prime, and then subtract the number of quadruples that are divisible by the product of two primes, add the number of quadruples divisible by three primes, etc.
