すいません。
下記を読み返してみてまた疑問がわいてしまいました。
http://www.geocities.jp/narunarunarunaru/study/Number_Theory/Fermat_method_descend3.jpg

「So we can write
u^2+v^2=Mr,
A^2+B^2=Mp
(for some 1≦r<M)」

の箇所でどうしてr<Mと言えるのでしょうか?

それと,

「((uA+vB)/M)^2+((vA-uB)/M)^2=rp」
の箇所でuA+vBとvA-uBがM^2で割り切れる理由はどうしてなのでしょうか?