「初等整数論/合成数を法とする合同式」の版間の差分

2022年7月7日 (木) 00:06時点における最新版

初等整数論/フェルマーの小定理で、フェルマーの小定理を用いて、素数を法とする剰余類の構造を調べたので、次に、一般の自然数を法とする合同式について考えたい。まず、素数の冪を法とする場合について考え、次に一般の法について考える。

$p^{e}$ を法とする合同式について

$p^{e}$ を法とする剰余類は $0, 1, \dots, p^{e} - 1$ の $p^{e}$ 個ある。

$\gcd (a, p) = 1$ ならば $\gcd (a, p^{e}) = 1$ である。よってこのとき任意の $b (\mod p^{e})$ に対し $a x \equiv b (\mod p^{e})$ となる $x (\mod p^{e})$ が一意的に定まる。このような剰余類 $a (\mod p^{e})$ は $b p + r, 0 \leq b \leq p^{e - 1} - 1, 1 \leq r \leq p - 1$ の形に一意的に書けるから、ちょうど $p^{e - 1} (p - 1)$ 個存在する。

一方、 $a$ が $p$ の倍数の場合、 $a x \equiv b (\mod p^{e})$ となる $x (\mod p^{e})$ が存在するかも定かでない。例えば $2 x \equiv 3 (\mod 4), 9 x \equiv 3 (\mod 27)$ などは解を持たない。 $a = s p^{f}, b = t p^{g}, \gcd (s, p) = \gcd (t, p) = 1$ とおくと $a x \equiv b (\mod p^{e}) ⟺ s p^{f} x \equiv t p^{g} (\mod p^{e})$ である。ここで、つぎの3つの場合に分かれる。

1. $g \geq e$ のとき $b \equiv 0 (\mod p^{e})$ よりこの合同式はすべての剰余類を解に持つ。

2. $e, f > g$ のとき $s p^{f - g} x \equiv t (\mod p^{e - g})$ つまり $s p^{f - g} x - t \equiv 0 (\mod p^{e})$ であるが $f > g, \gcd (t, p) = 1$ より、この合同式は解を持たない。

3. $f \leq g < e$ のとき $s x \equiv t p^{g - f} (\mod p^{e - f})$ は $\gcd (s, p) = 1$ よりただ1つの剰余類 $x = x_{0} (\mod p^{e - f})$ を解に持つ。しかし $a x \equiv b (\mod p^{e})$ は $p^{e}$ を法とする合同式である。よって、これはちょうど $p^{f}$ 個の剰余類 $x_{0} + k p^{e - f} (\mod p^{e}) (k = 0, 1, \dots, p^{g} - 1)$ を解に持つ。

次に、合同方程式 $f (x) \equiv 0 (\mod p^{e})$ が解を持つのはどのような場合か考える。そもそも $f (x) \equiv 0 (\mod p)$ が解を持たなければならないことは言うまでもない。まず、正の整数 $k, m$ に対して

(x + p^{m})^{k} = x^{k} + k x^{k - 1} p^{m} + (\binom{k}{2}) x^{k - 2} p^{2 m} + \dots \equiv x^{k} + k x^{k - 1} p^{m} (\mod p^{m + 1})

より

