これは遠い昔、とある研究集会で発表したことのある話である。 概要ぐらいしか公に残されているものがないと思うので、昔のノートを参照しながら書いてみる。 (ちなみに最近このブログにポツポツ書いている数学系の記事は、だいたい昔のノートを読み返して抜き出したものだったりする。) 定義 まずは前段階として、擬素数について思い出しておく。 広義に擬素数とは素数ならば必ず満たす条件を満たしている必ずしも素数でない整数、ということだが、単に擬素数とだけ言えばフェルマーの小定理 「\(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{s...