The smallest prime divisor

#primes#smallest divisor#compositeness

Statement

Show that if $n>1$ is composite, then $n$ has a prime divisor $p\le\sqrt n$ .

Hint

Write $n=ab$ with $1<a\le b<n$ . Then $a\le\sqrt n$ .

Show solutionHide solution

Factorization. Since $n$ is composite, $n=ab$ with $1<a\le b<n$ .

Bound. If $a>\sqrt n$ , then $b\ge a>\sqrt n$ , so $ab>n$ , contradiction. Hence $a\le\sqrt