プーレ数と超プーレ数 - tsujimotterのノートブック

明日話したくなる「数」のお話シリーズの最新動画で超プーレ数という概念を紹介しました。

www.youtube.com

動画内でいくつか定理を紹介しましたが、証明までは説明しませんでした。このブログ記事では動画の補足情報として、動画で紹介できなかった証明部分を紹介したいと思います。

目次：

1. プーレ数、超プーレ数とは

2. 素因数が2個の超プーレ数

3. 素因数が3以上の超プーレ数

4. もっと一般化できるか？

5. プーレ数は無限個あります！！

参考文献

1. プーレ数、超プーレ数とは

まずはじめにプーレ数の定義から紹介しましょう。

定義１（プーレ数）

$a$ を $2$ 以上の整数とし， $m$ を合成数とする． $m$ が

$a^{m} \equiv a \pmod{m} \tag{1}$

を満たすとき， $m$ を底を $a$ とする擬素数（pseudoprime）という．

特に $a = 2$ のとき，底を $2$ とする擬素数のこと，すなわち

$2^{m} \equiv 2 \pmod{m} \tag{2}$

を満たす合成数 $m$ のことをプーレ数（Poulet number）という．

プーレ数をさらに進化させたものが超プーレ数です。プーレ数の定義式 $(2)$ において、 $m$ を「 $m$ のすべての約数 $d$ 」に置き換えて、それがすべての $d$ に対して満たすような数 $m$ を超プーレ数といいます。

つまり定義は次の通りです：

定義２（超プーレ数）

$m$ を合成数とする． $m$ の任意の約数 $d$ が

$2^{d} \equiv 2 \pmod{d} \tag{3}$

を満たすとき， $m$ を超プーレ数（super-Poulet number）という．

当然ですが、 $m$ 自身は $m$ の約数なので、超プーレ数ならばプーレ数です。

具体例として

$341 = 11 \times 31 \tag{4}$

はプーレ数です。これが動画で紹介した数でした。

実際

$2^{341} \equiv 2 \pmod{341} \tag{5}$

が成り立ちます。ちなみに、これを発見したのはサラスという人なのですが、あの $3\times 3$ の行列式の「サラスの方法」を発見したサラスさんと同一人物です。まさかこんなところで出てくるとは。

サラスさんがこの式を発見したのは1819年のことですが、フェルマーの小定理の逆に関する $a = 2$ における最初の反例だったという訳です。

じゃあなんで「サラス数」ではなくて「プーレ数」という名前がついているのかと疑問に思うかと思います。実は、Poulet（プーレ）さんは1926年に $5 \times 10^7$ 以下のすべての擬素数を決定しているのだそうです。1938年には $10^6$ まで擬素数表を拡張したそうで、その意味で彼が研究した数ということでプーレ数と呼ばれるのだと思います。

さらにいえば、 $341$ は超プーレ数でもあります。実際、 $341 = 11 \times 31$ の約数は

$1, \; 11, \; 31, \; 341$

の4つであることが直ちに分かるので

$2^{341} \equiv 2 \pmod{341}$

$2^{31} \equiv 2 \pmod{31}$

$2^{11} \equiv 2 \pmod{11}$

$2^{1} \equiv 2 \pmod{1}$

が成り立つならば $341$ は超プーレ数です。実際、上記の4つの合同式は成り立ちます。

2. 素因数が2個の超プーレ数

実は $341$ のように、２つの相異なる素因数 $p, q$ によって $pq$ と表されるプーレ数は、必ず超プーレ数になることが、次のようにしてわかります。

命題１

$p, q$ を相異なる素数とする．ここで， $pq$ がプーレ数のとき， $pq$ は超プーレ数でもある．

（証明）
$pq$ の約数は $d = 1, \; p, \; q, \; pq$ の4通りである。

ゆえに

$2^{pq} \equiv 2 \pmod{pq}$

$2^{p} \equiv 2 \pmod{p}$

$2^{q} \equiv 2 \pmod{q}$

$2^{1} \equiv 2 \pmod{1}$

が成り立つことが示されれば $pq$ は超プーレ数である。

最初の合同式は $pq$ がプーレ数であることから従う。2, 3番目の合同式は素数 $p, q$ についてのフェルマーの小定理より従う。4番目の合同式は明らか。

（証明おわり）

したがって、 $341$ が超プーレ数であることは明らかだったというわけですね。

3. 素因数が3以上の超プーレ数

以上の考察により

「相異なる3つ以上の素因数からなる超プーレ数があるのか」

ということが気になってきます。

そこで、以下では素因数をたくさん持つような超プーレ数について、その性質を考えていきましょう。

まず、素因数をたくさん持つ超プーレ数は「親玉」のような存在です。

命題２

$m$ を超プーレ数とする．このとき， $m$ の任意の約数で $1$ でも素数でもないものは超プーレ数である．

