# GCD of a subset

Let $A=\{i: 1 \leq i \leq n\} \subset \mathbb{N}$ and $B \subset A$, $|B|=k$ ($k < n$). What's the probability that $\gcd(B)>1$?

EDIT: $n$ and $k$ are given. I think this can be solved with inclusion-exclusion principle?

-
Perhaps it may be useful to know that the probability that a number $k < n$ selected being coprime to $n$ is $\phi(n)/n$. – user38268 Aug 5 '12 at 8:42

## 1 Answer

Not a complete solution, but a direction:

Let's denote by $A_p$ the event $\forall a\in B,p |a$. We want to know the probability of $\bigcup_{p \space prime}^{} A_p$.

Since we have We have $\lfloor\frac np\rfloor$ numbers that sivisible by $p$, we can get that $p(A_p)=\dfrac{|A_p|}{|\Omega|}=\dfrac{\big\lfloor\frac np\big\rfloor \choose k}{n\choose k}$.

$p(A_p)$ vanishes for $\lfloor\frac np\rfloor \lt k$.

Also, we have $A_p \cap A_q=A_{p \times q}$ for any $p$, $q$ primes.

So we can proceed with inclusion-exclusion principle: $$p(n,k)=\sum_{p \space prime}\dfrac{\big\lfloor\frac np\big\rfloor \choose k}{n\choose k}-\sum_{p, q\space primes}\dfrac{\big\lfloor\frac n{p\cdot q}\big\rfloor \choose k}{n\choose k}+...$$

-