コンテンツにスキップ

初等整数論/合成数を法とする合同式

出典: フリー教科書『ウィキブックス(Wikibooks)』


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

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

[編集]

を法とする剰余類は 個ある。

ならば である。よってこのとき任意の に対し となる が一意的に定まる。このような剰余類 の形に一意的に書けるから、ちょうど 個存在する。

一方、 の倍数の場合、 となる が存在するかも定かでない。例えば などは解を持たない。 とおくと である。ここで、つぎの3つの場合に分かれる。

1. のとき よりこの合同式はすべての剰余類を解に持つ。

2. のとき つまり であるが より、この合同式は解を持たない。

3. のとき よりただ1つの剰余類 を解に持つ。しかし を法とする合同式である。よって、これはちょうど 個の剰余類 を解に持つ。


次に、合同方程式 が解を持つのはどのような場合か考える。そもそも が解を持たなければならないことは言うまでもない。まず、正の整数 に対して

より

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

定理 2.4.1
[編集]

を合同方程式 の解とする。このとき ならば

となる がちょうど1つ定まる。 ならばそのような は存在しないか、 すべての に対して (*) が成り立つ。

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

定理 2.4.2
[編集]

を合同方程式 の解とする。 を整数とする。 このとき ならば

となる はちょうど1つ定まる。


任意の素数 と正の整数 に対し、合同方程式 の解の個数は 個である。より詳しく、各 に対し、 となる が1個ずつある。


中国の剰余定理

[編集]

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

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

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

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

のどの2つをとっても互いに素であるとき、任意の整数 について、

を満たす を法としてただひとつ存在する。(ここでの「ただひとつ」というのは、互いに合同なものは同じとみなすという意味である。)

証明 1

まず、 のときを証明する。

より、一次不定方程式に関する定理 1.9 より と表せる。このとき、

となる。

とおくと、

となる。(4) より、 とおけば、

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

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

さて、その唯一性であるが、 を任意の解とすれば、 となる。また同様にして となる。したがって合同の定義より、 の公倍数。 より、 の倍数である。したがって

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


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

(i) k = 1 のとき が唯一の解である(除法の原理より唯一性は保証される)。

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

最初の n の式は、帰納法の仮定によって なる がただひとつ存在する。

ゆえに、

を解けば良い。仮定より、 であるから、k = 2 の場合に当てはめて、この方程式を満たす が、 を法としてただひとつ存在する。

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

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

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

とおき、

とおく。仮定より、 なので定理 1.8 から

なる が存在する。

すると、連立合同方程式の解は、 となる。なぜなら任意の について、

となり、他の全ての項は の積なので で割り切れる。

したがって、 となる。よって が解である。

もちろん、各剰余類 に対し、 となる剰余類 はただ一つ存在する。このことから は 1対1 に対応していることがわかる。 特に は各 に対して となることと同値である。

さて、 1より大きい整数 と素因数分解すると、 はどの2つをとっても互いに素である。 ここで、次のことがわかる。

定理 2.4.3
[編集]

と素因数分解すると、任意の整数 について、

を満たす を法としてただひとつ存在する。 さらに、ここで が成り立つ。

証明
前段は中国の剰余定理を に適用したものである。 ならば の素因数であり、そうなると の素因数になってしまい、 となってしまう。

逆に を共に割り切る素数があるとするとそれは のいずれかである。そのようなものを1つ取ると より となる。


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

定理 2.4.4
[編集]

と素因数分解する。 を法とする既約剰余類の個数は である。


ここで現れた

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


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

[編集]

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

定理 2.4.5
[編集]

と互いに素な整数とすると

が成り立つ。

証明 と互いに素な数で 1 から までのもの をとる。 中国の剰余定理から である。

はすべて と互いに素である。さらに、これらを で割ったとき余りはすべて異なっている。 よって、これらは と互いに素な数で 1 から までのものをちょうど1回ずつとる。

したがって、

である。積 と互いに素であるから

が成り立つ。


素数を法とする場合と同様 と互いに素な数とし、 となる最小の正の整数 を法とする の位数と呼ぶ。

位数の法則 から

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