Prove that $n$ must be prime. Here is the complete question:
Suppose that $n=2^{m}h+1$, where m is an integer and $h$ is an odd positive integer less than $2^{m}$. Suppose that there is an integer $a$ such that $a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space n)$. Prove that $n$ must be prime. 
[Hint: show first that if $p$ is any prime divisor of $n$ then $ord_{p}(a)$ must be a divisor of $n-1=2^{m}k$ and not a divisor of $\frac{1}{2}(n-1)=2^{m-1}h$, and use Fermat's Little Theorem to deduce that $p\equiv1 (mod \space 2^{m})$.]
This is one of the hardest exam practice questions for my class, and I've been thinking over this question a few days and I think I am close, but I just need a bit of help. I am trying to follow the hint as much as I can. Here is what I have so far:
Assume $p$ is a prime divisor of n.
Since $p|n$ and  $n|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$
$\implies p\nmid a$
Then by Fermat's Theorem, 
$a^{p-1}\equiv 1 (mod \space p) $ and we have that $p|a^{\frac{1}{2}(n-1)}+1 = a^{2^{m-1}h}+1$
$\implies a^{\frac{1}{2}(n-1)}\equiv -1 (mod \space p)$ $\implies a^{(n-1)}\equiv 1 (mod \space p)$ (after squaring both sides)
So we have that $p | a^{p-1}-1$ and $p | a^{n-1}-1$ 
$\implies a^{p-1}\equiv a^{n-1} \equiv 1 (mod \space p)$ 
(here is where I am a bit fuzzy. I am sort of just assuming $ord_p(a) = p-1$)
so $(p-1)|(n-1) = 2^{m}h$ (also not too sure about that?)
It follows that $2^{m}|(p-1)$ i.e. $(p-1) = 2^{m}h$
So $n = (p-1)+1$ $\implies n$ must be prime, since our assumption was that $p$ is a prime.
I know I haven't used the hint exactly and I also haven't made use of the fact that $h$ is a an odd smaller than $2^{m}$. 
If someone can help me, it would be greatly appreciated!! 
 A: You can't simply assume $\operatorname{ord}_p(a) = p-1$. However, you are given
$$a^{\frac12(n-1)} \equiv -1 \pmod{n} \Rightarrow a^{\frac12(n-1)} \equiv -1 \pmod{p} \Rightarrow a^{n-1} \equiv 1 \pmod{p}.$$
Since $\operatorname{ord}_p(a)$ is the smallest positive number $k$ with $a^k \equiv 1 \pmod{p}$, you can deduce that  $\operatorname{ord}_p(a) \mid n-1$.
Let  $p = 2^s\cdot u + 1$ with $u$ odd. Then $a^{p-1} = a^{2^su} \equiv 1 \pmod{p}$. But $a^{2^{m-1}h} \equiv -1 \pmod{p}$, hence $(a^{2^{m-1}u})^h \equiv -1 \pmod{p}$, and thus $s \geqslant m$, so $p \equiv 1 \pmod{2^m}$, hence $p \geqslant 2^m + 1$.
Now, if $n$ were not prime, it would have at least two prime factors, all of which are $\equiv 1 \pmod{2^m}$, and hence the product of two such primes would be $\geqslant (2^m+1)^2$.

More detailed exposition:
We have an integer $n = 2^m\cdot h +1$ with $0 < h < 2^m$ odd, and we are assured of the existence of an integer $a$ with $a^{\frac12(n-1)} \equiv -1 \pmod{n}$.
To show that $n$ is prime, we take any prime $p$ dividing $n$ - such a prime exists, since we have $1 < 2^m$, hence $1 < n$ by $0 < h < 2^m$ - and then show that $p = n$. Since $m \geqslant 1$, it follows that $n$ is odd, and hence so is $p$. Write $p = 2^s\cdot u + 1$ with $u$ odd. Since by assumption
$$n \mid \left(a^{\frac12(n-1)} +1\right),$$
and $p$ divides $n$, we also have
$$p \mid \left(a^{\frac12(n-1)} +1\right) \iff a^{\frac12(n-1)} \equiv -1 \pmod{p}.$$
In particular, $a$ is not a multiple of $p$. By Fermat's theorem, we know that $\operatorname{ord}_p(a) \mid (p-1)$, hence
$$a^{p-1} = a^{2^s\cdot u} \equiv 1 \pmod{p}.$$
But $\frac12(n-1) = 2^{m-1}h$, and
$$\left(a^{2^{m-1}u}\right)^h = \left(a^{2^{m-1}h}\right)^u \equiv (-1)^u \equiv  -1 \pmod{p},$$
so $a^{2^{m-1}u} \not\equiv 1 \pmod{p}$, but $a^{2^su} \equiv 1 \pmod{p}$, hence $s > m-1$, or equivalently $s \geqslant m$.
Thus we have $2^m \mid 2^s\cdot u = (p-1)$. In particular, $p \geqslant 2^m + 1$. But
$$\left(2^m+1\right)^2 = 2^{m}\cdot 2^m + 2\cdot 2^m + 1 = 2^m\cdot h + 1 + \left(2^m(2^m-h) +2\cdot 2^m\right) > 2^mh+1 = n,$$
so $p > \sqrt{n}$.
If $n$ were composite, it would have at least one prime factor $\leqslant \sqrt{n}$, but we just saw that all prime factors of $n$ are $> \sqrt{n}$, hence $n$ must be prime.
