2013年8月24日土曜日

円分擬素数 あるいは なぜオイラー関数の冪和記号が欲しかったのか

これは遠い昔、とある研究集会で発表したことのある話である。 概要ぐらいしか公に残されているものがないと思うので、昔のノートを参照しながら書いてみる。 (ちなみに最近このブログにポツポツ書いている数学系の記事は、だいたい昔のノートを読み返して抜き出したものだったりする。)

定義

まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「\(p\) が素数ならば \(a^{p-1}\equiv 1 \bmod p\)」の式「\(a^{n-1}\equiv 1 \bmod n\)」を満たす合成数 \(n\) のことである。 正確にはこのとき「\(n\) は基 \(a\) の擬素数である」という。 以降簡単のためにこれを「\(n\) が \(\mathrm{psp}(a)\) を満たす」と表現する(psp とは pseudo prime の略である)。

\(n\) は奇数で \(\mathrm{psp}(a)\) を満たすとしよう。 すると \(n-1\) は偶数であり、2 でちょうど \(s\) 回割り切れるとすると \(n - 1 = 2^s n^*\) と書くことができる。 もちろん \(n^*\) は奇数である。 さて \(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^*} + 1)(a^{2^{s-2}n^*} + 1) \cdots (a^{n^*} + 1)(a^{n^*} - 1)\] \(n\) が素数の場合、積を割り切ればその因子の一つを割り切る、という性質が成り立つので、右辺の因子の一つを割り切る。 一方 \(n\) が合成数の場合、そのような保証はないが、たまたま素数と同じように右辺の因子のただ一つを割り切るかもしれない。 そのような擬素数を強擬素数といい、「\(n\) が \(\mathrm{spsp}(a)\) を満たす」と表現する(spsp とは strong pseudo prime の略である)。

以上のことはよく知られた話だが、ここから拡張を試みる。

さて、上では \(n-1\) を \(2\) で何回割り切れるかだけを問題にしたが、実際のところ \(X^m - 1\) という多項式の因数分解は次のようになることが知られている。 \[X^m - 1 = \prod_{d|m} \Phi_d(X)\] ここで \(\Phi_d(X)\) は \(d\) 次の円分多項式、すなわち \(1\) の原始 \(d\) 乗根を、それだけを根に持つ多項式である。 したがって、\(a^{n-1} - 1\) もこの形で因数分解されて、 \[a^{n-1} - 1 = \prod_{d|n-1} \Phi_d(a)\] となる。 先程と同様に、\(n\) が素数ならば \(n\) は右辺の因子の内ただ一つを割り切る。 一方、\(n\) が合成数のときは(たとえ強擬素数であったとしても)そのような保証はない。 が、たまたま素数と同じように \(n\) が右辺の因子の内ただ一つを割り切るかもしれない。 そのような強擬素数を円分擬素数といい、「\(n\) が \(\mathrm{cpsp}(a)\) を満たす」と表現する(cpsp とは cyclotomic pseudo prime の略である)ことにする。

強擬素数と円分擬素数の違いを簡単に述べると、 強擬素数は各素冪因子について基 \(a\) の位数の \(2\) 冪が一致するという条件である一方、 円分擬素数は各素冪因子について基 \(a\) の位数が完全に一致するという条件である。

基の個数

ここからは \(n\) を固定したとき、\(n\) が基 \(a\) の円分擬素数となるような \(a\) は \(n\) を法として何個あるかを計算していく。 そのために \(n\) の素因数分解を \(p_1^{e_1}\cdots p_r^{e_r}\) とする。 もちろん \(p_i\) は素数である。 先程述べたように、円分擬素数の条件は \(a\) の位数が各素冪因子について一致するということだが、その位数が \(n-1\) の約数としても登場しなければならない。 つまり、その位数は次の \(G\) の約数でなければならない。 \[G = \gcd(\{n-1\}\cup\{\varphi(p_i^{e_i}) | i = 1,\ldots,r\})\] ここでオイラー関数 \(\varphi(p_i^{e_i}) = (p_i - 1)p_i^{e_i - 1}\) だが、\(p_i\) は \(n\) の約数だから \(n-1\) とは互いに素である。よって \[G = \gcd(\{n-1\}\cup\{p_i - 1 | i = 1,\ldots,r\})\] と考えれば良い。

\(d\) を \(G\) の約数とすると、\(n\) の各素冪因子 \(p_i^{e_i}\) について位数 \(d\) の元は \((\mathbb{Z}/p_i^{e_i}\mathbb{Z})^{\times}\) に \(\phi(d)\) 個ずつ存在する。 そのうち一つを \(b_i\) と書くことにすると、孫子の剰余定理によって \(x\equiv b_i \bmod p_i^{e_i}\) であるような元 \(x\) が \(\mathbb{Z}/n\mathbb{Z}\) に一つ取れる。 いま \(b_i\) の決め方は任意だったから全ての素冪因子について位数 \(d\) である元はそれらの任意の組み合わせに対し一つずつ取れる。 つまり、全ての素冪因子について位数 \(d\) である元は \(\varphi(d)^r\) 個存在する。 \(G\) の約数全てについて和を取れば円分擬素数の基の個数が求められ、\(\sum_{d|G}\varphi(d)^r\) 個、 オイラー関数の冪和で示唆した記号を使うと \(n_r(G)\) 個である。

