Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

3 Answers

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|improve this answer
add comment

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.