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

整数整数-561 整数-1105 整数-1729

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の定理 $n$ を $2$ 以上の整数とする。このとき、 $n$ と互いに素な整数 $a$ に対して

$\displaystyle a^{\varphi(n)} \equiv 1 \pmod{n}$

が成り立つ。 $\varphi(\cdot)$ はトーシェント関数。

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

定義１ 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の定理 $n$ を $2$ 以上の整数とする。このとき、 $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}$

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

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

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

補題 $b$ と $c$ を互いに素な $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}$ から従うことは $b$ と $c$ が互いに素であることからわかる。 Q.E.D.

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

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

証明. $n=2^tp_1^{e_1}\cdots p_k^{e_k}$ を $n$ の素因数分解とする( $p_i$ は奇素数)。 $g_i$ を $p_i^{e_i}$ を法とする原始根とする。原始根の存在は(Z/nZ)*の群構造 - INTEGERSで証明している。このとき、中国式剰余定理によって、 $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.

系正整数 $n$ が $n$ と互いに素な任意の整数 $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テストの解説において、 $341$ は $2$ に対しては擬素数として振る舞うが $3$ に対しては合成数と判定されるという現象を見ました。或る $a$ に対して擬素数であるような合成数について、必ず別の $a'$ に対しては合成数と判定されるということが言えればFermatテストは正確な素数判定法となるのですが、事実はそうではありません。どんな $a$ をとってきても擬素数となってしまう、絶対擬素数と呼ばれる合成数達が存在するのです。

定義合成数 $n$ がCarmichael数(絶対擬素数とも呼ばれる)であるとは、 $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$

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

$\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-1$ が $n-1$ を割り切ることである。

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

$\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さんのものです(注: 昔のヘッダー)。この定理は彼の研究の中でもかなり大きい仕事と言えるでしょう。

Fermatテスト

Carmichaelの関数

Carmichael数

Carmichaelの $\lambda$ 関数