強擬素数の場合と比べてみると、強擬素数の基の個数は Monier により \[\left(1+\frac{2^{kr} - 1}{2^r -1}\right)\prod_{i=1}^{r}\gcd(n^*, p_i^*)\] と示されている。 ただし、\(k=v_2(G)\) である。 この2冪の等比数列の和のような部分が \(n_r(2^k)\) に該当しており、円分擬素数とは残りの奇因子の部分に違いが出てきていることが見て取れる。

2013年8月12日月曜日

オイラー関数の冪和

オイラー(totient)関数 \(\varphi(n)\) は \(1\) 以上 \(n\) 以下の \(n\) と互いに素な整数の個数を表す関数である。 言い方を変えると \((\mathbb{Z}/n\mathbb{Z})^\times\) の位数を表す関数である。 \(n\) 次円分多項式の次数という捉え方もある。 この関数が乗法的関数であることはよく知られている。 すなわち \(a\) と \(b\) が互いに素なとき \(\varphi(ab) = \varphi(a)\varphi(b)\) を満たす。

さて一般に、二つの乗法的関数 \(f\), \(g\) があったとき、次のように積の和をとったもの \(f\cdot g (n) = \sum_{d|n}f(d)g(d)\) も乗法的関数である。 よってたとえばオイラー関数の2乗和 \(\sum_{d|n}\varphi(d)^2\) は乗法的関数である。

こういったオイラー関数の2乗和や、より高次のオイラー関数の冪和について何かよく使われる記号がないものか、と昔から知りたく思っている。 ちなみに単なる因子の冪和については \(\sigma_k(n)\) という記号がある。 \(\sigma(n) = \sigma_1(n) = \sum_{d|n}d\) を一般化したものである。 その考え方を踏襲すると \(\sum_{d|n}\varphi(d) = n\) なので、\(n_k(n)\) になると考えるといいのかもしれない。

試しに OEIS を引くと、A029939 Sum phi(d)^2; d|n. は出てくるが、3乗の冪和である数列 1,2,9,10,65 が出てこない。 そのぐらい需要がない。 その需要のないものをどうして気にするか、ということはまた改めて書く。

2013年8月5日月曜日

Wilson の定理

Wilson の定理とは、素数 \(p\) に対し \((p-1)! \equiv -1 \bmod p\) が成り立つという初等整数論の定理である。 これが重要な定理ということは特にないと思うのだが、大体の教科書に載っている。 証明にはフェルマーの小定理を使ったり原始根を使ったりすることが多い。 しかし、そんな道具立ては解り易くないと思うのだ。

少し一般的な次のことを証明する (Gauss の一般化と呼ばれているようだ): \(n\) を \(3\) 以上の整数とするとき、\(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 ただし、\(k\) は \(1\) の平方根の個数の半分。

(証明) \(\mathbb{Z}/n\mathbb{Z}^\times\) は群なので、各元に逆元が存在する。 自分自身が逆元である元以外は、\(a\) と \(a^{-1}\) が別々に存在して \(a\cdot a^{-1} \equiv 1 \bmod n\) だから積に寄与しない。 自分自身が逆元である元とは \(a^2 \equiv 1 \bmod n\) ということなので、\(1\) の平方根である。 このような元 \(a\) に対し、\(-a\) も同様に \((-a)^2 \equiv a^2 \equiv 1 \bmod n\) を満たす。 \(n\) は \(3\) 以上と仮定したので、 \(a\) と \(-a\) は等しくない。 この二つの元の積を考えると、\(a\cdot(-a) \equiv -a^2 \equiv -1 \bmod n\) である。 \(1\) の平方根を \(2\) 個ずつ組にしたので、\(k\) を \(1\) の平方根の個数の半分として \(\prod_{i \in \mathbb{Z}/n\mathbb{Z}^\times} i \equiv (-1)^k \bmod n\) が成り立つ。 (証明終わり)

元の形の Wilson の定理は、奇素数 \(p\) に関しては \(n=p\) として上の命題を適用すれば \(\mathbb{Z}/p\mathbb{Z}\) が体だから \(a^2 \equiv 1 \bmod p\) の解は \(\pm 1\) 以外にないことから従い、\(p=2\) の場合は \(1 \equiv -1 \bmod 2\) なので成り立つことが判る。

さて残りは \(1\) の平方根の個数を確定すれば話が完結するが、これは \(\mathbb{Z}/n\mathbb{Z}^\times\) を巡回群の直積で書いたときの直積因子の個数を \(m\) とおくと、\(2^m\) となる。 したがって、素数以外には \(n = 4, p^e, 2 p^e\) の時だけ右辺が \(-1\) になる。 ちなみにこの右辺の値の数列がA103131としてOEISに登録されている、といった情報がMathWorldに書いてあった。