ペラン擬素数

$521$ といえばひっくり返して立方数となるような最小の素数という印象が強いかもしれませんが、 $521^2=271441$ が最小のPerrin擬素数であるという性質も記憶に値します。

$p_0=3, \ p_1=0, \ p_2=2, \quad p_n=p_{n-2}+p_{n-3} \ (n \geq 3)$

で定義される数列のことをPerrin数列と呼びます。この数列は次の面白い性質を満たします：

定理 $q$ が素数であれば、 $p_q$ は $q$ の倍数である。

証明. 証明は

で紹介されています。ただし、(※)の部分は次のように考えることもできます： $K$ を $x^3-x-1$ の分解体とし、 $\mathcal{O}_K$ をその整数環とすると、

$p_q \in q\mathcal{O}_K \cap \mathbb{Z} = q\mathbb{Z}$

が言える。 Q.E.D.

$p_1=0$ を例外としても、この定理は逆は成り立ちません。つまり、合成数 $n$ であって、 $p_n$ が $n$ で割り切れるようなものが存在します。そのような $n$ のことをPerrin擬素数と呼び、最小のPerrin擬素数はAdams-Shanksが発見した

$271441=521^2$

です。今となっては次が証明されています：

定理 (Grantham, 2010) Perrin擬素数は無数に存在する。

証明は

で紹介したAlford-Granville-Pomeranceの定理の証明の手法が用いられます。

INTEGERS