カーマイケル関数

数学の一分野である数論において、正の整数 $n$ のカーマイケル関数 $λ$ $($ $n$ $)$ は、次の式を満たす最小の正の整数 $mである。$

a^{m}\equiv 1{\pmod {n}}

$n$ と互いに素な任意 $の$ 整数に対して成り立つ。代数的に言えば、 $λ$ $($ $n$ $)は$ $n を$ 法とする整数の乗法群の指数である。これは有限アーベル群であるため、指数 $λ$ $($ $n$ $)と$ 等しい位数を持つ元が存在する必要がある。そのような元は $n$ を法とする原始 $λ$ 根と呼ばれる。

カーマイケル $λ$ 関数: $λ$ $($ $n$ $)$ （ $1 \leq$ $n$ $\leq 1000 ）（オイラー$ $φ$ 関数と比較）

カーマイケル関数は、1910年にそれを定義したアメリカの数学者ロバート・カーマイケルにちなんで名付けられました^。[1]カーマイケルのλ関数、縮小トーティエント関数、最小普遍指数関数としても知られています。

$n$ を法とする整数の乗法群の位数は $φ$ $($ $n$ $)$ であり、 $φは$ オイラーのトーシェント関数である。有限群の元の位数は群の位数を割り切るため、 $λ$ $($ $n$ $)は$ $φ$ $($ $n$ $)$ を割り切る。次の表は、 $λ$ $($ $n$ $)$ （OEISのシーケンスA002322）と $φ$ $($ $n$ $)$ の最初の36個の値を比較したものである（異なる場合は太字で示し、異なる $n$ の値は（OEISのシーケンスA033949）に列挙されている）。

$n$	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	31	32	33	34	35	36
$λ (n)$	1	1	2	2	4	2	6	2	6	4	10	2	12	6	4	4	16	6	18	4	6	10	22	2	20	12	18	6	28	4	30	8	10	16	12	6
$φ (n)$	1	1	2	2	4	2	6	4	6	4	10	4	12	6	8	8	16	6	18	8	12	10	22	8	20	12	18	12	28	8	30	16	20	16	24	12

数値例

$n = 5$ 。5 より小さく互いに素な数の集合は ${1, 2, 3, 4$ } である。したがって、オイラーのトーティエント関数の値は $φ$ $(5) = 4$ であり、カーマイケル関数の値は $λ$ $(5)で$ なければならない。除数 1 はを除いて。 2 もなのでしたがって、 $λ$ $(5) = 4 で$ ある。確かに、で。 2 と 3 はどちらも 5 を法とする原始 $λ$ 根であり、また5 を法とする原始根でもある。 $a^{1}\not \equiv 1{\pmod {5}}$ $a\equiv 1{\pmod {5}}$ $2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}$ $1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}$
$n = 8$ 。8 より小さく互いに素な数の集合は ${1,3,5,7}$ である。したがって $φ$ $(8) = 4 で$ あり、 $λ$ $(8)$ は 4 の約数でなければならない。実際、 $λ$ $(8) = 2$ である。8 を法とする原始 $λ$ 根は 3、5、7 である。8 を法とする原始根は存在しない。 $1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}$

再発 $λ (n)$

素数乗のカーマイケル・ラムダ関数は、オイラーのトーティエントを用いて表すことができます。1または素数乗でない任意の数は、異なる素数乗の積として一意に表すことができます。この場合、積の $λ$ は素数乗因数の $λの$ 最小公倍数です。具体的には、 $λ$ $($ $n$ $)$ は次の式で与えられます。

\lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}

素数冪、すなわち $p$ $が素数$ で $r\geq1$ $で$ ある数 $p$ rに対するオイラーのトーティエントは次のように与えられる。

\varphi (p^{r}){=}p^{r-1}(p-1).

カーマイケルの定理

カーマイケルは、 $λ$ $($ $n$ $)が$ 前のセクションの再帰によって定義されていると見なされる場合、導入で述べた特性、つまり、すべてのaに対して $n$ と互いに素であるような最小の正の整数 $mであるという$ $特性$ を満たすことを確立する2つの定理を証明しました。 $a^{m}\equiv 1{\pmod {n}}$

