Euler's Criterion claims that $A^{\frac{(P-1)}{2}} \equiv_P \Bigl(\frac{A}{P}\Bigr)$ for prime $P$. My proof will use the fact that QRs forms a subgroup under modular multiplicative group $U(P)$. Then we will be able to utilize the Lagrange's theorem because we know the order of this subgroup.
$$Q = \lbrace x: x \equiv y^2 \space \text{for} \space x, y \in U(P) \rbrace$$
- Since $1$ is a QR for any $P$, identity will always be in this particular set.
- Our set is closed under modular multiplication since multiplication of QRs will always be a QR.
- Our set is closed under inverses as it can be easily shown:
$$x \in Q$$ $$x \equiv y^2$$
Then since multiplication of $x$ with it's inverse is congruent to $1$ (a QR),
$$y^2x^{-1} \equiv 1$$
the multiplication of $x^{-1}$ with a QR is congruent to a QR. This is only possible if $x^{-1} \in Q$. Hence our set is closed under inverses.
$Q$, fulfills all the conditions to be a subgroup of $U(P)$. Hence it is. Since any element in a group to the order of the group is equal to the identity by Lagrange's theorem, same holds true here.
We know that cardinality of $Q$ is $\frac{P-1}{2}$. Hence for $\forall A \in Q$,
$$A^{\frac{P-1}{2}} \equiv 1 \equiv \Bigl(\frac{A}{P}\Bigr).$$
Other part of the proof is trivial. It depends on the field property stating that square root of the identity is either $-1$ or $+1$. And also the fact that a $n$th degree equation have $n$ solutions.
What do you think of my proof. Is it correct?