工繊大の塚本です.

In article <884dcc4b-c8c6-4c4c-8011-a0d2a1196064@z10g2000yqb.googlegroups.com>
KyokoYoshida <kyokoyoshida123@gmail.com> writes:
> 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と言えるのでしょうか?

 u, v は u ≡ A  (mod M), v ≡ B  (mod M) であり,
かつ, -M/2 ≦ u, v ≦ M/2 を満たすように取られています.
このとき, u^2 + v^2 ≦ (M/2)^2 + (M/2)^2 = M^2/2 で,
 u^2 + v^2 は M で割り切れますから,
 u^2 + v^2 = M r とすれば,
 1 ≦ r ≦ (M^2/2)/M = M/2 < M です.
 
> それと,
> 「((uA+vB)/M)^2+((vA-uB)/M)^2=rp」
> の箇所でuA+vBとvA-uBがM^2で割り切れる理由はどうしてなのでしょうか?

 u A + v B = (u - A) A + (v - B) B + (A^2 + B^2) であり,
 u - A, v - b, A^2 + B^2 は M で割り切れますから,
 u A + v B は (M^2 ではなく) M で割り切れます.
同様に, v A - u B = (v - B) A - (u - A) B ですから,
 v A - u B は M で割り切れます.
-- 
塚本千秋@数理・自然部門.基盤科学系.京都工芸繊維大学
Tsukamoto, C. : chiaki@kit.ac.jp