# Solving a inclusion-exclusion problem

Tags:
1. Nov 18, 2014

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. One of my friend told me that he can determine the number of ways with inclusion-exclusion principle and found the result 195 for given N=10 and the positive integers are 12,46,100,131,5,6,7,8,9.

I can not still catch how he used inclusion-exclusion principle to find out the number of ways.Hence I need an expert's help.
If the value of N varies how can I find out the number of ways using inclusion-exclusion principle? I'm a novice in learning inclusion-exclusion principle.So I need better explanation

2. Nov 18, 2014

### gopher_p

Given that the number of distinct $4$-sets that can be constructed from the given set is ${10\choose4}=210$ and that the number of $4$-sets that include both 6 and 8 (and therefore would not have the desired property) is ${8\choose 2}=28$, I'd say that your friend's solution is incorrect.

So I think you should demand a more in-depth explanation from your friend.

3. Nov 24, 2014

### Joffan

I think the meaning is that, choosing 4 numbers {a,b,c,d}, we then examine whether gcd(a,b,c,d) = 1. Choosing 6 and 8 does not shut down that possibility.

Clearly we do need at least one odd number, and while 7 and 131 are co-prime to all the other possible choices, 5 and 9 are not.

More difficult is finding the 10th number when only 9 are specified.