ヴィーフェリッヒ数

$16547533489305$ は知られている最大のWieferich数です。

Fermatの小定理より奇素数 $p$ に対して

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

が成り立ちますが、

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

が成り立つような $p$ のことをWieferich素数というのでした：

1093, 3511：ヴィーフェリッヒ素数 - INTEGERS
1093と3511について - INTEGERS

ところで、Fermatの小定理を一般化したEulerの定理を用いると、任意の奇数 $m$ に対して

$2^{\varphi(m)} \equiv 1 \pmod{m}$

が成り立ちます。ここで、 $\varphi(\cdot)$ はトーシェント関数。

このことから、Wieferich数は次のように定義されます。

定義 (吾郷-Dilcher-Skula) 奇数 $m$ がWieferich数であるとは、

$2^{\varphi(m)} \equiv 1 \pmod{m^2}$

が成り立つときにいう。

知られているWieferich数は以下の104個の整数です。

定理１(吾郷-Dilcher-Skula) 次の $104$ 個の整数は全てWieferich数である。

$\begin{align}&1093, 3279, 3511, 7651, 10533, 14209, 17555, 22953, 31599, 42627, 45643, \\ &52665, 68859, 94797, 99463, 127881, 136929, 157995, 228215, 298389, 410787, \\ &473985, 684645, 895167, 1232361, 2053935, 2685501, 3697083, 3837523, \\ &6161805, 11512569, 18485415, 19187615, 26862661, 34537707, 49887799, \\ &57562845, 80587983, 103613121, 134313305, 149663397, 172688535, \\ &241763949, 249438995, 310839363, 349214593, 402939915, 448990191, \\ &518065605, 648541387, 725291847, 748316985, 1047643779, 1208819745, \\ &1346970573, 1554196815, 1746072965, 1945624161, 2175875541, 2244950955, \\ &3142931337, 3242706935, 3626459235, 4040911719, 4539789709, 5238218895, \\ &5836872483, 6527626623, 6734852865, 9428794011, 9728120805, \\ &10879377705, 12122735157, 13619369127, 15714656685, 17510617449, \\ &20204558595, 22698948545, 28286382033, 29184362415, 32638133115, \\ &40858107381, 47143970055, 52531852347, 60613675785, 68096845635, \\ &84859146099, 87553087245, 122574322143, 141431910165, 157595557041, \\ &204290536905, 254577438297, 262659261735, 367722966429, 424295730495, \\ &612871610715, 787977785205, 1103168899287, 1272887191485, \\ &1838614832145, 3309506697861, 5515844496435, 16547533489305.\end{align}$

もしWieferich素数が $1093, 3511$ のみであれば、Wieferich数はこれら104個で尽くされる。

まず、この定理を証明しましょう。

補題 $p$ を奇素数とし、 $a$ を $a \equiv 1 \pmod{p}$ を満たすような整数とする。また、 $N$ を非負整数とする。このとき、

$\displaystyle \mathrm{ord}_p(a^{p^N}-1)=\mathrm{ord}_p(a-1)+N$

が成り立つ。

証明. これは指数持ち上げ補題指数持ち上げ補題 - INTEGERSから従う。 Q.E.D.

命題奇数 $m$ がWieferich数であるための必要十分条件は $m$ の任意の素因数 $p$ に対して

$\displaystyle \mathrm{ord}_p(m) \leq \mathrm{ord}_p(2^{p-1}-1)-1+\mathrm{ord}_p\left( \prod_{l \mid m}(l-1)\right)$

が成り立つことである。ここで、積は $m$ の素因数 $l$ 全体をわたる。

整数の根基の記号を用いれば

$\displaystyle \varphi(\mathrm{rad}(m)) = \prod_{l \mid m}(l-1)$

と書ける。

証明. $m$ の素因数 $p$ を固定して、

$\displaystyle e:=\mathrm{ord}_p(m), \quad r:=\mathrm{ord}_p (\varphi(\mathrm{rad}(m)))$

とおく。 $\displaystyle a:=2^{p^r\varphi(p^e)}\equiv 1 \pmod{p}$ とする。トーシェント関数の明示公式から、 $p$ と互いに素な或る整数 $k$ が存在して $\varphi(m)=p^r\varphi(p^e)k$ と書ける。すると、

$\displaystyle 2^{\varphi(m)}-1=a^k-1 = (a-1)\sum_{i=0}^{k-1}a^i \equiv k(a-1) \pmod{p}$

