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