インテジャーズ

インテジャーズ

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

ヴィーフェリッヒ数

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

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

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

が成り立ちますが、

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

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

integers.hatenablog.com
integers.hatenablog.com

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

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

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

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

定義 (吾郷-Dilcher-Skula) 奇数mWieferich数であるとは、
2^{\varphi(m)} \equiv 1 \pmod{m^2}
が成り立つときにいう。

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

定理1(吾郷-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を奇素数とし、aa \equiv 1 \pmod{p}を満たすような整数とする。また、Nを非負整数とする。このとき、
\displaystyle \mathrm{ord}_p(a^{p^N}-1)=\mathrm{ord}_p(a-1)+N
が成り立つ。

証明. これは指数持ち上げ補題

integers.hatenablog.com

から従う。 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.

定理1の証明. 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

である。よって、命題よりmPQを素因数として持つときに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-1Q-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

定理2 (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

と評価できる。ここで、 \mathrm{ord}_q(2^{q-1}-1) < \log_q(2^{q-1})より q^{\mathrm{ord}_q(2^{q-1}-1)-1} < 2^{q-1}とざっくりと上から押さえていることに注意。 Q.E.D.


私はWieferich素数は無数に存在すると期待していますので、Wieferich数だって無数に存在すると期待しています。

*1:下の定理における評価はかなり粗いです。