Composite Number Has Prime Factor Less Than Or Equal To Its Square Root

Theorem

Let $n \in \N$ and $n = p_1 \times p_2 \times \cdots \times p_j$, $j \ge 2$, where $p_1, \ldots, p_j \in \Bbb P$ are prime factors of $n$.

Then $\exists p_i \in \Bbb P$ such that $p_i \le \sqrt n$.

That is, if $n \in \N$ is composite, then $n$ has a prime factor $p \le \sqrt n$.

Proof

Let $n$ be composite such that $n \ge 0$.

From Composite Number has Two Divisors Less Than It, we can write $n = a b$ where $a, b \in \Z$ and $1 < a, b < n$.

We may assume, without loss of generalization, that $a \le b$.

Let $a > \sqrt n$. Then $b \ge a > \sqrt n$.

However, if $b \ge a > \sqrt n$ is true, then $n = a b > \sqrt n \sqrt n > n$.

This is clearly a contradiction.

So $a \le \sqrt n$.

From Positive Integer Greater than 1 has a Prime Divisor it follows that there is some prime $p$ which divides $a$.

From Integer Absolute Value Greater than Divisors, we have that $p \le a$ and so $p \le \sqrt n$

From Divides is Partial Ordering on Positive Integers, $p \backslash n$.

Hence the result.

$\blacksquare$

Comment

Suppose we are testing a number to see whether it is prime, or so as to find all its divisors.

One way to do this (which may not be the most efficient in all circumstances, but it gets the job done) is to divide it by successively larger primes until you find one that is a factor of the number.

Eventually you're bound to find a prime that is a factor, by Positive Integer Greater than 1 has a Prime Divisor.

However, this result tells us that we don't need to go out that far.

If we've tested all the primes up to the square root of our target number without finding a divisor, we don't need to go any further because we know that our target number is prime after all.