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)$?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityLet $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)$?
UPDATED
We can simply take $$B = \{1\} \cup \{ d\in D_n\ :\ d > n^{1/2} \}.$$
Then for any $d\in D_n$:
Then $$\sum_{b\in B} \frac{n}{b} = n + O(n^{1/2}\cdot\tau(n)) = O(n)$$ as required.