- 933 名前：Kummer ◆g2BU0D6YN2 [2007/03/12(月) 23:25:52 ]
- 後の参照のため >>889 で述べたことの一部をもっと詳しく述べる。
命題
m ＞ 1 と a を有理整数で gcd(a, m) = 1 とする。
m = (2^e)r、r は奇数。
r の相異なる素因数の個数を s とする。
x^2 ≡ a (mod m) に解があるためには
(1) e = 0 または e = 1 のときは r の各素因数 p に対して
(a/p) = 1 が必要十分である。
この条件が満たされるとき解の個数は 2^s である。
(2) e = 2 のときは r の各素因数 p に対して
(a/p) = 1 であり、さらに a ≡ 1 (mod 4) が必要十分である。
この条件が満たされるとき解の個数は 2^(s+1) である。
(3) e ≧ 3 のときは r の各素因数 p に対して
(a/p) = 1 であり、さらに a ≡ 1 (mod 8) が必要十分である。
この条件が満たされるとき解の個数は 2^(s+2) である。
証明
(1) は >>866 と >>889 より直ちに出る。
(2) は >>866 と >>879 と >>889 より直ちに出る。
(3) は >>866 と >>881, >>882 と >>889 より直ちに出る。
|
 |