が成り立つので、補題より

$\displaystyle \mathrm{ord}_p(2^{\varphi(m)}-1)=\mathrm{ord}_p(a-1) = \mathrm{ord}_p( (2^{p-1})^{p^{r+e-1}}-1)=\mathrm{ord}_p(2^{p-1}-1)+r+e-1$

が得られた。 $m$ がWieferich数であるための必要十分条件は $m$ の任意の素因数 $p$ に対して

$\displaystyle \mathrm{ord}_p(2^{\varphi(m)}-1) \geq 2\mathrm{ord}_p(m)$

が成り立つことなので主張が従う。 Q.E.D.

系 Wieferich数の最大素因数はWieferich素数である。

証明. $m$ をWieferich数、 $p$ をその最大素因数とする。このとき、

$\displaystyle \mathrm{ord}_p(\varphi(\mathrm{rad}(m))) = 0$

なので、命題より

$\displaystyle \mathrm{ord}_p(m) \leq \mathrm{ord}_p(2^{p-1}-1)-1$

が成り立つ。よって、 $\mathrm{ord}_p(2^{p-1}-1) \geq 2$ となって、 $p$ がWieferich素数であることがわかる。 Q.E.D.

定理１の証明. $P=1093, \ Q=3053$ とする。これらがWieferich素数であることは二番目に上げた記事で証明しているが、 $\mathrm{ord}_P(2^{P-1}-1)=\mathrm{ord}_Q(2^{Q-1}-1)=2$ である(コンピュータによる数値計算で確かめられる)。また、

$P-1=2^2\cdot 3\cdot 7 \cdot 13, \quad Q-1=2\cdot 3^3\cdot 5 \cdot 13$

である。以下、Wieferich素数が $1093, 3511$ しか存在しないと仮定する(ただし、与えられた数がWieferich数であることを確認することはこの仮定と無関係であることに注意)。仮定のもとで、系より任意のWieferich数 $m$ に対して

$\displaystyle \mathrm{ord}_P(\varphi(\mathrm{rad}(m)))=\mathrm{ord}_Q(\varphi(\mathrm{rad}(m)))=0$

である。よって、命題より $m$ は $P$ や $Q$ を素因数として持つときに $2$ 以上の指数を取り得ない。つまり、Wieferich数は次の3つのタイプに分類される。

(I) ( $P$ より小さい素因数を持つ整数) $\cdot P$

(II) ( $Q$ より小さい $P$ 以外の素因数を持つ整数) $\cdot Q$

(III) ( $Q$ より小さい $P$ 以外の素因数を持つ整数) $\cdot P\cdot Q$

実際には、(I)型Wieferich数は $3, 7, 13, P$ 、(II)型Wieferich数は $3, 5, 13, Q$ 、(III)型Wieferich数は $3, 5, 7, 13, P, Q$ のみしか素因数を持ち得ない( $P-1$ と $Q-1$ の素因数に注意)。

理由: (I), (II), (III)いずれかの型のWieferich数を $m$ として、 $m$ が上記以外の素因数を持ったと仮定する。その中で最大のものを $p$ とすれば

$\displaystyle \mathrm{ord}_p(\varphi(\mathrm{rad}(m)))=0$

である。当然 $p$ はWieferich素数ではないので、命題の不等式が成立せず $m$ がWieferich数であるという仮定に矛盾する。

以下、命題を利用して全Wieferich数を決定する。

(I)型Wieferich数は

$\begin{align}&P\\ &3\cdot P\\ &3^i\cdot 7\cdot P\\ &3^i\cdot 13 \cdot P\\ &3^j \cdot 7\cdot 13 \cdot P\end{align}$

である( $0\leq i \leq 2, \ 0 \leq j \leq 3$ )。

理由: $a, b, c$ を非負整数として $m=3^a\cdot 7^b\cdot 13^c\cdot P$ とする。このとき、

$\displaystyle \mathrm{ord}_7(\varphi(\mathrm{rad}(m)))=\mathrm{ord}_{13}(\varphi(\mathrm{rad}(m)))=1$

であるから、 $m$ がWieferich数となるのは $b, c \leq 1$ のときに限る。あとは

$\displaystyle \mathrm{ord}_3(\varphi(\mathrm{rad}(m)))=b+c+1$

であることに注意すればわかる。

(II)型Wieferich数は

$\begin{align}&3^j\cdot Q\\ &3^j\cdot 5\cdot Q \\ &3^k\cdot 13\cdot Q \\ &3^k\cdot 5\cdot 13 \cdot Q\end{align}$

