Thread: n has divisor 1<d<sqrt(n)

1. n has divisor 1<d<sqrt(n)

Here is the problem. Let n be a positive integer, not = 1, and not prime, prove n has a divisor d such that 1<d<sqrt(n)

The way i began attacking this was by saying n is either even or odd. If n is even and not prime then n >= 4 and 2|any even integer and 1<2<sqrt(4). They problem im having is on the odd case there is no number like 2 that will divide all odd numbers so i dont know how to show a divisor would fall in this interval

2. Let $d$ be a divisor of $n$. Then $\frac n d$ is also a divisor of $n$; if both are less than $\sqrt n$ we have $n = d \times \frac n d < (\sqrt n)^2=n$ which is clearly impossible.

3. the conclusion is false.
the case when n=9 is a counterwexample.

4. As Shanks said, this is wrong, the interval should be $1 < d \leq \sqrt{n}$, otherwise perfect squares ( $4$, $9$, $16$, ...) fall short of the interval. I'll use the interval I mentioned.

Let us conjecture that $n$ is not prime, greater than one, and has not got any factor (divisor, whatever) $d$ such as $1 < d \leq \sqrt{n}$.

Then, since $n$ is not prime, it is composite and clearly has two divisors. Denote its two divisors $d_1$ and $d_2$, that is, ( $d_1 d_2 = n$).

Since $d_1$ and $d_2$ are not in $(1, \sqrt{n}]$, we must conclude that $d_1 > \sqrt{n}$ and $d_2 > \sqrt{n}$. Thus we must conclude that $d_1 d_2 > \sqrt{n}^2$, that is, $d_1 d_2 > n$. However we know that $d_1 d_2 = n$, so there is a contradiction.

$\therefore$ $n$ composite has at least one divisor in $(1, \sqrt{n}]$. Thus, if $d$ is any divisor of $n$, $1 < d \leq \sqrt{n}$.

________________________

EDIT : actually this proof is complete, because $d_1$ and $d_2$ needn't be prime, and any composite number can be represented as the product of two composite numbers. Correct me if I am wrong.

5. Originally Posted by Bruno J.
Let $d$ be a divisor of $n$. Then $\frac n d$ is also a divisor of $n$; if both are less than $\sqrt n$ we have $n = d \times \frac n d < (\sqrt n)^2=n$ which is clearly impossible.
Haha, oops. I didn't prove the right thing, but as Bacterius noticed we can just turn the proof around. And obviously we have to include $\sqrt n$ in the range (my mistake).

When $n$ is composite it has both a divisor $1 < d_1 \leq \sqrt n$ and a divisor $\sqrt n \leq d_2 < n$.