定理1 — $a$ が $n$ と互いに素であれば、. ^[2] $a^{\lambda (n)}\equiv 1{\pmod {n}}$

$これは、 nを$ 法とする整数の乗法群のどの元も $λ$ $($ $n$ $)$ を割り切るということを意味する。カーマイケルは、1(nを法として)に合同な $a$ $の$ 最小のべき乗である元 $a$ を、nを法とする原始λ根と呼ぶ。^{[3] （これは} $n$ を法とする原始根と混同してはならない。カーマイケルはこれを $n$ を法とする原始λ根と呼ぶことがある。） $a^{\lambda (n)}$ $\varphi$

定理2 —任意の正の整数 $nに対して、$ $nを法とする原始$ $λ$ 根が存在する。さらに、 $g が$ そのような根である場合、 $g$ のべき乗に合同な原始 $λ$ 根が存在する。^[4] $\varphi (\lambda (n))$

$g$ が定理によって保証される原始 $λ$ 根の 1 つである場合、には $λ$ $($ $n$ $)$ より小さい正の整数解 $m が$ 存在せず、すべての a に対して $n$ $と$ 互いに素となるような正の $m$ $<$ $λ$ $($ $n$ $)$ は存在しないことがわかります。 $g^{m}\equiv 1{\pmod {n}}$ $a^{m}\equiv 1{\pmod {n}}$

定理 2 の 2 番目のステートメントは、 $nを法とするすべての原始$ $λ$ 根が単一の根 $g$ の累乗に合同であるという意味ではありません。^[5]たとえば、 $n$ $= 15 の$ 場合、およびであるときに $λ$ $($ $n$ $) = 4 になります。 15 を法とする原始$ $λ$ 根は 2、7、8、13 の4 つあります。根 2 と 8 は互いの累乗に合同であり、根 7 と 13 は互いの累乗に合同ですが、 7 も 13 も 2 や 8 の累乗には合同ではなく、その逆も同様です。 15 を法とする乗法群の他の 4 つの要素、つまり 1、4 ( を満たす)、11、14 は、15 を法とする原始 $λ$ 根ではありません。 $\varphi (n)=8$ $\varphi (\lambda (n))=2$ $1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}$ $4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}$

対照的な例として、 $n$ $= 9$ のとき、およびとなります。9を法とする原始 $λ$ 根は2と5の2つあり、それぞれが他方の5乗に合同です。また、どちらも9を法とする原始λ根です。 $\lambda (n)=\varphi (n)=6$ $\varphi (\lambda (n))=2$ $\varphi$

カーマイケル関数の性質

この節では、ある整数が非ゼロ整数で割り切れるとは、となる整数が存在する場合を言う。これは次のように表される。 $n$ $m$ $k$ $n=km$

m\mid n.

最小限の $λ (n)$

$n$ と互いに素なすべての数 $aに対して$ $a$ $m$ $\equiv 1 (mod$ $n$ $)$ と仮定します。すると $λ$ $($ $n$ $) |$ $m$ となります。

証明： $m$ $=$ $kλ$ $($ $n$ $) +$ $r$ （ $0 \leq$ $r$ $<$ $λ$ $($ $n$ $)）$ のとき、

a^{r}=1^{k}\cdot a^{r}\equiv \left(a^{\lambda (n)}\right)^{k}\cdot a^{r}=a^{k\lambda (n)+r}=a^{m}\equiv 1{\pmod {n}}

$n$ と互いに素なすべての数に対して合同 $が$ 成り立つ。r $<$ $λ$ $($ $n$ $)$ であり、 $λ$ $($ $n$ $)$ $は$ $n$ と互いに素なすべての $数$ に対して合同が成り立つ最小の正の指数であるため、 $r$ $= 0$ となる。

$λ (n)$ 分割する $φ (n)$

