インテジャーズ

INTEGERS

数、特に整数に関する記事。

ピライ素数

Pillaiは「n!+1の素因数をnで割った余りは1であると言えるだろうか?」という疑問を持ちました。

\begin{align} 2!+1&=3 \\ 3!+1&=7 \\ 4!+1&= 5^2 \\ 5!+1&= 11^2 \\ 6!+1 &= 7 \times 103 \\ 7!+1 &=  71^2\end{align}

についてはn!+1の任意の素因数pp \equiv 1 \pmod{n}を満たしていることがわかります。ところが、

8!+1 = 61 \times 661

に至って、61 \equiv 661 \equiv 5 \pmod{8}という例が現れます。つまり、Pillaiの疑問は否定的であることがわかりました。そうして、Pillai素数という概念が定義されています:

定義 ある自然数nが存在して、n!+1を割り切り、p \not \equiv 1 \pmod{n}が成り立つような素数pのことをPillai素数という。

61661はPillai素数ですが、最小のPillai素数は23です(Chowlaが指摘)。

14!+1 = 23 \times 3790360487, \quad 18!+1 = 19 \times 23 \times 29 \times 61 \times 67 \times 123610951

で、23 \equiv 9 \pmod{14}, \quad 23 \equiv 5 \pmod{18}となっています。最初の100個のPillai素数は次のようになっています:

\begin{align}&23, 29, 59, 61, 67, 71, 79, 83, 109, 137, 139, 149, 193, 227, 233, 239, 251, 257, 269, \\ &271, 277, 293, 307, 311, 317, 359, 379, 383, 389, 397, 401, 419, 431, 449, 461, 463, \\ &467, 479, 499, 503, 521, 557, 563, 569, 571, 577, 593, 599, 601, 607, 613, 619, 631, \\ &641, 647, 661, 673, 683, 691, 709, 719, 727, 733, 739, 787, 797, 809, 811, 823, 829, \\ &853, 857, 881, 883, 887, 907, 919, 947, 953, 967, 983, 991, 1019, 1021, 1031, 1033, \\ &1061, 1091, 1117, 1129, 1151, 1153, 1187, 1201, 1213, 1217, 1229, 1249, 1289, 1297\end{align}

この記事では次の定理を証明しましょう。

定理 (Erdős, G. E. Hardy-Subbarao) Pillai素数は無数に存在する。

証明. 任意の正整数kに対して、(10k+7)!+1の最大の素因数をp_kとする。このとき、p_kはPillai素数となることを証明する。もし、

p_k \not \equiv 1  \pmod{10k+7}

であればp_kはPillai素数なので、

p_k \equiv 1 \pmod{10k+7}

が成り立つと仮定する。このとき、正の偶数aが存在して

p_k = 1+a(10k+7)

と書ける。(p_k-1)!を分割して考えることにより

(p_k-1)! \equiv (p_k-10k-8)!\times (-1)^{10k+7}(10k+7)! \pmod{p_k}

なので、Wilsonの定理p_kの定義より

(p_k-10k-8)!+1 \equiv 0 \pmod{p_k}

が成り立つ。このとき、

p_k \not \equiv 1 \pmod{p_k-10k-8}

が成り立てばp_kはPillai素数であることがわかる。そこで、

p_k \equiv 1 \pmod{p_k-10k-8}

と仮定しよう。このとき、正の偶数bが存在して

p_k=1+b(p_k-10k-8)

と書ける。p_k = 1+a(10k+7)を代入すると

1+a(10k+7) = 1+b(1+a(10k+7)-10k-8)

よりa=(a-1)b、すなわちa+b=abが得られる。これより、a=b=2となって

p_k=1+2(10k+7) = 20k+15.

これは、p_kが素数であることに矛盾する。

以上でp_kがPillai素数であることが示されたが、明らかにp_k > 10k+7なので、Pillai素数が無数に存在することが従う。 Q.E.D.