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

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.

• $\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 – 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}$

• $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$). – Especially Lime Nov 16 '17 at 16:09
• @EspeciallyLime Good point. I have made a change in the answer – Shailesh Nov 16 '17 at 16:31
• 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! – 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)$.

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