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