（証明）
$m$ の任意の $1$ でも素数でもない約数を $d$ とする。 $d$ は従って合成数であるが、この $d$ が超プーレ数であることを示す。

$d$ の任意の約数を $d'$ とすると、 $d' \mid d \mid m$ より、 $d'$ は $m$ の約数。 $m$ は超プーレ数なので

$2^{d'} \equiv 2 \pmod{d'}$

が成り立つ。 $d'$ は任意より $d$ は超プーレ数である。

（証明おわり）

つまり、素因数をたくさん持つ超プーレ数が１つあると、その約数はすべて超プーレ数になるので、たくさんの超プーレ数が得られるというわけです。すなわち、素因数をたくさん持つ超プーレ数は「親玉」のような存在だというわけですね。

さらに面白いことに、共通の素因数を持つ超プーレ数が３つあると、そこから新しい超プーレ数を構成することができます。つまり、命題２と逆方向の話が成り立つというわけです。

具体的には

$2701 = 37\times 73$
$4033 = 37\times 109$
$7957 = 73\times 109$

が超プーレ数なのですが、これらは $37, \; 73, \; 109$ という3つの素数を2つずつ使って得られる数です。

これらが超プーレ数であるという事実から、素因数をすべて1回ずつ使った

$37 \times 73 \times 109 = 294409$

という合成数も超プーレ数であることがわかってしまうのです！

面白いですが、どうしてそんなことが成り立つのでしょうか！？

実はこれを一般化した、次のような定理が成り立つのです：

定理３

$p, q, r$ を相異なる素数とする．このとき， $pq, qr, pr$ がいずれも超プーレ数であるならば， $pqr$ も超プーレ数である．

証明は大変ですが、頑張って証明してみましょう！

（証明）
任意の $d \mid pqr$ に対して

$2^d \equiv 2 \pmod{d}$

が成り立つことを示せば良い。 $pqr$ の任意の約数は $1, p, q, r, pq, qr, pr, pqr$ である。

$d \neq pqr$ のときは、仮定： $pq, qr, pr$ が超プーレ数より示されている。

ゆえに、 $d = pqr$ のとき

$2^{pqr} \equiv 2 \pmod{pqr}$

を示せばよい。

まず、素数 $p$ についてのフェルマーの小定理より

$2^{p} \equiv 2 \pmod{p} \tag{6}$

が成り立つ。

また、 $pq$ が超プーレ数より

$2^{pq} \equiv 2 \pmod{pq}$

が成り立つが、 $\bmod{p}$ とると

$2^{pq} \equiv 2 \pmod{p}$

である。素数 $p$ についてのフェルマーの小定理より

$2^{pq} \equiv (2^p)^q \equiv 2^q \pmod{p}$

であるから

$2^q \equiv 2 \pmod{p} \tag{7}$

が成り立つ。

さらに、 $pr$ が超プーレ数より

$2^{pr} \equiv 2 \pmod{pr}$

が成り立つが、同様に $\bmod{p}$ とると

$2^{pr} \equiv 2 \pmod{p}$

である。素数 $p$ についてのフェルマーの小定理より

$2^{pr} \equiv (2^p)^r \equiv 2^r \pmod{p}$

であるから

$2^r \equiv 2 \pmod{p} \tag{8}$

が成り立つ。

したがって、 $(6), (7), (8)$ より

$2^{pqr} \equiv (2^p)^{qr} \equiv 2^{qr} \equiv (2^q)^r \equiv 2^r \equiv 2 \pmod{p}$

であり

$2^{pqr} \equiv 2 \pmod{p} \tag{9}$

が成り立つ。

同様に

$2^{pqr} \equiv 2 \pmod{q} \tag{10}$

$2^{pqr} \equiv 2 \pmod{r} \tag{11}$

も成り立つ。

したがって、 $(9), (10), (11)$ より

$p \mid 2^{pqr} - 2$ かつ $q \mid 2^{pqr} - 2$ かつ $r \mid 2^{pqr} - 2$

が成り立つので

$pqr \mid 2^{pqr} - 2$

が従う。すなわち

$2^{pqr} \equiv 2 \pmod{pqr}$

が示された。

（証明おわり）

4. もっと一般化できるか？

ところでこういう定理を見ると、さらに多くの素因数を持つ場合も同じことが言えないか気になりますね。実は定理３をさらに一般化した次のような定理も成り立ちます！

定理４（定理３の一般化）

$m$ を $n$ 個の相異なる素数の積で表される合成数とする．

このとき， $m$ の素因数から相異なる2つを任意に選んで $p, q$ としたとき， $pq$ のいずれも超プーレ数であるならば， $m$ も超プーレ数である．

（証明）
$d_0\mid m$ を任意にとったとき

