# Proof about least prime numbers dividing n

Assume $n \in N$ is composite. Prove if p is the least prime number dividing n, then $p^2 \leq n$

Approach: I tried to write the first few prime and composite numbers but I didn't any patter. Any hints to start this problem

• Hint: if $p$ divides $n$ then $n=pm$. Now let $q$ be the least prime dividing $m$. – lulu Jun 3 '16 at 12:00

Hint: If $p$ is a prime number dividing $n$, then $n = kp$ for some integer $k$ (which is not 1 as $n$ is composite). What can you say about $k$ if $p^2 > n$?

• Or rather, what can you say about the prime factors of $k$. Are they prime factors of $n$? Are they smaller than $p$? – Anamaki Jun 3 '16 at 12:13
• by exahustion, I see that k is greater than p, but why does it make sense? – TheMathNoob Jun 3 '16 at 12:16
• How do you get that? I don't understand – Anamaki Jun 3 '16 at 12:18
• 10=5*2, so 2 is the least prime number and 5 is k – TheMathNoob Jun 3 '16 at 12:19
• But we also assumed $p^2 > n$, remember. – Anamaki Jun 3 '16 at 12:21

Let $p$ be the least prime dividing $n$. Since n is a composite, $\exists q \neq 1$ prime, such that $q | \frac{n}{p}$. By assumption $p \leq q$

$pq \leq n$ as $p$ and $q$ both divide $n$.

$\implies pp \leq pq \leq n$

$p^2 \leq n$

By the Fundamental Theorem of Arithmetic, you can write $$n=\prod_{j=1}^hp_j^{\alpha_j}$$ where $p_1< p_2<\ldots< p_h$ and $\alpha_j$ are positive integers. By assumption, we have $p=p_1$. Moreover, because $n$ is composite, we know that either $h>1$ or $\alpha_1>1$. In the former case, $n\geq p_1^{\alpha_1}p_2^{\alpha_2}\geq p_1p_2>p_1^2=p^2$; in the latter case, $n\geq p_1^2=p^2$.