\((\mathbb{Z}/p\mathbb{Z})^{\times}=\left\{ 1,g,g^{2},\cdots\cdots,g^{p-2}\right\} \)とする。

\(QR(a,p)=1\)のとき

\(a=g^{2k}\)であるのでフェルマーの小定理を使うと、\(a^{\frac{p-1}{2}}=g^{k(p-1)}=\left(g^{p-1}\right)^{k}\overset{p}{\equiv}1\)

\(QR(a,p)=-1\)のとき

\(a=g^{2k+1}\)であり、\(g^{\frac{p-1}{2}}\)は位数2の元なので、\(a^{\frac{p-1}{2}}=g^{k(p-1)}g^{\frac{p-1}{2}}=g^{\frac{p-1}{2}}\overset{p}{\equiv}-1\)

*

これより、\(a\)が平方剰余、平方非剰余のどちらでも成り立つので与式は成り立つ。