Show: $p\text{ is prime}\iff p\text{ has no divisor }d\text{ where }1<d\leq\sqrt p$

Let $p\in\mathbb Z$, $p>1$. Prove that $$p\text{ is prime}\iff p\text{ has no divisor }d\text{ where }1<d\leq\sqrt p.$$

It is easy to show "$\implies$"; if $p$ is prime, then its only positive divisors are 1 and $p$ itself. Therefore, there are no divisors $d$ for which it holds that $1<d\leq\sqrt p<p$.

However, I'm having trouble with "$\impliedby$". I was thinking of using the contrapositive. So assume $p$ is not prime. Then we would like to show that $p$ has a divisor $d$ such that $1<d\leq \sqrt p$. I was thinking of using the fact that we can write $p$ as the (unique) product of finitely many prime numbers; $p=p_1\cdots p_k$, for some $k\in\mathbb N$.

From here on I wouldn't know how to continue. Could someone help me out?

EDIT

This is my proof then, based on the hints given:

Assume $p$ is not prime. Then $p$ must have at least one divisor $d$, such that $1<d<p$. We can therefore write $p=qd$, for some $q\in\mathbb Z$. This automatically means that $q$ is also a divisor of $p$. Now assume both $q$ and $d$ are greater then $\sqrt a$. Then $a=qd>a$. Contradiction. Therefore it holds that $q\leq\sqrt a$ or $d\leq\sqrt a$.

• Show that if $a=bc$ then $b\leq \sqrt{a}$ or $c\leq \sqrt{a}.$ Commented Feb 14, 2017 at 20:58
• Suppose $p$ is not prime but has no divisors smaller than $\sqrt{p}$. The product of any two divisors will be larger than $p$, contradiction... Commented Feb 14, 2017 at 21:06
• This question feels like a duplicate. Commented Feb 14, 2017 at 23:03

if $p$ is not prime, then it has some divisor $d>1$, and hence $1 < d \leq \sqrt{p}$ or $d > \sqrt{p}$.

If $d > \sqrt{p}$, then $p = dk$ for some $k \leq \sqrt{p}$.

Check the lemma (which also proves the existence of prime divisors):

If $n$ is not prime, the smallest non-trivial (i.e. $\ne 1, n$) divisor of $n$ is prime.

Indee, if this smallest divisor is not prime, it has a non-trivial divisor, which is also a divisor of $n$, contradicting the ‘smallest divisor’ property.

Corollary: If $n$ is not prime, the smallest non-trivial divisor $d$ of $n$ is $\le \sqrt n$.

Indeed, suppose $d>\sqrt n$. Then $\;e=\dfrac nd<\dfrac n{\sqrt n}=\sqrt n<d$. Contradiction.