Let $\tau(n)$ denote the number of positive divisors of the positive integer $n$. Prove that there exist infinitely many positive integers $a$ such that the equation $$\tau(an) = n$$ does not have a positive integer solution $n$.

I don't understand how the solution below they get that $\alpha \geq p$ implies that $$p^{\alpha-p+1} \geq \dfrac{p}{p+1}(\alpha+1).$$ How did they get that? That is saying that $\dfrac{\tau(k)}{k} \geq \dfrac{p}{p+1}$.


enter image description here

  • 1
    $\begingroup$ Hint: that's equivalent to $f(\alpha) \ge f(p)$ for $f(x) = p^x / (x+1)$. $\endgroup$ – dxiv Oct 5 '16 at 0:16
  • $\begingroup$ @dxiv Can you explain why $\dfrac{p_i^{\alpha_i}}{\alpha_i+1}\tau(k) \geq \dfrac{2^{p-1}}{p} \tau(k)$? $\endgroup$ – user19405892 Oct 5 '16 at 1:27
  • $\begingroup$ I don't see how that relates to the original question, and I don't have the context to the entire proof. $\endgroup$ – dxiv Oct 5 '16 at 1:43
  • $\begingroup$ @dxiv That statement is in the proof. $\endgroup$ – user19405892 Oct 5 '16 at 1:43

The solution isn't saying that $\tau(k)/k \ge p/(p+1)$, the inequality $p^{\alpha - p + 1} \ge \frac{p}{p+1}(\alpha+1)$ follows independently of (1) for any $\alpha \ge p$. One simple way to see this is to note that when $\alpha = p$, both sides are equal to $p$; any increment of $\alpha$ by one causes the LHS to increase by a factor of $p$, while the RHS goes up by $<1$.

  • $\begingroup$ @user19405892 Possibly. The proof isn't that carefully composed, and it certainly isn't intended to be as tight as possible. $\endgroup$ – Erick Wong Oct 5 '16 at 3:47

Your Answer

