I'm studying elliptic curves in finite fields, and seeing an algorithm to find points of the curve, there's a point in which I have o check if an element $z\in\mathbb F_q$ is a square number, being $q$ an odd power of a prime.
I've seen it can be easily checked this way, we compute: $$z^{(q-1)/2}$$ if it's $1$, then it's a square, if it's $-1$, it's not.
I can't see why this works. I've tried first seeing the implication that if it's a square, that equality must hold, i.e. if $z=n^2$: $$n^{q-1}\equiv1\mod q$$
Any hints?
I'm going to assume $q$ is odd as this seem to be the relevant case. $\mathbb{F}_q^\times$ is a cyclic group of order $q-1$. So pick a generator $a$ then every element which is of the form $(a^2)^n$ are squares and the ones which are not of this form are non-squares (official term is quadratic residue and non-quadratic residue)
As there is even split of squares and non-squares and noting $x^{q-1}-1=(x^{(q-1)/2}+1)(x^{(q-1)/2}-1)$ we have the result.
This result is known as Euler's Criterion and I take you must have seen this before but forgot about it if you are studying elliptic curve :).