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

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

定義

まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「\(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)\) に該当しており、円分擬素数とは残りの奇因子の部分に違いが出てきていることが見て取れる。