Jump to content

Carmichael function

From Wikipedia, the free encyclopedia
Carmichael λ function: λ(n) for 1 ≤ n ≤ 1000 (compared to Euler φ function)

In number theory, a branch of mathematics, the Carmichael function λ(n) of a positive integer n is the smallest positive integer m such that

holds for every integer a coprime to n. In algebraic terms, λ(n) is the exponent of the multiplicative group of integers modulo n. As this is a finite abelian group, there must exist an element whose order equals the exponent, λ(n). Such an element is called a primitive λ-root modulo n.

The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910.[1] It is also known as Carmichael's λ function, the reduced totient function, and the least universal exponent function.

The order of the multiplicative group of integers modulo n is φ(n), where φ is Euler's totient function. Since the order of an element of a finite group divides the order of the group, λ(n) divides φ(n). The following table compares the first 36 values of λ(n) (sequence A002322 in the OEIS) and φ(n) (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 examples

[edit]
  • n = 5. The set of numbers less than and coprime to 5 is {1,2,3,4}. Hence Euler's totient function has value φ(5) = 4 and the value of Carmichael's function, λ(5), must be a divisor of 4. The divisor 1 does not satisfy the definition of Carmichael's function since except for . Neither does 2 since . Hence λ(5) = 4. Indeed, . Both 2 and 3 are primitive λ-roots modulo 5 and also primitive roots modulo 5.
  • n = 8. The set of numbers less than and coprime to 8 is {1,3,5,7} . Hence φ(8) = 4 and λ(8) must be a divisor of 4. In fact λ(8) = 2 since . The primitive λ-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

Recurrence for λ(n)

[edit]

The Carmichael lambda function of a prime power can be expressed in terms of the Euler totient. Any number that is not 1 or a prime power can be written uniquely as the product of distinct prime powers, in which case λ of the product is the least common multiple of the λ of the prime power factors. Specifically, λ(n) is given by the recurrence

Euler's totient for a prime power, that is, a number pr with p prime and r ≥ 1, is given by

Carmichael's theorems

[edit]

Carmichael proved two theorems that, together, establish that if λ(n) is considered as defined by the recurrence of the previous section, then it satisfies the property stated in the introduction, namely that it is the smallest positive integer m such that for all a relatively prime to n.

Theorem 1 — If a is relatively prime to n then .[2]

This implies that the order of every element of the multiplicative group of integers modulo n divides λ(n). Carmichael calls an element a for which is the least power of a congruent to 1 (mod n) a primitive λ-root modulo n.[3] (This is not to be confused with a primitive root modulo n, which Carmichael sometimes refers to as a primitive -root modulo n.)

Theorem 2 — For every positive integer n there exists a primitive λ-root modulo n. Moreover, if g is such a root, then there are primitive λ-roots that are congruent to powers of g.[4]

If g is one of the primitive λ-roots guaranteed by the theorem, then has no positive integer solutions m less than λ(n), showing that there is no positive m < λ(n) such that for all a relatively prime to n.

The second statement of Theorem 2 does not imply that all primitive λ-roots modulo n are congruent to powers of a single root g.[5] For example, if n = 15, then λ(n) = 4 while and . There are four primitive λ-roots modulo 15, namely 2, 7, 8, and 13 as . The roots 2 and 8 are congruent to powers of each other and the roots 7 and 13 are congruent to powers of each other, but neither 7 nor 13 is congruent to a power of 2 or 8 and vice versa. The other four elements of the multiplicative group modulo 15, namely 1, 4 (which satisfies ), 11, and 14, are not primitive λ-roots modulo 15.

For a contrasting example, if n = 9, then and . There are two primitive λ-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other. They are also both primitive -roots modulo 9.

Properties of the Carmichael function

[edit]

In this section, an integer is divisible by a nonzero integer if there exists an integer such that . This is written as

A consequence of minimality of λ(n)

[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 that r = 0 since r < λ(n) and λ(n) is the minimal positive exponent for which the congruence holds for all a coprime with n.

λ(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. In particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a primitive root, which is the case for odd prime powers.

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

Divisibility

[edit]

Proof.

By definition, for any integer with (and thus also ), we have that , and therefore . This establishes that for all k relatively prime to a. By the consequence of minimality proved above, we have .

Composition

[edit]

For all positive integers a and b it holds that

.

This is an immediate consequence of the recurrence for the Carmichael function.

Exponential cycle length

[edit]

If is the biggest exponent in the prime factorization of n, 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:[6][7]

(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)[8] positive integers nN (a "prevailing" majority):

with the constant[7]

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−Δ.[9]

Minimal order

[edit]

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

Small values

[edit]

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

Moreover, n is of the form

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

Image of the function

[edit]

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

where

Use in cryptography

[edit]

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

Proof of Theorem 1

[edit]

For n = p, a prime, Theorem 1 is equivalent to Fermat's little theorem:

For prime powers pr, r > 1, if

holds for some integer h, then raising both sides to the power p gives

for some other integer . By induction it follows that for all a relatively prime to p and hence to pr. This establishes the theorem for n = 4 or any odd prime power.

Sharpening the result for higher powers of two

[edit]

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

,

where is an integer. With r = 3, this is written

Squaring both sides gives

where is an integer. It follows by induction that

for all and all a coprime to .[13]

Integers with multiple prime factors

[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. The results for prime powers establish that, for ,

From this it follows that

where, as given by the recurrence,

From the Chinese remainder theorem one concludes that

See also

[edit]

Notes

[edit]
  1. ^ Carmichael, Robert Daniel (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/S0002-9904-1910-01892-9.
  2. ^ Carmichaael (1914) p.40
  3. ^ Carmichael (1914) p.54
  4. ^ Carmichael (1914) p.55
  5. ^ Carmichael (1914) p.56
  6. ^ Theorem 3 in Erdős (1991)
  7. ^ a b Sándor & Crstici (2004) p.194
  8. ^ Theorem 2 in Erdős (1991) 3. Normal order. (p.365)
  9. ^ Theorem 5 in Friedlander (2001)
  10. ^ a b Theorem 1 in Erdős (1991)
  11. ^ a b Sándor & Crstici (2004) p.193
  12. ^ 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. S2CID 50397623.
  13. ^ Carmichael (1914) pp.38–39

References

[edit]