Carmichael function

From Wikipedia, the free encyclopedia
  (Redirected from Carmichael's totient function)
Jump to navigation Jump to search
Carmichael λ function: λ(n) for 1 ≤ n ≤ 1000 (compared to Euler φ 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

am ≡ 1   (mod n)

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 ns such that they are different are listed in OEISA033949).

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[edit]

Carmichael's function at 8 is 2, λ(8) = 2, because for any number a coprime to 8 it holds that a2 ≡ 1 (mod 8). Namely, 12 = 1 (mod 8), 32 = 9 ≡ 1 (mod 8), 52 = 25 ≡ 1 (mod 8) and 72 = 49 ≡ 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 a4 ≡ 1 (mod 8) for all a coprime to 8, but 4 is not the smallest such exponent.

Computing λ(n) with Carmichael's theorem[edit]

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

where p1 < p2 < ... < pk are primes and r1, r2, ..., rk are positive integers. Then λ(n) is the least common multiple of the λ of each of its prime power factors:

This can be proved using the Chinese remainder theorem.

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

Euler's function for prime powers pr is given by

Properties of the Carmichael function[edit]

Order of elements modulo n[edit]

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

.

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

Minimality[edit]

Suppose am ≡ 1 (mod n) for all numbers a coprime with n. Then λ(n) | m.

Proof: If m = (n) + r with 0 ≤ r < λ(n), then

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[edit]

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

where we take advantage of the fact that C := (h + 1)h/2 is an integer.

So, for k = 3, h an integer:

By induction, when k ≥ 3, we have

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

λ(n) divides φ(n)[edit]

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[edit]

Proof. The result follows from the formula

mentioned above.

Composition[edit]

For all positive integers a and b it holds that

.

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

Exponential cycle length[edit]

If n has maximum prime exponent rmax under prime factorization, then for all a (including those not coprime to n) and all rrmax,

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

Average value[edit]

For any n ≥ 16:[2][3]

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

and γ ≈ 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λ(n) > n4/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 ≤ n67108863 have λ(n) > n4/5 meaning that the majority of the λ values is exponential in the length l := log2(n) of the input n, namely

ν n = 2ν – 1 sum
average
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[edit]

For all numbers N and all but o(N)[4] positive integers nN (a "prevailing" majority):

with the constant[3]

Lower bounds[edit]

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

positive integers n ≤ N such that λ(n) ≤ ne−Δ.[5]

Minimal order[edit]

For any sequence n1 < n2 < n3 < ⋯ of positive integers, any constant 0 < c < 1/ln 2, and any sufficiently large i:[6][7]

Small values[edit]

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

Moreover, n is of the form

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

Image of the function[edit]

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

where

Use in cryptography[edit]

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

See also[edit]

Notes[edit]

  1. ^ Carmichael, Robert Daniel. The Theory of Numbers. Nabu Press. ISBN 1144400341.[page needed]
  2. ^ Theorem 3 in Erdős (1991)
  3. ^ a b Sándor & Crstici (2004) p.194
  4. ^ Theorem 2 in Erdős (1991) 3. Normal order. (p.365)
  5. ^ Theorem 5 in Friedlander (2001)
  6. ^ a b Theorem 1 in Erdős 1991
  7. ^ a b 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.

References[edit]