We will proceed by showing the group axioms hold under multiplication. Since this is a subset of \(U_p\) essentially by definition, this will imply it is a subgroup of it as well.

• It is clear that \(1\in Q_p\), since \(1\equiv 1^2\). So there is an identity.
• Next, if \(a\) and \(b\) are both in \(Q_p\) (with \(a\equiv s^2\) and \(b\equiv t^2\)), then \(ab\) is also a quadratic residue (since \((st)^2\equiv s^2 t^2\equiv ab\)).
• All that remains is to check that this set has inverses under multiplication.
  • Assume that \(a\equiv s^2\in Q_p\).
  • Then note that \[\left(s^{-1}\right)^2 a\equiv \left(s^{-1}\right)^2 s^2\equiv \left(s\cdot s^{-1}\right)^2\equiv 1\]
  • So by definition \[\left(s^{-1}\right)^2=a^{-1}\; ,\] which means that if \(a\in Q_p\) then \(a^{-1}\in Q_p\) as well.

(For those with some additional algebraic background, it turns out\(Q_p\) is in fact a quotient group of \(U_p\) as well, but we will not delve further into this here.)

• Certainly \(g^{2n}=\left(g^n\right)^2\), so the even powers of \(g\) are QR.
• But also note that if \(a\in Q_p\) and \(a=s^2\), that \(s\) and \(a\) are themselves still powers of \(g\) (by definition of \(g\)).
• So if \(s=g^n\) and \(a=g^m\) for some \(n,m\), then \[a=g^m\equiv g^{2n}\text{ mod }(p)\; ;\] so \[m\equiv 2n\text{ mod }(p-1)\; .\]
• This is only possible if \(m\) is even since \(p-1\) and \(2n\) are even.