Carmichael function

In number theory, a branch of mathematics, the Carmichael function associates to every positive integer $n$ a positive integer $λ (n)$ , defined as the smallest positive integer $m$ such that

a m \equiv 1 (mod n)

Carmichael

λ

function:

λ (n)

for

1 \leq n \leq 1000

(compared to Euler

φ

function)

for every integer $a$ between 1 and $n$ that is coprime to $n$ . In algebraic terms, $λ (n)$ is the exponent of the multiplicative group of integers modulo $n$ .

The Carmichael function is named after the American mathematician Robert Carmichael and is also known as the reduced totient function or the least universal exponent function.

The following table compares the first 36 values of $λ (n)$ (sequence A002322 in the OEIS) with Euler's totient function $φ$ (in bold if they are different; the $n$ s such that they are different are listed in 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

Numerical example

Carmichael's function at 8 is 2, $λ (8) = 2$ , because for any number $a$ coprime to 8 it holds that $a 2 \equiv 1 (mod 8)$ . Namely, $12 = 1 (mod 8)$ , $32 = 9 \equiv 1 (mod 8)$ , $52 = 25 \equiv 1 (mod 8)$ and $72 = 49 \equiv 1 (mod 8)$ . Euler's totient function at 8 is 4, $φ (8) = 4$ , because there are 4 numbers less than and coprime to 8 (1, 3, 5, and 7). Euler's theorem assures that $a 4 \equiv 1 (mod 8)$ for all $a$ coprime to 8, but 4 is not the smallest such exponent.

Computing $λ (n)$ with Carmichael's theorem

By the unique factorization theorem, any $n > 1$ can be written in a unique way as

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

where $p 1 < p 2 < ... < p k$ are primes and $r 1, r 2, ..., r k$ are positive integers. Then $λ (n)$ is the least common multiple of the $λ$ of each of its prime power factors:

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

This can be proved using the Chinese remainder theorem.

Carmichael's theorem explains how to compute $λ$ of a prime power $p r$ : for a power of an odd prime and for 2 and 4, $λ (p r)$ is equal to the Euler totient $φ (p r)$ ; for powers of 2 greater than 4 it is equal to half of the Euler totient:

\lambda (p^{r})={\begin{cases}\varphi \left(p^{r}\right)&{\mbox{if }}p^{r}=2,3^{r},4,5^{r},7^{r},11^{r},13^{r},17^{r},19^{r},23^{r},29^{r},31^{r},\dots \\{\tfrac {1}{2}}\varphi \left(p^{r}\right)&{\text{if }}p^{r}=8,16,32,64,128,256,\dots \end{cases}}

Euler's function for prime powers $p r$ is given by

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

Properties of the Carmichael function

Order of elements modulo $n$

Let $a$ and $n$ be coprime and let $m$ be the smallest exponent with $a m \equiv 1 (mod n)$ , then it holds that

m\,|\,\lambda (n)

.

That is, the order $m := ord n (a)$ of a unit $a$ in the ring of integers modulo $n$ divides $λ (n)$ and

\lambda (n)=\max\{\operatorname {ord} _{n}(a)\,\colon \,\gcd(a,n)=1\}

Minimality

Suppose $a m \equiv 1 (mod n)$ for all numbers $a$ coprime with $n$ . Then $λ (n) | m$ .

Proof: If $m = kλ (n) + r$ with $0 \leq r < λ (n)$ , then

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}}

for all numbers $a$ coprime with $n$ . It follows $r = 0$ , since $r < λ (n)$ and $λ (n)$ the minimal positive such number.

Extension for powers of two

For $a$ coprime to (powers of) 2 we have $a = 1 + 2 h$ for some $h$ . Then,

a^{2}=1+4h(h+1)=1+8C

where we take advantage of the fact that $C := .mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px;white-space:nowrap} (h + 1) h / 2$ is an integer.

So, for $k = 3$ , $h$ an integer:

{\begin{aligned}a^{2^{k-2}}&=1+2^{k}h\\a^{2^{k-1}}&=\left(1+2^{k}h\right)^{2}=1+2^{k+1}\left(h+2^{k-1}h^{2}\right)\end{aligned}}

By induction, when $k \geq 3$ , we have

a^{2^{k-2}}\equiv 1{\pmod {2^{k}}}.

It provides that $λ (2 k)$ is at most $2 k - 2$ .[1]

$λ (n)$ divides $φ (n)$

This follows from elementary group theory, because the exponent of any finite group must divide the order of the group. $λ (n)$ is the exponent of the multiplicative group of integers modulo $n$ while $φ (n)$ is the order of that group.

We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

Divisibility

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

Proof. The result follows from the formula

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

mentioned above.

Composition

For all positive integers $a$ and $b$ it holds that

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

.

This is an immediate consequence of the recursive definition of the Carmichael function.

