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

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.