Re: Fermatの降下法
工繊大の塚本です.
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
Fnews-brouse 1.9(20180406) -- by Mizuno, MWE <mwe@ccsf.jp>
GnuPG Key ID = ECC8A735
GnuPG Key fingerprint = 9BE6 B9E9 55A5 A499 CD51 946E 9BDC 7870 ECC8 A735