Exercise 553Number theory › PrimesHigh schoolAdded 3 Nov 2026

Smallest prime divisor

#smallest divisor#compositeness#sqrt bound

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. $n=ab$ with $1<a\le b<n$ .

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

Prime divisor. Any prime divisor $p$ of $a$ satisfies $p\le a\le\sqrt n$ .

Conclusion. To test primality of $n$ , it suffices to test divisibility by primes up to $\sqrt n$ .