Prove that for every number that's not a prime, it exists a prime $p$ with $p\mid n$ and $p \leq \sqrt{n}$

Question

For $n \in \mathbb{N}$, if $n$ is not a prime and $n ≥ 2$, it exists a prime $p$ with $p\mid n$ and $p \leq \sqrt{n}$.

How would I mathematically correctly prove this sentence? I've thought about using prime factorization.

Answer 1

We can assume that $n \gt 1$. If $n$ is composite, then it can be written as the product of two factors, $n = ab$ where $a, b \gt 1$. Since $a \gt \sqrt n$ and $b \gt \sqrt n$ implies $ab \gt n$, then at least one of $a$ or $b$ is less than or equal to $\sqrt n$. We can arrange things so that $a \le \sqrt n$.

If $a$ is prime, then $p=a$. If $a$ is not prime, then it has a prime divisor, $p$, and $p \lt a \le \sqrt n$. The conclusion follows.

Answer 2

By definition, if n >= 2 is not a prime, there exists at least one prime p such that p | n.

The problem is to prove that there exists a p <= sqrt(n).

Suppose that, for all p_i, i = 1..k, primes which divide n, p_i > sqrt(n). Let v_i, i = 1..k, be n / p_i.

All v_i are integers, and are <= sqrt(n) (else p_i * v_i > n, absurd), and v_i divide n.

For any i = 1..k, v_i is either prime or composite; in any case, v_i, or its prime factors, are prime and < n, contradiction. This completes the proof.

Answer 3

Let $p$ the smallest divisor $>1$ of $n$. Then $p$ is prime.

Indeed, if $p$ were not prime, it woulde decompose as $p=ab$, with $a,b>1$, and $p$ wouldn't be the smallest non-trivial divisor of $n$.

Furthermore, if $n$ is not prime, $p\le \sqrt n$.

This is because, as $n=pa$ for some $a>1$, if $p>\sqrt n$, then $a=\dfrac np <\sqrt n$, and again, $p$ wouldn't be the smallest &c.

Answer 4

Let $p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ be the prime factorization of $n$. In particular let these primes be listed in order from least to greatest, that is, $p_1<p_2<\cdots<p_n$.

Then we can write,

$$ n = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k} = p_1 p_2 \left(p_1^{\alpha_1-1} p_2^{\alpha_2-1} \cdots p_k^{\alpha_k}\right) > p_1 p_1 \left(p_1^{\alpha_1-1} p_2^{\alpha_2-1} \cdots p_k^{\alpha_k}\right) \geq p_1p_1 \left( 1 \right) = p_1^2. $$

Thust $p_1^2 \leq n $ and in particular $p_1 \leq \sqrt{n}$.