>>733 において合同方程式 x^2 ≡ D (mod 4m) の解法が必要であった。 この問題について考える。
m ＞ 1 を有理整数で、m = (p_1)^(k_1)...(p_r)^(k_r) を m の素因数分解とする。
a を有理整数として合同方程式 x^2 ≡ a (mod m) を考える。 この解は、明らかに各 i に対して x^2 ≡ a (mod (p_i)^(k_i)) の 解でもある。
逆に各 i に対して x^2 ≡ a (mod (p_i)^(k_i)) の解を b_i とする。 中国式剰余定理(前スレ１の341)より c ≡ b_i (mod (p_i)^(k_i)) となる c ∈ Z がある。 c^2 ≡ a (mod (p_i)^(k_i)) だから c^2 ≡ a (mod m) である。
以上から x^2 ≡ a (mod m) の解の mod m の個数を N とし、 x^2 ≡ a (mod (p_i)^(k_i)) の解の mod (p_i)^(k_i) の個数を N_i とすると、 N = Π N_i となる(>>100)。
以上から x^2 ≡ a (mod m) は m が素数 p のべき p^n のときに 解ければよい。 この問題は a が p と素なときが本質的であるが、そのときは 環 Z/p^nZ の可逆元のなす群 (Z/p^nZ)^* (>>516) の構造と関係する。 よって、この問題を解く前に (Z/p^nZ)^* の構造について述べる。
