インテジャーズ

インテジャーズ

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

カーマイケルのλ関数と絶対擬素数

Fermatテスト

Fermatテストと呼ばれるお手軽な素数判定法があります。まず、Fermatの小定理を思い出しましょう。

Fermatの小定理 pを素数とする。このとき、pと互いに素な整数aに対して
a^{p-1} \equiv 1 \pmod{p}
が成り立つ。

この定理を使えば、nと互いに素な整数aに対して、a^{n-1}nを法として1と合同でなければnは合成数であると判定することができます。

例えば、2^{6-1}=32 \equiv 2 \not \equiv 1\pmod{6}なので、6は合成数であると判定できます。これが、Fermatテストです。

しかしながら、Fermatテストには欠陥があって、

a^{n-1}nを法として1と合同でなければnは合成数である

は真なのですが、

a^{n-1}nを法として1と合同であればnは素数である

とは必ずしも言えないという点です。実際、WolframAlphaなどで計算してみると分かりますが、合成数341=11 \times 31について

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

が成り立ちます。このような合成数のことを擬素数と呼びます。素数になりすましているというわけですね。擬素数であっても、aとしてはnと互いに素な整数であれば何でもよいので、aを取り替えることによって合成数であることが証明できる場合があります。

実際、

3^{341-1} \equiv 56 \not \equiv 1 \pmod{341}

なので、341は合成数であると判定できます。

Carmichaelの\lambda関数

Fermatの小定理を拡張したのがEulerの定理でした:

Eulerの定理 n2以上の整数とする。このとき、nと互いに素な整数aに対して
\displaystyle a^{\varphi(n)} \equiv 1 \pmod{n}
が成り立つ。\varphi(\cdot)トーシェント関数

そういえば、このブログでは多分これらの定理の証明をしたことはないのですが、Lagrangeの定理から自明です(Q.E.D.)。さて、今回はEulerの定理の精密化であるCarmichaelの定理を紹介します。

定義1 Carmichaelの\lambda関数を次のような数論的関数として定義する:
\lambda(1):=1.
\lambda(2):=1, \lambda(4):=2. 整数e \geq 3に対して、\lambda(2^e):=2^{e-2}.
奇素数pと整数e\geq 1に対して、\lambda(p^e):=p^{e-1}(p-1).
整数n \geq 2に対する\lambda(n)n=p_1^{e_1}\cdots p_k^{e_k}を素因数分解とするときに
\lambda(n):=\mathrm{lcm}(\lambda(p_1^{e_1}), \dots, \lambda(p_k^{e_k}))
によって定義する。

次は、素因数分解して考えれば、定義より明らかです:

基本性質 a, bを正整数とするとき、
\displaystyle a \mid b \Longrightarrow \lambda(a) \mid \lambda(b)
及び
\displaystyle \mathrm{lcm}(\lambda(a), \lambda(b) ) = \lambda(\mathrm{lcm}(a, b) )
が成り立つ。

トーシェント関数の代わりに\lambda関数でも同様の定理が成立するというのがCarmichaelの定理です:

Carmichaelの定理 n2以上の整数とする。このとき、nと違いに素な整数aに対して
\displaystyle a^{\lambda(n)} \equiv 1 \pmod{n}
が成り立つ。

証明. まず、nが素数冪であるときに確認する。n=2, 4のときは自明。n=8のときは、奇数a=2b+1に対して、

a^{\lambda(8)}=a^2=(2b+1)^2=1+4b(b+1) \equiv 1 \pmod{8}.

よって、e \geq 3に対して、aが奇数であれば

\displaystyle a^{\lambda(2^e)}=a^{2^{e-2}}\equiv 1 \pmod{2^e}

が成り立つことはeに関する帰納法で証明できる。pが奇素数である場合は、正整数eに対して \lambda(p^e)=\varphi(p^e)なので、Eulerの定理より a^{\lambda(p^e)}\equiv 1 \pmod{p^e}が成り立つ。

一般のnについては、n=\prod_pp^eと素因数分解される場合、\lambda(p^e) \mid \lambda(n)であることから、nの任意の素因数pに対して

a^{\lambda(n)} \equiv 1 \pmod{p^e}

が成り立つことがわかる(anと互いに素な整数)。よって、a^{\lambda(n)} \equiv 1 \pmod{n}が成立する。 Q.E.D.

定義から明らかに\lambda(n) \mid \varphi(n)なので、Carmichaelの定理はEulerの定理の精密化であることがわかります。しかし、重要なのは単なる精密化ということではなく、optimalな精密化であるということです。

定義2 n2以上の整数とし、anと互いに素な整数とする。このとき、指数 \mathrm{Ind}_a(n)a^e \equiv 1 \pmod{n}が成り立つような最小の正整数eとして定義する。

補題 bcを互いに素な2以上の整数とする。このとき、bcと互いに素な整数aに対して、
\mathrm{Ind}_a(bc)=\mathrm{lcm}(\mathrm{Ind}_a(b), \mathrm{Ind}_a(c) )
が成り立つ。