である( $0 \leq j \leq 3, \ 0 \leq k \leq 4$ )。

理由: $a, b, c$ を非負整数として $m=3^a\cdot 5^b\cdot 13^c\cdot Q$ とする。このとき、

$\displaystyle \mathrm{ord}_5(\varphi(\mathrm{rad}(m)))=\mathrm{ord}_{13}(\varphi(\mathrm{rad}(m)))=1$

であるから、 $m$ がWieferich数となるのは $b, c \leq 1$ のときに限る。あとは

$\displaystyle \mathrm{ord}_3(\varphi(\mathrm{rad}(m)))=c+3$

であることに注意すればわかる。

(III)型Wieferich数は

$\begin{align}&3^k\cdot P\cdot Q\\ &3^k\cdot 5\cdot P\cdot Q \\ &3^l\cdot 7\cdot P\cdot Q \\ &3^l\cdot 5\cdot 7\cdot P\cdot Q \\ &3^l\cdot 13^n\cdot P\cdot Q\\ &3^l\cdot 5\cdot 13^n \cdot P\cdot Q\\ &3^m\cdot 7\cdot 13^n\cdot P\cdot Q\\ &3^m\cdot 5\cdot 7\cdot 13^n\cdot P \cdot Q\end{align}$

である( $0 \leq k \leq 4, \ 0 \leq l \leq 5, \ 0 \leq m \leq 6, \ 1 \leq n \leq 2$ )。

理由: $a, b, c, d$ を非負整数として $m=3^a\cdot 5^b\cdot 7^c \cdot 13^d\cdot P\cdot Q$ とする。

$(P-1)(Q-1) = 2^3\cdot 3^4\cdot 5\cdot 7\cdot 13^2$

に注意する。このとき、

$\displaystyle \mathrm{ord}_5(\varphi(\mathrm{rad}(m)))=\mathrm{ord}_{7}(\varphi(\mathrm{rad}(m)))=1, \ \mathrm{ord}_{13}(\varphi(\mathrm{rad}(m)))=2$

であるから、 $m$ がWieferich数となるのは $b, c \leq 1, \ d \leq 2$ のときに限る。あとは

$\displaystyle \mathrm{ord}_3(\varphi(\mathrm{rad}(m)))=\begin{cases}c+4 & (d=0) \\ c+5 & (d=1, 2)\end{cases}$

であることに注意すればわかる。

以上で、仮定のもとで、Wieferich数は (I)型Wieferich数12個、(II)型Wieferich数18個、(III)型Wienerisch数74個の計104個で尽くされることが示された。これら104個の数が定理の主張に書いた104個の数であることは掛け算すればわかる。 Q.E.D.

Wieferich素数が新たに発見されたとしても、有限個のWieferich素数からは有限個のWieferich数しか生じません*1。

定理２ (Banks-Luca) Wieferich素数全体のなす集合を $\mathrm{WP}$ , Wieferich数全体のなす集合を $\mathrm{WN}$ とし、 $\#\mathrm{WP} < \infty$ と仮定する。このとき、 $\#\mathrm{WN} < \infty$ であり、

$\displaystyle P:=\max_{q \in \mathrm{WP}}q, \quad W:=\max_{w \in \mathrm{WN}}w$

とすると、

$\displaystyle W < 2^{(P-1)\cdot \#\mathrm{WP}}\prod_{l \leq P}(l-1)$

が成り立つ(積は $P$ 以下の素数をわたる)。

証明. $w \in \mathrm{WN}$ を任意に取る。系より $w$ の素因数は $P$ 以下である。 $\displaystyle M:=\prod_{l \leq P}(l-1)$ とおく。命題より $w$ の任意の素因数 $p$ に対して

$\displaystyle \mathrm{ord}_p(w) \leq \mathrm{ord}_p(2^{p-1}-1)-1+\mathrm{ord}_p(M)$

であることから、

$\displaystyle w < \prod_{q \in \mathrm{WP}}2^{q-1}q^{\mathrm{ord}_q(M)}\times \prod_{\substack{p \leq P \\ p \not \in \mathrm{WP}}}p^{\mathrm{ord}_p(M)}=\prod_{q \in \mathrm{WP}}2^{q-1}\prod_{p \leq P}p^{\mathrm{ord}_p(M)} < 2^{(P-1)\cdot \#\mathrm{WP}}M$