Contradicting $p|n $s.t $p > \sqrt n$ I have proved a basic theorem in prime numbers, If $n \ge  2$ and $n$ is composite, then it is divisible by some prime $p \le \sqrt n$. This is a fairly basic result, and then my textbook shows me how the 'Sieve' works etc. But I am interested to know, does
$ p | n $ where p > $\sqrt n$
provide a contradiction? The first theorem does not imply anything about the existence/ non existence of such a prime...
I would like to know, because when asked to determine whether 111 is prime, I would say that $\sqrt{111} < 11 <\sqrt{121} $ and argue that 111 is not divisible by any of the primes less than 11. But i am currently not convinced that there does exists $p > \sqrt n$ such that p | n.
 A: The theorem doesn't say anything about the primes larger than $\sqrt{n}$, but for the type of argument you want to make, you don't need.
So Step by step here is what you are doing:


*

*Step 1: Check that $n$ is not divisible by any prime $p \leq \sqrt{n}$.


If it is, like for example if $3|111$, then $n$ is not prime, because you found a divisor. If it is not, go to step 2.


*

*Step 2: Assume by contradiction $n$ is not prime. Then by the above theorem, $n$ is divisible by some $p \leq \sqrt{n}$. But this is not the case, as you have seen in case 1. This is a contradiction.

A: Yes it can happen that there is a prime greater than $\sqrt{n}$ that divides $n$. For an explicit example note that $11 \mid 33$ and $11 > \sqrt{33}$. 
In fact, for any two distinct primes $p,q$ the number $pq$ will have a prime divisor larger than $\sqrt{pq}$, namely the larger of the two primes $p,q$. 
The point is though that for your application this is not relevant as you know if it is composite then there exists a "small" prime divisor. So, if there is no "small" prime divisor it cannot be composite. 
In our example, by the usual sieving you would in fact not find directly that $11 \mid 33$, but it does not matter as you would have found $3 \mid 33$ and this suffices to show that $33$ is composite. 
More generally, there is an involution on the set of divisors of $n$,  given by $d \mapsto n/d$, thus knowing all divisors of $n$ up to $\sqrt{n}$ is essentially as good as knowing all of them. 
