二個の平方数の和
x 1 − r y 1 ≡ x 2 − r y 2 ( mod p ) {\displaystyle {x_{1}-ry_{1}}\equiv {x_{2}-ry_{2}}\;(\operatorname {mod} \;p)}
となるものが存在する。 x = | x 1 − x 2 | , y = | y 1 − y 2 | {\displaystyle x=|x_{1}-x_{2}|,y=|y_{1}-y_{2}|} とすると
x 2 ≡ r 2 y 2 ≡ − y 2 ( mod p ) x 2 + y 2 ≡ 0 ( mod p ) {\displaystyle {\begin{aligned}&{x^{2}}\equiv {r^{2}y^{2}}\equiv {-y^{2}}\;(\operatorname {mod} \;p)\\&{x^{2}+y^{2}}\equiv 0\;(\operatorname {mod} \;p)\end{aligned}}}
である。 x , y < p {\displaystyle x,y<{\sqrt {p}}} であるから
0 < x 2 + y 2 < 2 p {\displaystyle 0<x^{2}+y^{2}<2p}
であり、故に
x 2 + y 2 = p {\displaystyle x^{2}+y^{2}=p}
である。
必要条件については A = x 2 + y 2 {\displaystyle A=x^{2}+y^{2}} が p ≡ 3 ( mod 4 ) {\displaystyle p\equiv 3\;(\operatorname {mod} \;4)} の形の素因数を持つと仮定して矛盾を導く(背理法)。 p | a {\displaystyle p|a} であれば
A = p a = x 2 + y 2 {\displaystyle A=pa=x^{2}+y^{2}}
と書ける。ここで p | x {\displaystyle p|x} であれば必然的に p | y {\displaystyle p|y} であり、 p 2 | A {\displaystyle p^{2}|A} であるから両辺を p 2 {\displaystyle p^{2}} で除するものとする。 p ⧸ | x {\displaystyle p\not |x} であれば x x − 1 ≡ 1 ( mod p ) {\displaystyle xx^{-1}\equiv 1\;(\operatorname {mod} \;p)} となる x − 1 {\displaystyle x^{-1}} が存在する。両辺に ( x − 1 ) 2 {\displaystyle (x^{-1})^{2}} を乗すると