# Proving that a composite number $n$ has a factor $k \leq \sqrt{n}$

Prove that a composite number $n$ has a factor $k \leq \sqrt{n}$.

Do we prove by proof by contrapositive?

Prove that a prime number $n$ has no factor $k \leq \sqrt{n}$.

Any tip?

-
The purported "contrapositive" is not really the contrapositive of the original statement. I suggest starting with the original statement. What do you know about a composite number? – Code-Guru Nov 29 '12 at 21:06

By definition if $n$ is composite then $n=ab$ for some positive $a,b$ both not $0$.

If $a\le \sqrt{n}$ then we are done, otherwise $a > \sqrt{n}$ so $b = \frac{n}{a} < \frac{n}{\sqrt{n}} = \sqrt{n}$.

-

If $n$ is composite, then $n=ab$ for some integers $a,b>1$. If $a,b > \sqrt{n}$, then $n=ab>\sqrt{n}\sqrt{n}=n$, a contradiction.

Note that the contrapositive of saying that a composite has such a factor is that if there is no such factor then it is not composite, not that a prime has no such factor.

-

Actually, since this question was not worded very precisely, this is true for prime numbers too. Every positive integer has $1\le\sqrt n$ as a divisor.

Slightly less tongue-in-cheek: The correct contrapositive (inserting the missing constraint $k>1$) is:

If a number $n$ has no divisors $1<k\le\sqrt n$, then $n$ is prime.

which is a useful characterization of primality. As stated in the other answers, this is true because if $ab=n$, then $\min(a,b)\le\sqrt n$ is a divisor of $n$.

-