証明. x=\mathrm{Ind}_a(bc), \ y=\mathrm{lcm}(\mathrm{Ind}_a(b), \mathrm{Ind}_a(c) )とする。a^x \equiv 1 \pmod{bc}からa^x \equiv 1 \pmod{b}が従い、\mathrm{Ind}_a(b) \mid xがわかる*1。同様に、\mathrm{Ind}_a(c) \mid xなので、y \mid xが示された。よって、xの最小性から、後はa^y \equiv 1 \pmod{bc}を示せばよい。これが a^y \equiv 1 \pmod{b}a^y \equiv 1 \pmod{c}から従うことはbcが互いに素であることからわかる。 Q.E.D.

optimalな精密化とは、次の定理が成り立つことです:

定理 n2以上の任意の整数とする。このとき、nと互いに素な整数aが存在して、\lambda(n)=\mathrm{Ind}_a(n)が成り立つ。

証明. n=2^tp_1^{e_1}\cdots p_k^{e_k}nの素因数分解とする(p_iは奇素数)。g_ip_i^{e_i}を法とする原始根とする。原始根の存在は

integers.hatenablog.com

で証明している。このとき、中国式剰余定理によって、nと互いに素な整数aであって

a \equiv 3 \pmod{2^t}, \ a \equiv g_i \pmod{p_i^{e_i}} \ (1 \leq {}^{\forall}i \leq k)

が成り立つようなものが存在する。上記記事の1.2において、5 \mapsto 3としても同じ合同式が成立するので*2

\mathrm{Ind}_a(2^t)=\mathrm{Ind}_3(2^t) = \lambda(2^t)

が成り立つ。また、g_iの取り方から

\displaystyle \mathrm{Ind}_a(p_i^{e_i}) =\mathrm{Ind}_{g_i}(p_i^{e_i})=p_i^{e_i-1}(p_i-1)=\lambda(p_i^{e_i})

が成り立つ。あとは、\lambda関数の定義と補題から\mathrm{Ind}_a(n)=\lambda(n)が従う。 Q.E.D.

正整数nnと互いに素な任意の整数aに対して合同式 a^{n-1} \equiv 1 \pmod{n}を満たすための必要十分条件は\lambda(n)n-1を割り切ることである。

証明. \lambda(n) \mid n-1であれば、Carmichaelの定理より a^{n-1} \equiv 1 \pmod{n}nと互いに素な任意の整数aに対して成立する。次に、nと互いに素な任意の整数aに対して合同式 a^{n-1} \equiv 1 \pmod{n}が成り立つと仮定する。すると、指数の定義より\mathrm{Ind}_a(n) \mid n-1が成り立つ。定理より、\lambda(n) = \mathrm{Ind}_a(n)なるaが存在するので、\lambda(n) \mid n-1が従う。 Q.E.D.

素数pに対しては \lambda(p)=p-1なので、この系はFermatの小定理と両立的であることが確認できます。

Carmichael数

冒頭のFermatテストの解説において、3412に対しては擬素数として振る舞うが 3に対しては合成数と判定されるという現象を見ました。或るaに対して擬素数であるような合成数について、必ず別のa'に対しては合成数と判定されるということが言えればFermatテストは正確な素数判定法となるのですが、事実はそうではありません。どんなaをとってきても擬素数となってしまう、絶対擬素数と呼ばれる合成数達が存在するのです。

定義 合成数nCarmichael数(絶対擬素数とも呼ばれる)であるとは、nと互いに素な任意の整数aに対して合同式 a^{n-1} \equiv 1 \pmod{n}が成り立つときにいう。

まずわかることとして、二つの素数の積であるような絶対擬素数は存在しません。理由: p > qなる二つの素数を考える。このとき、

\displaystyle \frac{pq-1}{p-1} = \frac{(p-1)q+q-1}{p-1}=q+\frac{q-1}{p-1}

は整数ではないため、\lambda(p) \nmid pq-1がわかる。一方、\lambda(pq) \mid pq-1であれば \lambda(p) \mid pq-1でなければならない。\lambda(p^2)=p(p-1) \nmid p^2-1=(p+1)(p-1)も明らか

一方、三つの素数の積であるような合成数を考えると絶対擬素数が出現し始めます。Carmichaelの論文には

561=3\times 11 \times 17, \ 1105=5\times 13 \times 17, \ 2821=7\times 13 \times 31, 15841=7\times 31 \times 73

の4つが書かれています。実際、

\begin{align}\lambda(561) &= \mathrm{lcm}(2, 10, 16)=80 \mid 560 \\ \lambda(1105)&=\mathrm{lcm}(4, 12, 16) = 48 \mid 1104 \\ \lambda(2821)&=\mathrm{lcm}(6, 12, 30) = 60 \mid 2820 \\ \lambda(15841) &= \mathrm{lcm}(6, 30, 72)=360 \mid 15840\end{align}

