Prove or disprove: If $n$ is not prime, then there exists an integer $a$ which divides $n$ and is in the interval $2\leq a \leq \sqrt{n}$. If $n$ is not prime, then there exists an integer $a$ which divides $n$ and is in the interval $2\leq a \leq \sqrt{n}$.
I need to either prove or disprove this.
My approach would to first attempt to test values for $a$ and $n$ to see if it seems true.
I have tried $a = 4$ and $n = 16$. This statement holds for these $n$ = 16. I then tried $n = 36$, and found an integer $a$ to be $4$. This statement so far seems true.
Next, I will try to prove this by proving the statement's contrapositive, because it seems easier to do that than proving the original statement.
This is where I am running into trouble.
 A: I think I can prove this directly! Here is what I would do. 
If $n$ is a square, obviously it suffices to choose $a = \sqrt{n}$. So suppose $n$ is not a square, and not prime. We do know that $n$ has a prime factorization, $n = p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$ with $\alpha_i \geq 1$. If $k>1$ then without loss of generality let $p_1 = \text{min}\{p_1,p_2,\ldots, p_k\}$. We know $$p_1^2 < p_1p_k \leq p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k} = n $$ and hence $p_1 < \sqrt{n}$ (and obviously $p_1 \geq 2$). Else if $k = 1$ we must have $\alpha_1 = 2j+1$ where $j \geq 1$ (this follows from choosing $n$ not to be a square, and $n$ not being prime). We see quickly that $$p_1^2 < p_1^{\alpha_1}  = n$$ and so $\space 2 \leq p_1<\sqrt{n}$ in either case. So a choice of $a$ as the smallest prime in $n$'s prime factorization will suffice. 
Can you proceed as you've said and arrive at this result through contrapositive?
A: Suppose $n$ is not prime. Then $n$ has a nontrivial factor, $c$. There are two possibilities:


*

*$2\le c\le\sqrt{n}$. Yay! We're done!

*$\sqrt{n}<c$. Uh oh, that's not good. But: can you think of another factor of $n$, related to $c$, which we know is "small" precisely because we know $c$ is "big"?

EDIT: You might find the following problem easier to think about, although the math is really the same:

Suppose $n$ can be written as the sum of two primes. Show that, for some prime $a$ with $a\le {n\over 2}$, $n-a$ is prime.

(The "prime" here is basically irrelevant - it's just added to make this not completely trivial.)
A: If $n$ is not prime, there exist 2 integers $a$ and $b$ (where $a$ and $b$ are both greater than $1$) and $n=ab$.
Assume towards contradiction that both $a$ and $b$ are greater than $\sqrt{n}$. Thus, $ab>\sqrt{n}\sqrt{n}$. Then, $ab>n$, $ab \neq n$.
So, if both $a$ and $b$ are greater than $\sqrt{n}$, then $a$ does not divide $n$. 
Thus, either $a$ or $b$ is less than or equal to $\sqrt{n}$. Without loss of genrality, let $a$ be the integer that is less than or equal to $\sqrt{n}$. 
$\therefore $ If $n$ is not prime, then there exists an integer $a$ which divides $n$ and is in the interval $2 \leq a \leq \sqrt{n}$.
