# Small covering of divisors

Let $$D_n$$ be the set of divisors of $$n$$.

Does there always exists a $$B\subseteq D_n$$ such that $$D_n = \{\gcd(ab,n) \mid a\leq \sqrt{n}, b\in B\}$$ and $$\sum_{b\in B} \frac{n}{b}=O(n)$$?

We can simply take $$B = \{1\} \cup \{ d\in D_n\ :\ d > n^{1/2} \}.$$
Then for any $$d\in D_n$$:
• if $$d\leq n^{1/2}$$, we take $$(a,b)=(d,1)$$;
• if $$d>n^{1/2}$$, we take $$(a,b)=(1,d)$$.
Then $$\sum_{b\in B} \frac{n}{b} = n + O(n^{1/2}\cdot\tau(n)) = O(n)$$ as required.