なので、これらの数は絶対擬素数です。

また、正整数kに対して 6k+1, 12k+1, 18k+1が全て素数であるような場合については、n=(6k+1)(12k+1)(18k+1)は絶対擬素数です。実際、

\lambda(n) = \mathrm{lcm}(6k, 12k, 18k) = 36k \mid (6k+1)(12k+1)(18k+1)-1

となっています。この形の最小の絶対擬素数はk=1の場合の1729=7\times 13 \times 19です。ちなみに、絶対擬素数かつラマヌジャンのタクシー数である1729素数大富豪においてラマヌジャン革命という特殊能力を有しています*3

絶対擬素数は素因数を三つしか持たないというわけではありません。

41041=7\times 11 \times 13 \times 41, \ 825265 = 5\times 7 \times 17\times 19\times 73

などは

\begin{align}\lambda(41041)&=\mathrm{lcm}(6, 10, 12, 40) = 120 \mid 41040 \\ \lambda(825265)&=\mathrm{lcm}(4, 6, 16, 18, 72)=144 \mid 825264\end{align}

なので、絶対擬素数です。

絶対擬素数を小さい順に100個列挙すると次のようになります:


\begin{align}&561, 1105, 1729, 2465, 2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, \\
&62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, \\
&278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461, \\
&530881, 552721, 656601, 658801, 670033, 748657, 825265, 838201, 852841, 997633, \\
&1024651, 1033669, 1050985, 1082809, 1152271, 1193221, 1461241, 1569457, 1615681, \\
&1773289, 1857241, 1909001, 2100901, 2113921, 2433601, 2455921, 2508013, 2531845, \\
&2628073, 2704801, 3057601, 3146221, 3224065, 3581761, 3664585, 3828001, 4335241, \\
&4463641, 4767841, 4903921, 4909177, 5031181, 5049001, 5148001, 5310721, 5444489, \\
&5481451, 5632705, 5968873, 6049681, 6054985, 6189121, 6313681, 6733693, 6840001, \\
&6868261, 7207201, 7519441, 7995169, 8134561, 8341201, 8355841, 8719309, 8719921, \\
&8830801, 8927101, 9439201\end{align}


もし、絶対擬素数が有限個しかなければ、それらをあらかじめ排除しておくことによってFermatテストは正確な素数判定法になれます。が、実は絶対擬素数は無数に存在します。

定理 (Alford-Granville-Pomerance*4 1994) 絶対擬素数は無数に存在する。
W. R. Alford, A. Granville, C. Pomerance, There are Infinitely Many Carmichael Numbers, Annals of Mathematics. 139 (1994), 703–722.

数の世界は実に奥が深いです。


最後にKorseltによる絶対擬素数の判定法を紹介してこの記事を終えます。Korseltはこの定理をCarmichaelより10年以上前に証明していましたが、絶対擬素数の具体例を見つけることはできなかったため、Carmichael数という名前になってしまいました。cf. スティグラーの法則

定理 (Korselt) 合成数nが絶対擬素数となるための必要十分条件は nが無平方かつnの任意の素因数pに対して、p-1n-1を割り切ることである。

証明. この記事では既に系という形で絶対擬素数の判定法を証明しているので、示すべきことは「絶対擬素数は必ず無平方である」ということのみである。nを絶対擬素数とし、n=p^kmという分解を持つと仮定する(pは素数、k2以上の整数、mpと互いに素な整数)。中国式剰余定理によって

\displaystyle a \equiv 1 +p \pmod{p^k},\quad a \equiv 1 \pmod{m}

が成り立つような整数aが存在し、それはnと互いに素である。すると、nが絶対擬素数であるという仮定から a^{n-1} \equiv 1 \pmod{n}が成り立つ。これは

(1+p)^{n-1} \equiv 1 \pmod{p^2}

を導くが、一方で

(1+p)^{n-1} \equiv 1 +(n-1)p \equiv 1-p\pmod{p^2}

なので矛盾が生じる。よって、nは無平方である。 Q.E.D.

この記事内容はブログ仲間tsujimotter氏による記事

tsujimotter.hatenablog.com

とかなりの部分が重複してしまっています。ですが、\lambda関数は今後も扱う予定なので、self-containedを目指す当ブログの性格上、私も記事にすることにしました。

*1:割り算の原理を使って最小性から余りが0となるよくやるやつ。

*2:ただし、e=3については直接確認して、帰納法を9=1+2^3から始める。

*3:みうらさんの記事 togetter.com も参考になります。ちなみに、「1729以外の絶対擬素数を素数として出した場合は、素因数の数だけペナルティとして山札から手札にカードを追加するが、出したカードはそのまま場に残してゲームを続行する」という新ルールを思いついたことをここに報告致します。

*4:GranvilleさんとPomeranceさんは特に尊敬する数学者です。このブログのヘッダーの文章はPomeranceさんのものです。この定理は彼の研究の中でもかなり大きい仕事と言えるでしょう。