Show that a positive integer n is composite if and only if $\sigma(n)>n+\sqrt{n}$.

I saw this question, but I do not understand the blue marked inequality.

Suppose that $n$ is composite. Then $n=ab$ where $a$ and $b$ are integers with $1<a\leq b<n$. It followas that either $a\geq\sqrt{n}$ or $b\geq\sqrt{n}$. Consequently $\color{blue}{\underline{\color{black}{\sigma(n)\geq 1+a+b+n}}}$ $>1+\sqrt{n}+n>n+\sqrt{n}$. Conversely, suppose that $n$ is prime. Then $\sigma(n)=n+1$ so that $\sigma(n)\leq n+\sqrt{n}$. Hence $\sigma(n)>n+\sqrt{n}$ implies that $n$ is composite.

  • $\begingroup$ $\sigma(n)$ is sum of divisors. So in this case at least 1,a,b and n are divisors and hence the inequality. That is exactly how i have proceeded in my answer too $\endgroup$ – Shailesh Nov 17 '17 at 0:55

Necessary Condition

If $n$ is composite, then $n$ has a factor other than $1$ and $n$, say $p$. Then ofcourse $\frac{n}{p}$ is also a factor. By AM-GM inequality, we have

$p + \frac{n}{p} \ge 2\sqrt{n}$.

So, $\sigma(n) \ge n + 1 + p + \frac{n}{p} \ge n + 1 + 2\sqrt{n} \ge n + \sqrt{n}$

However, if $p$ and $\frac{n}{p}$ are the same (as pointed out by Especially Lime), then

$\sigma(n) \ge n + 1 + \sqrt{n} \ge n + \sqrt{n}$

Sufficient Condition

This is sufficiently straightforward by taking the contrapositive and proving it.

If $n$ is prime, then $\sigma(n) = n + 1 < n + \sqrt{n}$

  • $\begingroup$ $p$ and $n/p$ don't have to be different (which is why you appear to be getting $2\sqrt n$ instead of $\sqrt n$). $\endgroup$ – Especially Lime Nov 16 '17 at 16:09
  • $\begingroup$ @EspeciallyLime Good point. I have made a change in the answer $\endgroup$ – Shailesh Nov 16 '17 at 16:31
  • $\begingroup$ Thnx, I did it simular to your solution, but there is one inequality I do not understand. Can you please explain it to me? I just posted the picture! $\endgroup$ – WinstonCherf Nov 16 '17 at 17:06

Hint: What is $\sigma(p)$ for $p$ prime?. If $n$ is composite, you can write it as $n=pq$ where $p,q$ are coprime. Now you know four divisors of $n$, so have a lower bound for $\sigma(n)$.

  • $\begingroup$ Thnx for the hint. But how can I proof it that way? $\endgroup$ – WinstonCherf Nov 16 '17 at 16:16
  • $\begingroup$ One of $p,q$ is at least $\sqrt n$ $\endgroup$ – Ross Millikan Nov 16 '17 at 16:33

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.