fixedpoint.jp

2020-01-29

双子の素数の間にある整数は6の倍数

よく知られた事実ですが、3より大きい素数は\(6n-1\)か\(6n+1\)の形をしていることから、標題の命題が導かれます。さらに、順に3つ並んだ奇数\((2n+1, 2n+3, 2n+5)\)が全て素数になるのは、\((3, 5, 7)\)の場合のみであることが分かります。

2020-01-08

素数pを法とする合同式と周期pの周期関数の不動点

フェルマーの小定理は次のような初等整数論の定理です。

定理1

任意の正整数\(a\)と素数\(p\)について\[a^p \equiv a \pmod p.\]

定理1の初等的な証明としては[1]にあるものが代表的です。一方[2]において、\(p\)回ほどこすと元に戻るような置換の不動点を考える"a simple counting technique"と呼ばれる方法による証明が紹介されています。

具体的には、以下のような定理を利用します:

定理2

ある有限集合\(X\)と素数\(p\)が任意に与えられたとする。\(f^p\)が恒等写像となるような関数\(f: X \rightarrow X\)について、\(f\)の不動点の集合を\(X_0\)とすると\[\lvert X \rvert \equiv \lvert X_0 \rvert \pmod p.\]

実際、\(X := \{1, 2, ..., a\}^p\)とし、\(f(n_1, n_2, ..., n_p) := (n_2, ..., n_p, n_1)\)という関数\(f\)に対し定理2を適用でき、定理1が導かれます。さらに[2]ではリュカの定理も定理2を使って証明しています。ここでは別の例として、以下のウィルソンの定理を証明してみます:

定理3

任意の整数\(p (> 1)\)について、\(p\)が素数であるためには次の条件が必要十分である:\[(p-1)! \equiv -1 \pmod p.\]

証明

十分性については対偶を考えると簡単です。必要性を証明するため、\(p\)が素数であると仮定します。\(p = 2\)および\(p = 3\)の場合は明らかなので、\(p > 3\)とします。自然数の3つ組の集合\(V\)を以下のように定義します:\[V := \{(q, a, b) \in \mathbb{N}^3 \mid q < a < b < p \text{ and } a b = p q + 1\}.\]\(V\)の各要素\(v\)について\(v = (q_v, a_v, b_v)\)のように添字\(v\)を付けて各成分を表すことにします。\(p\)が3より大きい素数であることから、\[\prod_{v \in V} a_v b_v = (p-2)!\]であることに注意してください。\(V\)の各要素\(v\)について自然数の集合\(W_v\)を\(W_v := \{1, 2, ..., a_v b_v\}\)と定義します。また関数\(f_v: W_v \rightarrow W_v\)を次のように定義します:\[f_v(k) =\begin{cases}(k + q_v) \bmod p q_v, & \text{if \(k \leq p q_v\)}\\a_v b_v, & \text{if \(k = a_v b_v\)}\end{cases}\]すると、\(f_v\)は\(a_v b_v\)の1点だけを不動点とする周期\(p\)の周期関数です。\(f_v\)らすべての直積を取って\(f: X \rightarrow X\)(ただし\(X := \prod_{v \in V} W_v\))を定義します。すると\(f\)もやはり不動点を1つだけ持つ周期\(p\)の周期関数です。定理2を\(f\)に用いることで、\[\lvert X \rvert = \prod_{v \in V} \lvert W_v \rvert = (p-2)! \equiv 1 \pmod p\]が得られます。従って\((p-1)! \equiv (p-1) \equiv -1 \pmod p\)となります。

このように、素数\(p\)を法とするさまざまな合同式の背後に、該当する個数の不動点を持つ周期\(p\)の周期関数が隠れています。

参考

[1] https://primes.utm.edu/notes/proofs/FermatsLittleTheorem.html

[2] Hausner, M. (1983). Applications of a Simple Counting Technique. The American Mathematical Monthly, 90(2), 127-129. doi:10.2307/2975816

Archives