# Thread: Sum of positive divisor

1. ## Sum of positive divisor

Need help on the following:

Show a positive integer $\displaystyle n$ is composite iff $\displaystyle \sigma(n) > n + \sqrt{n}$.
$\displaystyle \sigma(n)$ denote the sum of positive divisor of n.

2. Originally Posted by kleenex
Need help on the following:

Show a positive integer $\displaystyle n$ is composite iff $\displaystyle \sigma(n) > n + \sqrt{n}$.
$\displaystyle \sigma(n)$ denote the sum of positive divisor of n.

Say $\displaystyle n>1$.

$\displaystyle n$ is prime if and only if $\displaystyle \sigma (n) = n+1$. Thus, $\displaystyle n$ is compositive if and only if $\displaystyle \sigma (n) > n+1 \mbox{ or }\sigma (n) < n+1$. But we cannot have $\displaystyle \simga(n) < n+1$ because $\displaystyle \sigma (n) > n+1$ (since $\displaystyle n$ and $\displaystyle 1$ are always divisors). Thus, $\displaystyle n$ is compositive if and only if $\displaystyle \sigma (n) > n+1$. Thus, if $\displaystyle \sigma (n) > n+\sqrt{n} >n+1$ and so it is compositive.

3. Thank you,

I was thinking:
Let $\displaystyle d|n$ where $\displaystyle 1<d<n$ so $\displaystyle 1<n/d<n$. If $\displaystyle d \leq \sqrt n$ then $\displaystyle n/d \geq \sqrt n$ but then I don't know what next. But your way is easier than my.

On the other hand you got syntax error.

4. OK, to complete your proof you have to show that if a number $\displaystyle n$ doesn't have a prime divisor less or equal than $\displaystyle \sqrt[]{n}$ it's prime

Indeed, suppose it doesn't have have a prime divisor less or equal than $\displaystyle \sqrt[]{n}$, then n has at least two prime divisors $\displaystyle p_1,p_2$ (if it's composite) such that $\displaystyle p_1\cdot{p_2}\leq{n}$.

But $\displaystyle p_1,p_2>{\sqrt[]{n}}$ so the product $\displaystyle p_1\cdot{p_2}>n$ and this is absurd

So every composite number $\displaystyle n$ has at least one prime divisor $\displaystyle p$ such that $\displaystyle p\leq{\sqrt[]{n}}$

But you can only achieve the equality if $\displaystyle n$ is a perfect square, and in that case $\displaystyle \sigma(n)\geq{n+\sqrt[]{n}+1}>n+\sqrt[]{n}$ so the inequality holds

Otherwise it's not a perfect square and it has a prime divisor $\displaystyle p$ such that $\displaystyle p<\sqrt[]{n}$
So $\displaystyle \frac{n}{p}>\sqrt[]{n}$ is a divisor of $\displaystyle n$ and therefore $\displaystyle \sigma(n)>n+\sqrt[]{n}$