- 127 名前：Kummer ◆g2BU0D6YN2 [2006/12/03(日) 13:33:44 ]
- 補題
a を有理整数で a ≡ 1 (mod 8) とする。
n ≧ 3 とし
x^2 ≡ a (mod 2^n) の根の一つを b とする。
このとき b + 2^n または b + 2^(n-1) のどちらか一方は
x^2 ≡ 1 (mod 2^(n+1) の根である。
証明
b^2 = a + (2^n)t とする。
(b + 2^n)^2 = b^2 + 2^(n+1)b + 2^(2n)
= a + (2^n)t + 2^(n+1)b + 2^(2n) ≡ a + (2^n)t (mod 2^(n+1))
よって t が偶数なら
b + 2^n が x^2 ≡ 1 (mod 2^(n+1)) の根である。
次に t が奇数の場合を考える。
n ≧ 3 だから 2n - 2 ≧ n + 1 である。
さらに b は奇数である。
よって
(b + 2^(n-1))^2 = b^2 + (2^n)b + 2^(2n-2)
≡ a + (2^n)t + (2^n) (mod 2^(n+1))
≡ a + (2^n)(t + 1) (mod 2^(n+1))
よって t が奇数なら b + 2^(n-1) が
x^2 ≡ 1 (mod 2^(n+1)) の根である。
証明終
|
 |
