カーマイケル関数

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

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

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

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

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

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

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

${\displaystyle \lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odds 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 different primes power.}}\end{cases}}}$

素数累乗、すなわちpが素数でr≥1である数p ^rに対するオイラーのトーティエントは次のように与えられる。

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

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

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

g が定理によって保証される原始λ根の 1 つである場合、 λ ( n )より小さい正の整数解m は存在せず、すべてのaに対してnと互いに素となるような正のm < λ ( n )は存在しないことを示しています。 ${\displaystyle g^{m}\equiv 1{\pmod {n}}}$ ${\displaystyle 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 を法とする原始λ根ではありません。 ${\displaystyle \varphi (n)=8}$${\displaystyle \varphi (\lambda (n))=2}$${\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}}$${\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}}$

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

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

${\displaystyle m\mid n.}$

nと互いに素なすべての数aに対してa ^m ≡ 1 (mod n )とすると、 λ ( n ) | mと なります。

証明: m = kλ ( n ) + r（0 ≤ r < λ ( n ) ）の場合、

${\displaystyle 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 )はその群の位数である。特に、原始根の存在により乗法群が巡回している場合、この 2 つは等しくなければならない。これは奇数の素数累乗の場合である。

したがって、カーマイケルの定理はオイラーの定理の強化版として見ることができます。

${\displaystyle a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)}$

証拠。

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

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

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

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

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

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

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

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

n ≥ 16の場合: ^{[6] [7]}

${\displaystyle {\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)}}$

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

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

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

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

さらに、より簡単にアクセスできる「対数/対数」値 の概要も示します。LoL ( n ) := ⁠lnλ ( n )の/lnn行⁠と

• LoL( n ) > ⁠4/5⁠ ─ λ ( n ) > n ^⁠4/5⁠ .

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

•  % 爆笑 > ⁠4/5⁠   → 60.49

60.49%（≈40 000 000）の整数1 ≤ n ≤67 108 863はλ ( n ) > n ^{⁠ 4/5⁠}つまり、λ入力nの長さl  := log ₂ ( n )あり、

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

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

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

定数^[7]

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

十分に大きな数NとΔ ≥ (ln ln N ) ³に対して、最大で

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

λ ( n ) ≤ne ^−Δを満たす正の整数n≤N。^[9]

任意の正の整数のシーケンスn ₁ < n ₂ < n ₃ < ⋯に対して、任意の定数0 < c < ⁠ 1/行 2⁠、そして十分に大きいi : ^{[10] [11]}

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

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

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

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

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

ある平方根のない整数m < (ln A ) ^{c ln ln ln A}に対して。^[10]

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

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

どこ

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

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

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

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

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

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

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

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

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

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

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

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

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

両辺を二乗すると

${\displaystyle 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},}$

ここで は整数である。帰納的に次のようになる。 ${\displaystyle h_{r+1}}$

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

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

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

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

ここで、p ₁ < p ₂ < ... < p _{k は}素数であり、r ₁、r ₂、...、r _{k は}正の整数である。素数の累乗の結果から、 ${\displaystyle 1\leq j\leq k}$

${\displaystyle 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}}.}$

このことから、

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

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

${\displaystyle \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 )}.}$

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

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

• カーマイケル数

• ポール・エルデシュ;カール・ポメランス;エリック・シュムッツ (1991)。 「カーマイケルのラムダ関数」。アクタ算術。58 (4): 363–385。土井：10.4064/aa-58-4-363-385。ISSN  0065-1036。MR  1121092。Zbl 0734.11047  。
• Friedlander, John B. ; Pomerance, Carl; Shparlinski, Igor 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．ドルドレヒト: クルーワー学者。 32–36、193–195ページ。ISBN 978-1-4020-2546-4.ZBL1079.11001  。​
• カーマイケル、ロバート D. [1914]。プロジェクト グーテンベルクの「数論」