これは初等群論から導かれる。なぜなら、任意の有限群の指数は必ずその群の位数を割り切れるからである。λ $($ $n$ $)$ $は$ $n を$ 法とする整数の乗法群の指数であり、 $φ$ $($ $n$ $)はその群の位数である。特に、$ 原始根の存在により乗法群が巡回的である場合、すなわち奇数の素数冪の場合、これら2つは必ず等しくなる。

したがって、カーマイケルの定理はオイラーの定理を明確にしたものと見ることができます。

割り切れるかどうか

a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)

証拠。

定義により、（したがっても）を満たす任意の整数に対してが成り立ち、したがってとなります。これにより、 $a$ と互いに素なすべての $k$ に対してが成り立ちます。上で証明された最小性の帰結により、が成り立ちます。 $k$ $\gcd(k,b)=1$ $\gcd(k,a)=1$ $b\,|\,(k^{\lambda (b)}-1)$ $a\,|\,(k^{\lambda (b)}-1)$ $k^{\lambda (b)}\equiv 1{\pmod {a}}$ $\lambda (a)\,|\,\lambda (b)$

構成

すべての正の整数 $a$ と $b$ に対して、

\lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))

。

これはカーマイケル関数の再発の直接的な結果です。

指数関数的サイクル長

$がn$ の素因数分解における最大の指数である場合、すべての $a （$ $n$ と互いに素でないものも含む）とすべての $r$ $\geq$ $r$ $max$ に対して、 $r_{\mathrm {max} }=\max _{i}\{r_{i}\}$ $n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}$

a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.

特に、平方自由 $n$ （ $r$ $max$ $= 1$ ）の場合、すべてのa $に対して、$

a\equiv a^{\lambda (n)+1}{\pmod {n}}.

平均値

$n$ $\geq 16$ の場合: ^[6]^[7]

{\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}

（以下、エルデシュ近似と呼ぶ）定数

B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537

γ $\approx 0.57721$ 、オイラー・マスケロニ定数 $。$

次の表は、最初の $226 - 1 =の概要を示しています。$ $λ$ 関数の値は、正確な平均値とエルデシュ近似値の両方で $67,108,863$ $個$ $あります。$

さらに、よりアクセスしやすい「対数/対数」値の概要も示します $。LoL( n ) := .mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}⁠ln λ ( n )/ln n⁠$ と

$LoL(n) > ⁠ 4 / 5 ⁠ \Leftrightarrow λ (n) > n ⁠ 4 / 5 ⁠$ 。

そこで、表の行番号26の列のエントリ

$% LoL > ⁠ 4 / 5 ⁠$ → 60.49

60.49%（≈40 000 000）の整数 $1 \leq n \leq 67108863$ は $λ$ $($ $n$ $) >$ $n$ $⁠$ $4 / 5 ⁠$ つまり、 $λ$ 入力 $n$ 長さ $l$ $:= log$ $2$ $($ $n$ $)$ 、すなわち

\left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.

