Let n be a composite integer. Show that there exists a prime p dividing n, with $p \le n^\frac{1}{2}$

Given n is composite, there exists $a, b \in \mathbb{N}$ such that:

$$\begin{aligned} a \cdot b &= n \end{aligned}$$

Let's suppose $a <= b$.

If a = b, $a = b = \sqrt{n}$. So the prime p clearly exists.

If a < b,

$$\begin{aligned} a = \frac{\sqrt{n}}{b} \cdot \sqrt{n} \end{aligned}$$

Given $a \not = b \not = \sqrt{n}$, observe that$\sqrt{n} < b$, or else $a > \sqrt{n} > b$, which contradicts the assumption that a < b. This means $a < \sqrt{n}$. So such prime p would also exist.

$\Box$

# posted by rot13(Unafba Pune) @ 9:20 PM