Let’s consider the subset $S=\{n,n-1,...,n-(k-1)\}$. There are $a,b\in S$ such that $a|b$. So, $a\leq b/2$. On the other hand $n-k<a\leq b/2\leq n$. That is $n-k<\frac{n}{2}$ Therefore, $k>\frac{n}{2}$. Let’s prove that $k>n/2$ satisfies. Suppose that there is a subset $S$ not satisfying the condition. Well, let’s consider subsets $S_{2k+1}= \{x=(2k+1)\cdot 2^l | l \in N, x\leq n \}$ where $2k<n$. It’s clear that $|S_{2k+1}\cap S|\leq 1$ and $\cup_{k=0}^{\frac{n}{2}} S_{2k+1}$ consists $M$. So, $|S|$ is less or equal to the number of sets $S_{2k+1}$, but the number of these sets is less or equal to $n/2$, therefore, $S$ isn’t a $k-element$ subset — contradiction.