「pを素数とするとき、x²+y²=p となる自然数x,y はあるか？」

まずはp=2に対しては1²+1²=2なので答えはYesです。

つぎにpを奇素数として、先ほどと同じように進めてみます。 こんどは因数分解といっても係数を整数にとることができません。 それでも強引に x²+y²=(x+i y)(x-iy) と因数分解してみます。ここでiは2乗すると-1となる虚数です。 さっきは整数の素因数分解だったのですが、 今度は整数とiという虚数を含めた集合の素因数分解を考えなければならないのです。 実はこの場合もうまくいくのです！ すなわち、Gaussの複素整数 a+bi（aとbは整数）は、 順番を度外視して一意的に素数の積にあらわされるのです。 （なお、複素整数内で分解不可能な数を素数、 逆数のある±1、±i は単数と呼び、単数の差は無視します。）
これは複素整数たちにも割り算があるということで説明がつきます。 普通の整数a の b による割り算は、商をq、余りをrとすると、 a=qb+r、であって 0≦r≦ b-1 でした。 Gaussの複素整数αのβによる割り算は、 α=Qβ+R であって、|R|<|β|という形になります。 ここでQとしてはα/βに最も近い複素整数を取ればいいのです。 このような割り算があると、 Euclidの互除法によってαとβの公約数を求めることができることになります。 今、πが素数として、αγがπで割れるとします。 するとαかγはπで割れなければなりません。 なぜなら、α、γがともにπでわれないとすると、 互除法によって、あるx,y,x',y'によって、αx+πy=1、γx'+πy'=1 となり、 αγがπで割れなくなってしまうからです。 これでGaussの複素整数での素因数分解の一意性が言えます。

このGaussの複素整数の性質を使って、上の問題を解きます。 まず、解が存在するとしてその解をx=a,y=bとし、 π=a+bi、π'=a-biとおきます。 ここでππ'がpで1回しか割れないのでa,bはpと素であることに注意します。 式a²+b²=p をpで割った余りの数で眺めてみましょう。 (mod p と書くことします。） するとa²+b²≡0 (mod p)。 ここで、bb'≡1 (mod p)となるb'の2乗を両辺にかけると (ab')²+1≡0 (mod p)となり、 2乗すると-1とmod pで合同になる数が存在しなければなりません。 mod p における乗法群は、位数p-1の巡回群になることから このような数が存在するためには、p-1が4で割れること、 すなわち pは4で割ると1 余る素数であることが 必要十分条件となることがわかります。
逆に p は4で割ると1 余る素数だとしましょう。 そして、r を r²≡-1(mod p)となるような整数とします。 ここで、Gauss複素整数の性質を用いて、 π=a+biをpとr-iの公約数、π'=a-biとおきます。 すると、自然数ππ'は、(r-i)p、(r+i)p の約数だから 和2ipの約数、またp²の約数であるため、 結局1またはpのいずれかだということが言えます。 さらに、r²+1はpと素ではないので、 結局ππ'はpとなります。 これは問題の解が存在することを主張しています。 すなわち、