Prove that $N$ is composite if and only if $p|N$ for some $p$ prime, $p\leq \sqrt{N}$. Show that $N$ is composite if and only if $p|N$ for some $p$ prime, $p\leq \sqrt{N}$
I have absolutely no idea on how to start this, could you guys give me some tips?
I'll update if I can come up with something...
 A: By the Fundamental theorem of arithmetic, we may write $N>1$ as the product of primes, i.e. $$N=p_1p_2\cdots p_k$$
and this is unique if we insist that $p_1\le p_2\le\cdots \le p_k$.  We now have two cases:


*

*$k=1$, i.e. there is only one prime in the factorization.  Then $N$ is prime.

*$k\ge 2$, i.e. there are at least two primes in the factorization, and thus $N$ is composite.  Since $k\ge 2$, the product $p_2\cdots p_k$ has at least one prime in it, and that prime is at least $p_1$.  Thus, $p_1\le (p_2\cdots p_k)$.  Multiplying both sides by $p_1$ we get $p_1^2\le p_1(p_2\cdots p_k)=N$.  Hence $p_1^2\le N$; we take square roots to get $p_1\le \sqrt{N}$.
A: Hints
One direction of the proof should be just an application of the definition of composite, and nothing else.
For the other direction, prove this by contradiction.  Assume that all primes dividing $p$ were greater than $\sqrt{N}$.  What happens when you multiply these primes together again?

Answer
First part: We aim to show that, if $p\mid N$ and $p\leq \sqrt{N}$, then $N$ is composite.  For sake of reaching a contradiction, assume $N$ is prime.  Then, $N$ is only divisible by itself and $1$.  But, $1 < p \leq \sqrt{N}$ is a divisor of $N$ by hypothesis--a contradiction!  Hence, $N$ is composite.
Now, going the other way: If $N$ is composite, it is divisible by some primes (not necessarily unique) $p_1, p_2,\ldots, p_k$, $k\geq 2$.  Suppose that all of $p_i$ were greater than $\sqrt{N}$.  Then:
$$N=p_1p_2\cdots p_k > \underbrace{\sqrt{N}\cdots\sqrt{N}}_{k\;\text{times}} > N$$
Clearly, this is a contradiction.  Thus, at least one of the $p_i$ must be less than the square root of $N$.
