When is a number square in Galois field $p^n$ if it's not square mod $p$? Here is the problem, that I'm stuck on.
There is no square root of $a$ in $\mathbb{Z}_p$. Is there square root of $a$ in $GF(p^n)$?
Well, it's certainly true that $$x^{p^n}=x$$ and $$x^{p^n-1}=1$$ for nonzero $x$. 
If there is such an $x$ that $a=x^2$ then $$a^{\frac{p^n-1}{2}}=1$$
Now this actually is an equation in $\mathbb{Z}_{p}$ only, so I can write
$$a^{\frac{p^n-1}{2}}\equiv 1\mod p$$
Now the answer seems to be just a touch away because I know that $x^2\equiv a \mod p$ iff $a^{(p-1)/2}\equiv 1 \mod p$. How can I tie the ends together, what am I missing?

Because finite fields are uniquely determined by their order, you know that if $a\in\Bbb Z$, then one of two things is true, either $a=x^2$ for some other $x\in\Bbb Z/p=\Bbb F_p$, or not. In the case it is not, then $x^2-a$ is irreducible over $\Bbb F_p$. If so then
$$\Bbb F_p[x]/(x^2-a)\cong\Bbb F_{p^2}$$
and this is independent of choice of non-square $a\in\Bbb F_p$. Since there is only one field of order $p^2$, all integers are squares iff
$$\Bbb F_{p^n}\supseteq\Bbb F_{p^2}\iff 2|n$$