Exponential cycle length

If $n$ has maximum prime exponent $r max$ under prime factorization, then for all $a$ (including those not coprime to $n$ ) and all $r \geq r max$ ,

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

In particular, for square-free $n$ ( $r max = 1$ ), for all $a$ we have

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

Average value

For any $n \geq 16$ :[2][3]

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

(called Erdős approximation in the following) with the constant

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

and $γ \approx 0.57721$ , the Euler–Mascheroni constant.

The following table gives some overview over the first $226 - 1 = 67108863$ values of the $λ$ function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible “logarithm over logarithm” values $LoL(n) := ln λ (n) / ln n$ with

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

There, the table entry in row number 26 at column

$% LoL > 4 / 5$ → 60.49

indicates that 60.49% (≈ 40000000) of the integers $1 \leq n \leq 67108863$ have $λ (n) > n 4 / 5$ meaning that the majority of the $λ$ values is exponential in the length $l := log 2 (n)$ of the input $n$ , namely

\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 $\sum _{i\leq n}\lambda (i)$	average ${\tfrac {1}{n}}\sum _{i\leq n}\lambda (i)$	Erdős average	Erdős / exact average	$LoL$ average	% $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.430	1.9422	0.781064	49.13	28.17
17	131071	1964413592	14987.400660	28576.970	1.9067	0.785401	50.43	29.55
18	262143	7529218208	28721.797680	53869.760	1.8756	0.789561	51.17	30.67
19	524287	28935644342	55190.466940	101930.900	1.8469	0.793536	52.62	31.45
20	1048575	111393101150	106232.840900	193507.100	1.8215	0.797351	53.74	31.83
21	2097151	429685077652	204889.909000	368427.600	1.7982	0.801018	54.97	32.18
22	4194303	1660388309120	395867.515800	703289.400	1.7766	0.804543	56.24	33.65
23	8388607	6425917227352	766029.118700	1345633.000	1.7566	0.807936	57.19	34.32
24	16777215	24906872655990	1484565.386000	2580070.000	1.7379	0.811204	58.49	34.43
25	33554431	96666595865430	2880889.140000	4956372.000	1.7204	0.814351	59.52	35.76
26	67108863	375619048086576	5597160.066000	9537863.000	1.7041	0.817384	60.49	36.73

Prevailing interval

For all numbers $N$ and all but $o (N)$ [4] positive integers $n \leq N$ (a "prevailing" majority):

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

with the constant[3]

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

Lower bounds

For any sufficiently large number $N$ and for any $Δ \geq (ln ln N) 3$ , there are at most

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

positive integers $n \leq N$ such that $λ (n) \leq ne -Δ$ .[5]

Minimal order

For any sequence $n 1 < n 2 < n 3 < \dots$ of positive integers, any constant $0 < c < 1 / ln 2$ , and any sufficiently large $i$ :[6][7]

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

Small values

For a constant $c$ and any sufficiently large positive $A$ , there exists an integer $n > A$ such that[7]

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

Moreover, $n$ is of the form

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

for some square-free integer $m < (ln A) c ln ln ln A$ .[6]

Image of the function

The set of values of the Carmichael function has counting function[8]

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

where

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

Use in cryptography

The Carmichael function is important in cryptography due to its use in the RSA encryption algorithm.

Notes

Carmichael, Robert Daniel. The Theory of Numbers. Nabu Press. ISBN 1144400341.
Theorem 3 in Erdős (1991)
Sándor & Crstici (2004) p.194
Theorem 2 in Erdős (1991) 3. Normal order. (p.365)
Theorem 5 in Friedlander (2001)
Theorem 1 in Erdős 1991
Sándor & Crstici (2004) p.193
Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". Algebra & Number Theory. 8 (8): 2009–2026. arXiv:1408.6506. doi:10.2140/ant.2014.8.2009.

References

Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica. 58 (4): 363–385. doi:10.4064/aa-58-4-363-385. ISSN 0065-1036. MR 1121092. Zbl 0734.11047.
Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Period of the power generator and small values of the Carmichael function". Mathematics of Computation. 70 (236): 1591–1605, 1803–1806. doi:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
Carmichael, R. D. (2004-10-10). The Theory of Numbers. Nabu Press. ISBN 978-1144400345.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[car-1] Carmichael, Robert Daniel. The Theory of Numbers. Nabu Press. ISBN 1144400341.

[2] Theorem 3 in Erdős (1991)

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

[4] Theorem 2 in Erdős (1991) 3. Normal order. (p.365)

[5] Theorem 5 in Friedlander (2001)

[Theorem_1_in_Erdős_1991-6] Theorem 1 in Erdős 1991

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

[8] Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". Algebra & Number Theory. 8 (8): 2009–2026. arXiv:1408.6506. doi:10.2140/ant.2014.8.2009.