Midnight Floating Thought

これは遠い昔、とある研究集会で発表したことのある話である。 概要ぐらいしか公に残されているものがないと思うので、昔のノートを参照しながら書いてみる。 (ちなみに最近このブログにポツポツ書いている数学系の記事は、だいたい昔のノートを読み返して抜き出したものだったりする。) 定義 まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「$p$ が素数ならば $a^{p-1}\equiv 1modp$」の式「$a^{n-1}\equiv 1modn$」を満たす合成数 $n$ のことである。 正確にはこのとき「$n$ は基 $a$ の擬素数である」という。 以降簡単のためにこれを「$n$ が $\mathrm{psp}(a)$ を満たす」と表現する(psp とは pseudo prime の略である)。 $n$ は奇数で $\mathrm{psp}(a)$ を満たすとしよう。 すると $n-1$ は偶数であり、2 でちょうど $s$ 回割り切れるとすると $n-1=2^s{n}^{\ast }$ と書くことができる。 もちろん $n^{\ast }$ は奇数である。 さて $n-1$ は偶数であるから(条件式の右辺を左辺に移項すると)平方の差の形なのでよく知られているように和と差の積に因数分解できる。 $$a^{n-1}-1=(a^{\frac{n-1}{2}}+1)(a^{\frac{n-1}{2}}-1)$$ この形の因数分解を $s$ 回繰り返す。 $$a^{n-1}-1=(a^{2^{s-1}{n}^{\ast }}+1)(a^{2^{s-2}{n}^{\ast }}+1)\cdots (a^{n^{\ast }}+1)(a^{n^{\ast }}-1)$$ $n$ が素数の場合、積を割り切ればその因子の一つを割り切る、という性質が成り立つので、右辺の因子の一つを割り切る。 一方 $n$ が合成数の場合、そのような保証はないが、たまたま素数と同じように右辺の因子のただ一つを割り切るかもしれない。 そのような擬素数を強擬素数といい、「$n$ が \(\mathrm{s...

オイラー(totient)関数 $\phi (n)$ は $1$ 以上 $n$ 以下の $n$ と互いに素な整数の個数を表す関数である。 言い方を変えると $(\mathbb{Z}/n\mathbb{Z}{)}^{\times }$ の位数を表す関数である。 $n$ 次円分多項式の次数という捉え方もある。 この関数が乗法的関数であることはよく知られている。 すなわち $a$ と $b$ が互いに素なとき $\phi (ab)=\phi (a)\phi (b)$ を満たす。 さて一般に、二つの乗法的関数 $f$, $g$ があったとき、次のように積の和をとったもの $f\cdot g(n)=\sum _{d|n}f(d)g(d)$ も乗法的関数である。 よってたとえばオイラー関数の2乗和 $\sum _{d|n}\phi (d{)}^2$ は乗法的関数である。 こういったオイラー関数の2乗和や、より高次のオイラー関数の冪和について何かよく使われる記号がないものか、と昔から知りたく思っている。 ちなみに単なる因子の冪和については ${\sigma }_k(n)$ という記号がある。 $\sigma (n)={\sigma }_1(n)=\sum _{d|n}d$ を一般化したものである。 その考え方を踏襲すると $\sum _{d|n}\phi (d)=n$ なので、$n_k(n)$ になると考えるといいのかもしれない。 試しに OEIS を引くと、 A029939 Sum phi(d)^2; d|n. は出てくるが、3乗の冪和である数列 1,2,9,10,65 が出てこない。 そのぐらい需要がない。 その需要のないものをどうして気にするか、ということはまた改めて書く。

Wilson の定理とは、素数 $p$ に対し $(p-1)!\equiv -1modp$ が成り立つという初等整数論の定理である。 これが重要な定理ということは特にないと思うのだが、大体の教科書に載っている。 証明にはフェルマーの小定理を使ったり原始根を使ったりすることが多い。 しかし、そんな道具立ては解り易くないと思うのだ。 少し一般的な次のことを証明する (Gauss の一般化と呼ばれているようだ): $n$ を $3$ 以上の整数とするとき、$\prod _{i\in \mathbb{Z}/n{\mathbb{Z}}^{\times }}i\equiv (-1{)}^{k}modn$ が成り立つ。 ただし、$k$ は $1$ の平方根の個数の半分。 (証明) $\mathbb{Z}/n{\mathbb{Z}}^{\times }$ は群なので、各元に逆元が存在する。 自分自身が逆元である元以外は、$a$ と $a^{-1}$ が別々に存在して $a\cdot a^{-1}\equiv 1modn$ だから積に寄与しない。 自分自身が逆元である元とは $a^2\equiv 1modn$ ということなので、$1$ の平方根である。 このような元 $a$ に対し、$-a$ も同様に $(-a{)}^2\equiv a^2\equiv 1modn$ を満たす。 $n$ は $3$ 以上と仮定したので、 $a$ と $-a$ は等しくない。 この二つの元の積を考えると、$a\cdot (-a)\equiv -a^2\equiv -1modn$ である。 $1$ の平方根を $2$ 個ずつ組にしたので、$k$ を $1$ の平方根の個数の半分として $\prod _{i\in \mathbb{Z}/n{\mathbb{Z}}^{\times }}i\equiv (-1{)}^{k}modn$ が成り立つ。 (証明終わり) 元の形の Wilson の定理は、奇素数 $p$ に関しては $n=p$ として上の命題を適用すれば $\mathbb{Z}/p\mathbb{Z}$ が体だから \(a^2 \equiv 1 \bmod...