f (x + p^{m}) \equiv \sum_{k = 0}^{n} a_{k} (x^{k} + k x^{k - 1} p^{m}) = f (x) + p^{m} f^{'} (x) (\mod p^{m + 1})

が成り立つことから、次のことがわかる。

定理 2.4.1

$x = a$ を合同方程式 $f (x) \equiv 0 (\mod p^{m})$ の解とする。このとき $f^{'} (a) \equiv̸ 0 (\mod p)$ ならば

f (a + b p^{m}) \equiv 0 (\mod p^{m + 1}) \dots (*)

となる $a (\mod p)$ がちょうど1つ定まる。 $f^{'} (a) \equiv 0 (\mod p)$ ならばそのような $b (\mod p)$ は存在しないか、すべての $b (\mod p)$ に対して (*) が成り立つ。

数学的帰納法より、次の定理がすぐに導かれる。

定理 2.4.2

$x = a$ を合同方程式 $f (x) \equiv 0 (\mod p)$ の解とする。 $e \geq 2$ を整数とする。このとき $f^{'} (a) \equiv̸ 0 (\mod p)$ ならば

f (a + b p) \equiv 0 (\mod p^{e})

となる $b (\mod p^{e - 1})$ はちょうど1つ定まる。

例任意の素数 $p$ と正の整数 $e$ に対し、合同方程式 $x^{p - 1} \equiv 1 (\mod p^{e})$ の解の個数は $p - 1$ 個である。より詳しく、各 $a = 1, 2, \dots, p - 1$ に対し、 $x^{p - 1} \equiv 1 (\mod p^{e}), x \equiv a (\mod p)$ となる $x (\mod p^{e})$ が1個ずつある。

中国の剰余定理

一般の合成数を法とする場合は素数冪を法とする場合に帰着される。具体的に、次のような問題を考えてみる。

問 7 で割って 6 余り、13 で割って 12 余り、19 で割って 18 余る数はいくつか?

答えは、7×13×19 - 1 である。さて、このような問題に関して、次の定理がある。

定理 (w:中国の剰余定理)

$m_{1}, m_{2}, \dots, m_{k}$ のどの2つをとっても互いに素であるとき、任意の整数 $a_{1}, a_{2}, \dots, a_{k}$ について、

{\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{k} (\mod m_{k}) \end{matrix}

を満たす $x$ は $m_{1} m_{2} m_{3} \dots m_{k}$ を法としてただひとつ存在する。（ここでの「ただひとつ」というのは、互いに合同なものは同じとみなすという意味である。）

証明 1

まず、 $k = 2$ のときを証明する。

${\begin{matrix} x \equiv a_{1} (\mod m_{1}) \dots (1) \\ x \equiv a_{2} (\mod m_{2}) \dots (2) \end{matrix}$

$(m_{1}, m_{2}) = 1$ より、一次不定方程式に関する定理 1.9 より $m_{1} u + m_{2} v = 1$ と表せる。このとき、

${\begin{matrix} m_{2} v \equiv 1 (\mod m_{1}) \dots (3) \\ m_{1} u \equiv 1 (\mod m_{2}) \dots (4) \end{matrix}$

となる。

$x \equiv a_{1} m_{2} v + a_{2} m_{1} u (\mod m_{1} m_{2})$ とおくと、

$x - a_{1} = a_{1} (m_{2} v - 1) + a_{2} m_{1} u$ となる。(4) より、 $m_{2} v - 1 = m_{1} M$ とおけば、

$x - a_{1} = a_{1} m_{1} M + a_{2} m_{1} v$ は $m_{1}$ で割り切れる。したがって、合同の定義より方程式の (1) を満たす。また、同様に (3) を用いることで、(2) をも満たすことは容易に証明される。

よって、解が存在することが証明された。

さて、その唯一性であるが、 $y$ を任意の解とすれば、 $x, y \equiv a_{1} \Rightarrow x \equiv y \Rightarrow x - y \equiv 0 (\mod m_{1})$ となる。また同様にして $x - y \equiv 0 (\mod m_{2})$ となる。したがって合同の定義より、 $x - y$ は $m_{1}, m_{2}$ の公倍数。 $(m_{1}, m_{2}) = 1$ より、 $x - y$ は $m_{1} m_{2}$ の倍数である。したがって $x - y \equiv 0 \Rightarrow x \equiv y (\mod m_{1} m_{2})$

となり、唯一性が保証された。

次に、定理を k に関する数学的帰納法で証明する。

(i) k = 1 のとき $x \equiv a_{1} (\mod m_{1})$ は $x = a_{1}$ が唯一の解である（除法の原理より唯一性は保証される）。

(ii) k = n のとき成り立つと仮定する

${\begin{matrix} x \equiv a_{1} (\mod m_{1}) \\ x \equiv a_{2} (\mod m_{2}) \\ \dots \\ x \equiv a_{n} (\mod m_{n}) \\ x \equiv a_{n + 1} (\mod m_{n + 1}) \end{matrix}$

最初の n の式は、帰納法の仮定によって $x \equiv b (\mod m_{1} m_{2} \dots m_{n})$ なる $b$ がただひとつ存在する。

ゆえに、

${\begin{matrix} x \equiv b (\mod m_{1} m_{2} \dots m_{n}) \\ x \equiv a_{n + 1} (\mod m_{n + 1}) \end{matrix}$

を解けば良い。仮定より、 $(m_{1} m_{2} \dots m_{n}, m_{n + 1}) = 1$ であるから、k = 2 の場合に当てはめて、この方程式を満たす $x$ が、 $m_{1} m_{2} \dots m_{n} m_{n + 1}$ を法としてただひとつ存在する。

したがって、k = n のとき成り立つならば k = n+1 のときも成り立つことが証明された。

(i)(ii) より数学的帰納法から定理が証明される。

証明 2 この証明はガウスによる。

$M = m_{1} m_{2} \dots m_{n}$ とおき、

$M = m_{1} M_{1} = m_{2} M_{2} = \dots = m_{n} M_{n}$

とおく。仮定より、 $(M_{k}, m_{k}) = 1 (k = 1, 2, \dots, n)$ なので定理 1.8 から

$M_{k} t_{k} \equiv 1 (\mod m_{k})$ なる $t_{k}$ が存在する。

すると、連立合同方程式の解は、 $x \equiv a_{1} M_{1} t_{1} + a_{2} M_{2} t_{2} + \dots + a_{n} M_{n} t_{n} (\mod M)$ となる。なぜなら任意の $1 ≦ k ≦ n$ について、

$M_{k} t_{k} \equiv 1 \Rightarrow a_{k} M_{k} t_{k} \equiv a_{k} (\mod m_{k})$ となり、他の全ての項は $M_{1}, M_{2}, \dots, M_{k - 1}, M_{k + 1}, \dots, M_{n}$ の積なので $m_{k}$ で割り切れる。

したがって、 $x \equiv a_{k} (\mod x_{k})$ となる。よって $x$ が解である。

もちろん、各剰余類 $x (\mod m_{1} m_{2} \dots m_{k})$ に対し、 $x \equiv x_{i} (\mod m_{i})$ となる剰余類 $x_{i} (\mod m_{i})$ はただ一つ存在する。このことから $x (\mod m_{1} m_{2} \dots m_{k})$ と $(x_{1} (\mod m_{1}), x_{2} (\mod m_{2}), \dots, x_{k} (\mod m_{k}))$ は 1対1 に対応していることがわかる。特に $a \equiv 1 (\mod m_{1} m_{2} \dots m_{k})$ は各 $i$ に対して $a \equiv 1 (\mod m_{i})$ となることと同値である。

さて、 1より大きい整数 $n$ を $n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ と素因数分解すると、 $p_{i}^{e_{i}}$ はどの2つをとっても互いに素である。ここで、次のことがわかる。

定理 2.4.3

$n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ と素因数分解すると、任意の整数 $a_{1}, a_{2}, \dots, a_{k}$ について、

{\begin{matrix} a \equiv a_{1} (\mod p_{1}^{e_{1}}) \\ a \equiv a_{2} (\mod p_{2}^{e_{2}}) \\ \dots \\ a \equiv a_{k} (\mod p_{k}^{e_{k}}) \end{matrix}

を満たす $a$ は $n$ を法としてただひとつ存在する。さらに、ここで $\gcd (a, n) = 1 ⟺ \gcd (a_{i}, p_{i}^{e_{i}}) = 1 (i = 1, 2, \dots, k)$ が成り立つ。

証明
前段は中国の剰余定理を $m_{i} = p_{i}^{e_{i}}$ に適用したものである。 $\gcd (a_{i}, p_{i}^{e_{i}}) > 1$ ならば $p_{i}$ は $a_{i}$ の素因数であり、そうなると $p_{i}$ は $a$ の素因数になってしまい、 $p | \gcd (a, n)$ となってしまう。

逆に $a, n$ を共に割り切る素数があるとするとそれは $p_{i}$ のいずれかである。そのようなものを1つ取ると $a_{i} \equiv a \equiv 0 (\mod p_{i})$ より $\gcd (a_{i}, p_{i}^{e_{i}}) > 1$ となる。

この定理から、次のことがすぐにわかる。

定理 2.4.4

$n = p_{1}^{e_{1}} p_{2}^{e_{2}} \dots p_{k}^{e_{k}}$ と素因数分解する。 $n$ を法とする既約剰余類の個数は $\prod_{i = 1}^{k} p_{i}^{e_{i} - 1} (p_{i} - 1)$ である。

ここで現れた

φ (n) = \prod_{i = 1}^{k} p_{i}^{e_{i} - 1} (p_{i} - 1)

を $n$ の オイラー関数 (Euler's totient) という。これは円分多項式の次数として現れたものである。

フェルマー・オイラーの定理

中国の剰余定理から、フェルマーの小定理は次のように一般化される。

定理 2.4.5

$a$ を $n$ と互いに素な整数とすると

a^{φ (n)} \equiv 1 (\mod n)

が成り立つ。

証明 $n$ と互いに素な数で 1 から $n - 1$ までのもの $b_{1}, \dots, b_{k}$ をとる。中国の剰余定理から $k = φ (n)$ である。

$a b_{i} (i = 1, \dots, k)$ はすべて $n$ と互いに素である。さらに、これらを $p$ で割ったとき余りはすべて異なっている。よって、これらは $n$ と互いに素な数で 1 から $n - 1$ までのものをちょうど1回ずつとる。

したがって、

b_{1} b_{2} \dots b_{k} \equiv (a b_{1}) (a b_{2}) \dots (a b_{k}) = a^{k} (b_{1} b_{2} \dots b_{k}) (\mod n)

である。積 $b_{1} b_{2} \dots b_{k}$ も $n$ と互いに素であるから

a^{k} \equiv 1 (\mod n)

が成り立つ。

素数を法とする場合と同様 $a$ を $n$ と互いに素な数とし、 $a^{l} \equiv 1 (\mod n)$ となる最小の正の整数 $l$ を $n$ を法とする $a$ の位数と呼ぶ。

位数の法則から

a^{m} \equiv 1 (\mod n) ⟺ l | m

が成り立つ。これと、フェルマー・オイラーの定理から位数は $φ (n)$ の約数であることがわかる（この $φ (n)$ は、多くの場合、より小さな値をとる関数で置き換えられることを合成数を法とする剰余類の構造で見る）。

テンプレート:Nav

「初等整数論/合成数を法とする合同式」の版間の差分

2022年7月7日 (木) 00:06時点における最新版

目次

$p^{e}$ を法とする合同式について

定理 2.4.1

定理 2.4.2

中国の剰余定理

定理 2.4.3

定理 2.4.4

フェルマー・オイラーの定理

定理 2.4.5

ナビゲーションメニュー

「初等整数論/合成数を法とする合同式」の版間の差分

2022年7月7日 (木) 00:06時点における最新版

pe を法とする合同式について

定理 2.4.1

定理 2.4.2

中国の剰余定理

定理 2.4.3

定理 2.4.4

フェルマー・オイラーの定理

定理 2.4.5

ナビゲーション メニュー

検索

$p^{e}$ を法とする合同式について

ナビゲーションメニュー