$2^{d_0} \equiv 2 \pmod{d_0} \tag{12}$

が成り立つことを示す。

$d_0 = 1$ のときは明らかに $(12)$ は成り立つので、以下 $d_0 \neq 1$ とする。このとき、 $d_0$ が $s$ 個（ $1 \leq s\leq n$ ）の素因数を持つとして

$d_0 = p_1 \cdots p_s$

と表す。

$d_0$ の任意の約数 $d$ であって $k$ 個（ $1 \leq k \leq s$ ）の素因数の積で表される $d$ が

$2^{d} \equiv 2 \pmod{d_0} \tag{13}$

を満たすことを数学的帰納法により示す。これが示されれば式 $(12)$ が従い証明が完了する。

$(i)$ $d$ が $k = 1$ 個の素因数の積で表せるのとき（素数）：
$d = p_1$ としても一般性は失わないので

$2^{p_1} \equiv 2 \pmod{d_0} \tag{14}$

を示せばよい。

フェルマーの小定理より

$2^{p_1} \equiv 2 \pmod{p_1} \tag{15}$

$p_1 p_i$ （ $2 \leq i \leq s$ ）は超プーレ数なので

$2^{p_1 p_i} \equiv 2 \pmod{p_1 p_i}$

であり、 $\bmod{p_i}$ とると

$2^{p_1 p_i} \equiv 2 \pmod{p_i}$

である。素数 $p_i$ に対するフェルマーの小定理より

$2^{p_1 p_i} \equiv (2^{p_i})^{p_1} \equiv 2^{p_1} \pmod{p_i}$

であり

$2^{p_1} \equiv 2 \pmod{p_i} \tag{16}$

が従う。

$(15), (16)$ より

$2^{p_1} \equiv 2 \pmod{p_1 p_2 \cdots p_s}$

が従う。 $d_0 = p_1 p_2 \cdots p_s$ より、これは示すべき式 $(14)$ である。

$(ii)$ $d$ が $k = 2$ 個以上の素因数を持つとき：
$d$ の約数 $d'$ であって、 $k'$ 個（ $1 \leq k' < k$ ）の素因数の積で表される $d'$ が

$2^{d'} \equiv 2 \pmod{d_0}$

を満たすことを仮定して、 $2^{d} \equiv 2 \pmod{d_0}$ を示す。

$d$ の素因数を1つ選んで $p$ とする。このとき $d = p d_1$ と表せる。ここで帰納法の仮定より $2^{d_1} \equiv 2 \pmod{d_0}$ であるから

$2^{d} \equiv 2^{pd_1} \equiv (2^{d_1})^p \equiv 2^p \pmod{d_0}$

である。また $(i)$ より $2^p \equiv 2 \pmod{d_0}$ でもあるので、 $2^{d} \equiv 2 \pmod{d_0}$ が従う。

$(i), (ii)$ から数学的帰納法より、 $d_0$ の任意の約数 $d$ であって $k$ 個（ $1\leq k\leq s$ ）の素因数の積で表される $d$ が

$2^d \equiv 2 \pmod{d_0}$

を満たすことが示された。特に $2^{d_0} \equiv 2 \pmod{d_0}$ が言えたので、 $m$ が超プーレ数であることが示された。

（証明おわり）

5. プーレ数は無限個あります！！

ところで、プーレ数っていったいどれぐらいの量あるでしょうか？

実は、プーレ数（もっといえば底を $a$ とする擬素数）は無限に多く存在することが証明されています。面白いですね！

証明も面白いのですが、たとえばこんな方法で無限個のプーレ数を得ることができます。

定理５（Cipolla, 1904年）

$a \geq 2$ に対し， $p$ を $a(a^2 - 1)$ を割り切らない素数とする．また，

$\displaystyle n_1 = \frac{a^p - 1}{a - 1}, \;\; n_2 = \frac{a^p + 1}{a + 1}$

とすると， $n = n_1 n_2$ は底を $a$ とする擬素数．

（証明）

$\displaystyle n_1 = \frac{(a - 1)(a^{p-1} + \cdots + a + 1)}{a - 1} = a^{p-1} + \cdots + a + 1$
$\displaystyle n_2 = \frac{(a + 1)(a^{p-1} - a^{p-2} + \cdots - a + 1)}{a + 1} = a^{p-1} - a^{p-2} + \cdots - a + 1$

であるので、どちらも整数で特に奇数である。

また、 $\displaystyle n_1 - 1 = \frac{(a^p - 1) - (a - 1)}{a - 1} = \frac{a^p - a}{a - 1}$ であり、仮定 $p \nmid a$ とフェルマーの小定理より $p \mid a^p - a$ である。加えて仮定 $p \nmid a - 1$ より、 $p \mid n_1 - 1$ である。ゆえに $n_1 \equiv 1 \pmod{2p}$ 。