1.2: Problem 24: Prove that if \(n\) is composite, it must have a prime factor \(p \leq \sqrt{n}\).
Proof
Suppose \(n\) is composite, then \(n\) has a unique prime factorization where
$$
\begin{align*}
n &= p_1 \cdot p_2 \ \cdots \ p_k
\end{align*}
$$
such that \(p_1,...,p_k\) are primes. Without the loss of generality, suppose that \(p_1\) is the smallest prime in the factorization. Then, \(p_1 \leq p_2 \cdots p_k\). Observe that
$$
\begin{align*}
p_1 &\leq p_2 \cdots p_k \\
p_1^2 &\leq p_1 \cdot p_2 \cdots p_k\\
p_1^2 &\leq n \\
p_1 &\leq \sqrt{n}
\end{align*}
$$