Vfrdtyky

In number theory, the Carmichael function associates to every positive integer n a positive integer λ(n){displaystyle lambda (n)}, defined as the smallest positive integer m such that

am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}} for every integer a between 1 and n that is coprime to n.

(Dropping the phrase "between 1 and n" leads to an equivalent definition.)
In algebraic terms, λ(n){displaystyle lambda (n)} equals 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 first 36 values of λ(n){displaystyle lambda (n)} (sequence A002322 in the OEIS) compared to Euler's totient function φ{displaystyle varphi }. (in bold if they are different, the ns 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){displaystyle lambda (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){displaystyle varphi (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, i.e. λ(8)=2{displaystyle lambda (8)=2}, because for any number a co-prime to 8 it holds that a² ≡ 1 (mod 8). Namely, 1² = 1 (mod 8), 3² = 9 ≡ 1 (mod 8), 5² = 25 ≡ 1 (mod 8) and 7² = 49 ≡ 1 (mod 8). Euler's totient function at 8 is 4, i.e. φ(8)=4{displaystyle varphi (8)=4}, because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Euler's theorem assures that a⁴ ≡ 1 (mod 8) for all a coprime to 8, but 4 is not the smallest such exponent.

Computing λ(n){displaystyle lambda (n)} with Carmichael's theorem

By the fundamental theorem of arithmetic any n > 1 can be written in a unique way as

n=p1r1p2r2…pkrk{displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}dots p_{k}^{r_{k}}}

where p₁ < p₂ < ... < p_k are primes and r₁ , ..., r_k are positive integers. It is then the case that λ(n) is the least common multiple of the λ of each of its prime power factors:

λ(n)=lcm⁡(λ(p1r1),λ(p2r2),…,λ(pkrk)).{displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}.}

This can be proved using the Chinese Remainder Theorem.

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

Euler's function for prime powers is given by

φ(pr)=pr−1(p−1).{displaystyle varphi (p^{r})=p^{r-1}(p-1).;}

Properties of the Carmichael function

λ(n) divides φ(n)

This follows from elementary group theory, because the exponent of any finite abelian 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.

Minimality

Suppose am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}} for all numbers a coprime with n. Then λ(n)|m{displaystyle lambda (n)|m}.

Proof. If m=kλ(n)+r{displaystyle m=k;lambda (n)+r} with 0≤r<λ(n){displaystyle 0leq r<lambda (n)}, then ar=1k⋅ar≡(aλ(n))k⋅ar=akλ(n)+r=am≡1(modn){displaystyle a^{r}=1^{k}cdot a^{r}equiv (a^{lambda (n)})^{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{displaystyle r=0} , since r<λ(n){displaystyle r<lambda (n)} and λ(n){displaystyle lambda (n)} the minimal positive such number.

Divisibility

a|b⇒λ(a)|λ(b){displaystyle a|bRightarrow lambda (a)|lambda (b)}

Proof. The result follows from the formula

λ(n)=lcm⁡(λ(p1r1),λ(p2r2),…,λ(pkrk)){displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}}

mentioned above.

Composition

For all positive integers a{displaystyle a} and b{displaystyle b} it holds

λ(lcm(a,b))=lcm(λ(a),λ(b)){displaystyle lambda (mathrm {lcm} (a,b))=mathrm {lcm} (lambda (a),lambda (b))} .

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

Primitive m-th roots of unity

Let a{displaystyle a} and n{displaystyle n} be coprime and
let m{displaystyle m} be the smallest exponent with am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}},
then it holds

m|λ(n){displaystyle m|lambda (n)} .

That is, the orders of primitive roots of unity in the ring of integers modulo n{displaystyle n} are divisors of λ(n){displaystyle lambda (n)}.

Exponential cycle length

If n{displaystyle n} has maximum prime exponent rmax{displaystyle r_{rm {max}}} under prime factorization, then for all a{displaystyle a} (including those not co-prime to n{displaystyle n}) and all r≥rmax{displaystyle rgeq r_{rm {max}}},

ar≡ar+λ(n)(modn){displaystyle a^{r}equiv a^{r+lambda (n)}{pmod {n}}}

In particular, for squarefree n{displaystyle n} (rmax=1{displaystyle r_{rm {max}}=1}), for all a{displaystyle a}

a≡aλ(n)+1(modn){displaystyle aequiv a^{lambda (n)+1}{pmod {n}}}

Average and typical value

For any x > 16:

1x∑n≤xλ(n)=xln⁡xeB(1+o(1))ln⁡ln⁡x/(ln⁡ln⁡ln⁡x){displaystyle {frac {1}{x}}sum _{nleq x}lambda (n)={frac {x}{ln x}}e^{B(1+o(1))ln ln x/(ln ln ln x)}}.^[1][2]

Where B is a constant,

B=e−γ∏p(1−1(p−1)2(p+1))≈0.34537 .{displaystyle B=e^{-gamma }prod _{p}left({1-{frac {1}{(p-1)^{2}(p+1)}}}right)approx 0.34537 .}

For all numbers N and all except o(N) positive integers n ≤ N:

λ(n)=n/(ln⁡n)ln⁡ln⁡ln⁡n+A+o(1){displaystyle lambda (n)=n/(ln n)^{ln ln ln n+A+o(1)},}

where A is a constant,^[2][3]

A=−1+∑plog⁡p(p−1)2≈0.2269688 .{displaystyle A=-1+sum _{p}{frac {log p}{(p-1)^{2}}}approx 0.2269688 .}

Lower bounds

For any sufficiently large number N and for any Δ≥(ln⁡ln⁡N)3{displaystyle Delta geq (ln ln N)^{3}}, there are at most

Ne−0.69(Δln⁡Δ)1/3{displaystyle Ne^{-0.69(Delta ln Delta )^{1/3}}}

positive integers n≤N{displaystyle nleq N} such that λ(n)≤ne−Δ{displaystyle lambda (n)leq ne^{-Delta }}.^[4]

For any sequence n1<n2<n3<⋯{displaystyle n_{1}<n_{2}<n_{3}<cdots } of positive integers, any constant 0<c<1/ln⁡2{displaystyle 0<c<1/ln 2}, and any sufficiently large i:

λ(ni)>(ln⁡ni)cln⁡ln⁡ln⁡ni{displaystyle lambda (n_{i})>(ln n_{i})^{cln ln ln n_{i}}}.^[5][6]

Small values

For a constant c and any sufficiently large positive A, there exists an integer n>A{displaystyle n>A} such that λ(n)<(ln⁡A)cln⁡ln⁡ln⁡A{displaystyle lambda (n)<(ln A)^{cln ln ln A}}.^[6]
Moreover, n is of the form

n=∏(q−1)|m and q is primeq{displaystyle n=prod _{(q-1)|m{text{ and }}q{text{ is prime}}}q}

for some square-free integer m<(ln⁡A)cln⁡ln⁡ln⁡A{displaystyle m<(ln A)^{cln ln ln A}}.^[5]

Image of the function

The set of values of the Carmichael function has counting function

x(log⁡x)η+o(1) ,{displaystyle {frac {x}{(log x)^{eta +o(1)}}} ,}

where η=1−1+log⁡log⁡2log⁡2=0.08607{displaystyle eta =1-{frac {1+log log 2}{log 2}}=0.08607}….^[7]

Use in cryptography

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

See also

• Carmichael number

Notes

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.