# how many ways you can take 4 integers from the N numbers such that their GCD is 1

## how many ways you can take 4 integers from the N numbers such that their GCD is 1

Given N positive integers, not necessarily distinct, how many ways you can take 4 integers from the N numbers such that their GCD is 1.

for n=5 and the given numbers are.. 1 2 4 6 8 the answer is 4. how to calculate it?

• Do you know any properties of the numbers? For example, if I choose for the same n=5 the numbers 2,3,5,7,11 then the answer will be 5 choose 3 whereas in your example the calculation is 4 choose 3 as 1 with any 3 other numbers will work and the other 4 values have a common factor of 2. – JB King Apr 1 '15 at 20:24
• You can just take a prime in, and avoid that the 3 other numbers are divisible with that prime? Then the statement is true. – Atvin Apr 1 '15 at 20:24
• if no one is prime from n numbers, what will be the calculation? for example :- 4 ,9 ,15, 21,49 @Atvin – Shakhawat Hossain Apr 1 '15 at 20:31
• the numbers will be positive integers and they may not be distinct. @JB King – Shakhawat Hossain Apr 1 '15 at 20:32
• If all subsets with exactly 4 elements have a GCD of 1 then the answer is 5 choose 4 which is 5 since it is a matter of considering which integer is missing. Course if all 5 integers share a common factor greater than 1 then the answer is 0. For example if the numbers were 2 4 8 16 32, then there isn't any set that would work. – JB King Apr 1 '15 at 20:39

Counting $k$-subsets of $N$ integers whose gcd is $1$ is equivalent to the problem of counting set covers:
Given a set $X$, and a family $\cal F$ of $N$ subsets of $X$, count the $k$-subsets of $\cal F$ whose union is $X$.
To see this, let $X$ be the set of primes dividing any of the $N$ integers, and then identify each integer with the set of primes in $X$ not dividing that integer. Then the gcd of a set of $k$ integers is $1$ iff the union of the corresponding $k$ sets is all of $X$.
Set cover problems are difficult in general. Finding the minimum size of a set cover is known to be NP-hard. van Rooij [vR] gives an exponential-time algorithm for counting set covers. In general, an efficient algorithm is exceedingly unlikely. So, especially if $k$ is fixed at $4$, simply trying all $k$-subsets is a reasonable algorithm.