$ν$	$n = 2 ν - 1$	和 $\sum _{i\leq n}\lambda (i)$	平均 ${\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)$	エルデシュ平均	エルデシュ / 正確な平均	$LoL$ 平均	% $LoL$ > ⁠4/5⁠	% $LoL$ > ⁠7/8⁠
5	31	270	8.709677	68.643	7.8813	0.678244	41.94	35.48
6	63	964	15.301587	61.414	4.0136	0.699891	38.10	30.16
7	127	3574	28.141732	86.605	3.0774	0.717291	38.58	27.56
8	255	12994	50.956863	138.190	2.7119	0.730331	38.82	23.53
9	511	48032	93.996086	233.149	2.4804	0.740498	40.90	25.05
10	1023	178816	174.795699	406.145	2.3235	0.748482	41.45	26.98
11	2047	662952	323.865169	722.526	2.2309	0.754886	42.84	27.70
12	4095	2490948	608.290110	1304.810	2.1450	0.761027	43.74	28.11
13	8191	9382764	1145.496765	2383.263	2.0806	0.766571	44.33	28.60
14	16383	35504586	2167.160227	4392.129	2.0267	0.771695	46.10	29.52
15	32767	134736824	4111.967040	8153.054	1.9828	0.776437	47.21	29.15
16	65535	513758796	7839.456718	15225.43	1.9422	0.781064	49.13	28.17
17	131071	1964413592	14987.40066	28576.97	1.9067	0.785401	50.43	29.55
18	262143	7529218208	28721.79768	53869.76	1.8756	0.789561	51.17	30.67
19	524287	28935644342	55190.46694	101930.9	1.8469	0.793536	52.62	31.45
20	1048575	111393101150	106232.8409	193507.1	1.8215	0.797351	53.74	31.83
21	2097151	429685077652	204889.9090	368427.6	1.7982	0.801018	54.97	32.18
22	4194303	1660388309120	395867.5158	703289.4	1.7766	0.804543	56.24	33.65
23	8388607	6425917227352	766029.1187	1345633	1.7566	0.807936	57.19	34.32
24	16777215	24906872655990	1484565.386	2580070	1.7379	0.811204	58.49	34.43
25	33554431	96666595865430	2880889.140	4956372	1.7204	0.814351	59.52	35.76
26	67108863	375619048086576	5597160.066	9537863	1.7041	0.817384	60.49	36.73

優勢間隔

$すべての数Nと$ $o$ $($ $N$ $)$ $[$ ^8]以外のすべて $の$ 正の整数 $n\leqN$ （「優勢な」多数派）について：

\lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}

定数^[7]

A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688

下限

十分に大きな数 $N$ と $Δ\geq(ln ln N) 3$ に対して、最大で

N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)

$λ$ $($ $n$ $) \leq$ $ne$ $-Δ$ を満たす正の整数 $n$ $\leq N$ 。^[9]

最小注文

正の整数の任意の列 $n$ $1$ $<$ $n$ $2$ $<$ $n$ $3$ $< \dots$ に対して、任意の定数 $0 <$ $c$ $<$ $⁠$ $1 / 2行目 ⁠$ 、そして十分に大きい $i$ ：^[10]^[11]

\lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.

小さな値

定数 $c$ と十分に大きい正の $A$ に対して、整数 $n$ $>$ $A$ が存在し、^[11]

\lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.

さらに、 $n$ は次の形式をとる。

n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q

ある平方自由整数 $m$ $< (ln$ $A$ $)$ $c$ $ln ln ln$ $A$ に対して。^[10]

機能のイメージ

カーマイケル関数の値の集合は計数関数を持つ^[12]

{\frac {x}{(\ln x)^{\eta +o(1)}}},

どこ

\eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607

暗号での使用

カーマイケル関数は、RSA 暗号化アルゴリズムで使用されるため、暗号化において重要です。

定理1の証明

$n$ $=$ $p$ （素数）の場合、定理1はフェルマーの小定理と同等である。

a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.

素数累乗 $p$ $r$ , $r$ $> 1 の$ 場合、

a^{p^{r-1}(p-1)}=1+hp^{r}

が整数 $h$ に対して成り立つとき、両辺を $p$ 乗すると

a^{p^{r}(p-1)}=1+h'p^{r+1}

他の整数に対してはが成り立つ。帰納法により、すべてのa が $p$ と互いに素で $あり$ 、したがって $p$ $r$ $とも素であることがわかる。これにより、 n$ $= 4$ または任意の奇数の素数乗に対して定理が成立する。 $h'$ $a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}$

2のべき乗の結果をシャープにする

$2の（べき乗$ ）と互いに素な整数 $h$ $2$ に対して $a$ $= 1 + 2$ $h$ $2$ が成り立ちます。すると、

a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}

、

ここでは整数である。r $= 3$ のとき、これは次のように書ける $。$ $h_{3}$

a^{2^{r-2}}=1+2^{r}h_{r}.

両辺を二乗すると

a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},

ここでは整数である。帰納的に次の式が導かれる。 $h_{r+1}$

a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}

はと互いに素である $。$ [ ^13] $r\geq 3$ $2^{r}$

