Small covering of divisors

Question

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)$?

Answer 1

UPDATED

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.