Proof by contradiction concerning prime numbers. Where is the contradiction? Statement to be proved:

Prove that if $n > 1$ is not divisible by any prime number $p$ where $p \le \sqrt{n}$ then $n$ is a prime number.

Suppose we assume that $n$ is composite. We then prove that $n$ is divisible by a prime number $\le \sqrt{n}$. 
We proved that a composite number is divisible by a prime number $\le \sqrt{n}$. Can we fairly deduce from this that a prime number is not divisible by a number $\le \sqrt{n}$? I doubt this. As far as this proof is concerned, for all we know, both composite and prime numbers could be divisible by a prime number $\le \sqrt{n}$. Where is the contradiction?
 A: Your question really concerns the logic of contrapositives. You are proving that a sufficient condition for $n$ to be prime is that no prime number less than or equal to $\sqrt n$ divides $n$. One way of doing that is to show that a necessary condition for $n$ to be composite (negation of $n>1$ being prime) is the negation of the condition given above.
So, the logic works as follows. You want to show $P$ implies $Q$ (so $P$ is the sufficient condition). The method is to prove the contrapositive of the implication, that $\neg Q$ implies $\neg P$ (i.e. proving $\neg P$ is a necessary condition for $\neg Q$). Given that the contrapositive has been proven, one can be certain of $P$ implies $Q$ as well. One way to see that is to compare truth tables. But, one may be convinced the following argument: $P\implies Q$ follows from $\neg Q\implies \neg P$ since $P$ and $\neg Q$ would entail $\neg P$ a contradiction.
A: I am not sure if I understand your question. But if you want to prove that if $n$ is composite there must be at least one prime $p\leq\sqrt{n}$ that divides it:


*

*Each composite number has at least two prime factors.

*Assume the smallest prime that divides $n$ is $p$, and the next smallest $q$


Now if $p \gt \sqrt{n}$, that means $q \gt \sqrt{n}$, since if it wasn't, then it would not be larger than $p$. 
Two numbers multiplied together which both are larger than $\sqrt{n}$ can not be equal to $n$, because the square root function is strict increasing. Therefore the smallest prime dividing $n$ must be $\leq \sqrt{n}$.
A: " Can we fairly deduce from this that a prime number is not divisible by a number <= sqrt(n)?"
Well, obviously[#], but that's not at issue at all.  We were never asked to prove any such thing at all and we don't need to.
We were asked to prove "If $n >1$ is not divisible by any number, $k$ $1 < k \le \sqrt{n}$ then $n$ is prime".
We did a proof by contradiction "If $n$ is composite, then $k|n$ for some $k$"
THEREFORE "If $n$ is not divisible $\implies$ $n$ is not composite $\implies$ $n$ is prime."
Did we prove that $n$ prime $\implies$ $n$ is not divisible by any number less than $\sqrt{n}$?  No, we did not.  Why should we have?  That was not what we were trying to show
=====
[#]  Well, duh.  If $n$ is prime it's not divisible by anything other than itself and 1.  Duh!
A: we know any positive integer is always greater than  its sq.root of itself
              like
                     $25>\sqrt{25}$
               then $n>\sqrt{n}$.
         now given 
                    $p\le \sqrt{n}$
                therefore $n > \sqrt{n}\ge p$.
                   then  $n>p$
                    and $p>1$.
              therefore $p$ not equal to $n$ nor $1$.
let $p$ divides $n$.
 now $p$ is neither $n$ nor $1$
 but divides $n$.
now if $n$ is prime then it would only be divisible by $n$ and $1$.
 but $p$ divides $n$ though it is neither $n$ nor $1$.
therefore $n$ is not prime , i.e $n$ will be prime if it is not divisible by $p$ 
 such that $p\le\sqrt{n}$. (proved)