複数の素因数を持つ整数

一意因数分解定理により、任意の $n$ $> 1は$ 次のように一意に表される。

n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}

ここで、 $p$ $1$ $<$ $p$ $2$ $< ... <$ $p$ $k$ は素数であり、 $r$ $1$ $,$ $r$ $2$ $, ...,$ $r$ $k$ は正の整数である。素数のべき乗の結果から、 $1\leq j\leq k$

a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.

このことから、

a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,

ここで、再帰式から分かるように、

\lambda (n)=\operatorname {lcm} {\Bigl (}\lambda \left(p_{1}^{r_{1}}\right),\lambda \left(p_{2}^{r_{2}}\right),\ldots ,\lambda \left(p_{k}^{r_{k}}\right){\Bigr )}.

中国剰余定理から次の結論が得られる。

a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.

参照

カーマイケル数

注記

^ カーマイケル、ロバート・ダニエル (1910). 「新しい数論関数に関するノート」.アメリカ数学会報. 16 (5): 232– 238. doi : 10.1090/S0002-9904-1910-01892-9 .
^ カーマイケル（1914）p.40
^ カーマイケル（1914）p.54
^ カーマイケル（1914）p.55
^ カーマイケル（1914）56ページ
^ エルデシュ（1991）の定理3
^ ab Sándor & Crstici (2004) p.194
^ Erdős (1991) の定理 2 3. 正規順序。 (p.365)
^ Friedlander (2001) の定理5
^ エルデシュの ab 定理 1 (1991)
^ ab Sándor & Crstici (2004) p.193
^ フォード, ケビン; ルカ, フロリアン; ポメランス, カール (2014年8月27日). 「カーマイケルのλ関数の像」.代数と数論. 8 (8): 2009– 2026. arXiv : 1408.6506 . doi :10.2140/ant.2014.8.2009. S2CID 50397623.
^ カーマイケル（1914）pp.38–39

参考文献

ポール・エルデシュ;カール・ポメランス;エリック・シュムッツ (1991)。「カーマイケルのラムダ関数」。アクタ算術。58 (4): 363–385 .土井: 10.4064/aa-58-4-363-385。ISSN 0065-1036。MR 1121092。Zbl 0734.11047 。
フリードランダー, ジョン・B. ; ポメランス, カール; シュパルリンスキー, イゴール・E. (2001). 「発電機の周期とカーマイケル関数の微小値」.計算数学. 70 (236): 1591– 1605, 1803– 1806. doi : 10.1090/s0025-5718-00-01282-5 . ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
サンダー、ジョゼフ。クリスティチ、ボリスラフ (2004)。整数論ハンドブック II．ドルドレヒト: クルーワー学者。 pp . 32–36、193–195。ISBN 978-1-4020-2546-4. Zbl 1079.11001。
カーマイケル、ロバート・D. [1914].プロジェクト・グーテンベルクにおける数論

[1] カーマイケル、ロバート・ダニエル (1910). 「新しい数論関数に関するノート」.アメリカ数学会報. 16 (5): 232– 238. doi : 10.1090/S0002-9904-1910-01892-9 .

[2] カーマイケル（1914）p.40

[3] カーマイケル（1914）p.54

[4] カーマイケル（1914）p.55

[5] カーマイケル（1914）56ページ

[6] エルデシュ（1991）の定理3

[HBII194-7] Sándor & Crstici (2004) p.194

[8] Erdős (1991) の定理 2 3. 正規順序。 (p.365)

[9] Friedlander (2001) の定理5

[Theorem_1_in_Erdős_(1991)-10] エルデシュの ab 定理 1 (1991)

[HBII193-11] Sándor & Crstici (2004) p.193

[12] フォード, ケビン; ルカ, フロリアン; ポメランス, カール (2014年8月27日). 「カーマイケルのλ関数の像」.代数と数論. 8 (8): 2009– 2026. arXiv : 1408.6506 . doi :10.2140/ant.2014.8.2009. S2CID 50397623.

[13] カーマイケル（1914）pp.38–39