If n Is A Composite Number Then There Is A Prime Divisor Less Than Or Equal To Root n

Since \(n\) is composite then:

$$n=ab$$

Assume \(a \le b\), then \(a \le \sqrt{n}\), otherwise:

$$\begin{align} a \gt \sqrt{n} &\implies b \gt \sqrt{n} \\ &\implies ab \gt \sqrt{n}\sqrt{n} \\ &\implies ab \gt n \end{align}$$

According to the Fundamental Theorem of Arithmetic, there is a prime \(p\) such that \(p|a\). That means \(p \le \sqrt{n} \).

Styles

(uses cookies)