- 879 名前：Kummer ◆g2BU0D6YN2 [2007/03/10(土) 23:07:15 ]
- a を奇数として合同方程式
x^2 ≡ a (mod 2^n) を考える。
まず x^2 ≡ a (mod 2) は唯一つの解 x ≡ 1 (mod 2) を持つ。
次に x^2 ≡ a (mod 4) を考える。
a が奇数だから x も奇数である。
x = 2k + 1 とすると x^2 = 4k^2 + 4k + 1 だから
x^2 ≡ 1 (mod 4) である。
よって a ≡ 1 (mod 4) である。
よって x^2 ≡ a (mod 4) に解があるためには a ≡ 1 (mod 4) が
必要十分である。
このとき解は x ≡ 1 (mod 4) と x ≡ 3 (mod 4) の２個である。
次に x^2 ≡ a (mod 8) を考える。
a が奇数だから x も奇数である。
x = 4k ± 1 とすると、 x^2 = 16k^2 ± 8k + 1 だから
x^2 ≡ 1 (mod 8) である。
よって x^2 ≡ a (mod 8) に解があるためには a ≡ 1 (mod 8) が
必要十分である。
このとき解は x ≡ 1 (mod 8) と x ≡ 3 (mod 8)
x ≡ 5 (mod 8), x ≡ 7 (mod 8)
の４個である。
|
 |
