# Showing that a composite number has a small prime divisor?

At the moment I'm working on proving some statements and I've run into one that I can't seem to wrap my head around. It goes like this:

For $n \in \mathbb{Z}^+$, we define $\sqrt{n}$ as the real number $a$ such that $a^2 = n$. Show that if an integer $n > 1$ is composite, then it has a prime less than or equal to $\sqrt{n}$.

So far I've really only been able to prove by example using certain numbers but apart from that I'm rather lost on how I should approach and prove the statement. Any suggestions or help is much appreciated.

• What can you infer about the size of integer that has at least two (prime) factors $> \sqrt{n}\,?\ \$ – Bill Dubuque Jan 3 '15 at 19:46
• You can try using Fundamental Theorem of Arithmetic by decomposing n into primes. Then you can argue it out by comparing the value of the primes when necessary. – Novice Jan 3 '15 at 19:58

The smallest divisor $p$ of $n$ greater than $1$ is not $n$ because $n$ is composite. But $p$ is a prime, because if $p$ has a non trivial divisor $d$, then $d$ is a divisor of $n$, which contradicts the minimality of $p$ as divisor of $n$.

Let $q=n/p$. Since $q$ is a divisor of $n$, we have that $p\le q$, that is, $$p\le\frac np$$ or $$p^2\le n$$

This results from two facts:

1) If $n$ is composite, the smallest divisor $a$ of $n$ is $\,\le \sqrt n$.

Indeed, if $a>\sqrt n$, $b=n/a$ divides $n$ and $\,b<\sqrt n$, so $a$ would not be the smallest divisor of $n$.

2) The smallest integer that divides $n$ is prime. Indeed, if it were not prime, it would not be the smallest.

Lets assume has at least 2 divisors,if 2 of those divisors,lets name them $p$ and $q$,are bigger than $\sqrt{n}$ than you have that $p\cdot q>\sqrt{n}\cdot\sqrt{n}=n$ hence at least one of $p,q$ is smaller than $\sqrt{n}$