ご回答誠にありがとうございます。

>> でもM=1の時に(*)を満たすA,B∈Zが存在せず,
>> a^2+b^2=mp…(**)なるa,b∈Z,(N∋m≦M-1かつ1<m)も存在しない場合にはどうすればいいのでしょうか?
> 文脈からすると、p.178 以降にちゃんとした証明が載っているような気がするけど、
> こんな感じかな？:
> 平方剰余の相互法則(Quadratic Reciprocity)から、
>         p ≡ 1 (mod 4) なら、A^2 ≡ -1 (mod p)
> が成り立つ。すなわち、ある整数 M ≧ 1 が存在して、
>         A^2 + 1^2 = Mp
> (これは、p.176 の "A^2 + B^2 = Mp" の B = 1 の場合を言っている)
> M = 1 のときは、命題そのものなのでそれでおしまい。

これはそうですね。

> M > 1 のとき、
> (*)     a^2 + b^2 = mp, 1 ≦  m < M
> を満たす a, b, m が存在する。それは、次の恒等式から分かる：
>         (Xa + Yb)^2 + (Ya - Xb)^2 = (X^2 + Y^2)(a^2 + b^2)
> これは、
>         Xa + Yb = A, Ya - Xb = 1,  (X^2 + Y^2)(a^2 + b^2) = Mp
> と置いたものに等しい。

あっ。ありがとうございます。この恒等式の利用の仕方がやっと分かりました。

>         X^2 + Y^2 = r, Mp = rmp
> と置けば、1 ≦  m < M である。
>
> p は素数だから、 r か a^2 + b^2 のどちらか(または両方)が p の倍数となる。
> 仮に r が p の倍数でない(あるいは、二つの p の倍数のうちの一方)とすれば、
>           ((Xa + Yb)^2 + (Ya - Xb)^2) / r
>         = a^2 + b^2
>         = mp
> すなわち、(*) が成り立つ。
>
> m > 1 なら上記と同様にすれば
>         a'^2 + b'^b = m'p, 1 ≦  m' < m
> となる m' を見つけることができる。
> また、 a^2 + b^2 は正数だから、上記の繰り返しは m = 1 で停止する。

仰るとおりですね。有難うございます。