Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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}$.

share|cite|improve this answer

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.

share|cite|improve this answer

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$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.