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



Small covering of divisors
**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.


