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, the Carmichael function associates to every positive integer n a positive integer , defined as the smallest positive integer m such that

for every integer a between 1 and n that is coprime to n.

In algebraic terms, 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 (sequence A002322 in the OEIS) compared to 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
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
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, i.e. , because for any number a co-prime 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, i.e. , because there are 4 numbers lesser 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 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 , then it holds

.

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

Minimality[edit]

Suppose for all numbers a coprime with n. Then .

Proof. If with , then

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

Extension for powers of two[edit]

For a coprime to (powers of) 2 we have . Then,

where we take advantage of the fact that is an integer.

So, for k = 3, h an integer:

By induction, when k ≥ 3, we have .

It provides that is at most . [1]

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

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.

Divisibility[edit]

Proof. The result follows from the formula

mentioned above.

Composition[edit]

For all positive integers and it holds

.

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

Exponential cycle length[edit]

If has maximum prime exponent under prime factorization, then for all (including those not co-prime to ) and all ,

In particular, for squarefree (), for all

Average value[edit]

For any n ≥ 16:

[2][3]

(called Erdős-approximation in the sequel) with the constant

and , 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         .

There, the table entry in row number 26 at column

  •  % LoL > 4/5               60.49

indicates that 60.49 % (≈ 40,000,000) of the numbers have meaning that the majority of the λ-values is exponential in the length of the input , 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.43 1.9422 0.781064 49.13 28.17
17 131071 1964413592 14987.40066 28576.97 1.9067 0.785401 50.43 29.55
18 262143 7529218208 28721.79768 53869.76 1.8756 0.789561 51.17 30.67
19 524287 28935644342 55190.46694 101930.9 1.8469 0.793536 52.62 31.45
20 1048575 111393101150 106232.8409 193507.1 1.8215 0.797351 53.74 31.83
21 2097151 429685077652 204889.9090 368427.6 1.7982 0.801018 54.97 32.18
22 4194303 1660388309120 395867.5158 703289.4 1.7766 0.804543 56.24 33.65
23 8388607 6425917227352 766029.1187 1345633 1.7566 0.807936 57.19 34.32
24 16777215 24906872655990 1484565.386 2580070 1.7379 0.811204 58.49 34.43
25 33554431 96666595865430 2880889.140 4956372 1.7204 0.814351 59.52 35.76
26 67108863 375619048086576 5597160.066 9537863 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 , there are at most

positive integers such that .[5]

Minimal order[edit]

For any sequence of positive integers, any constant , and any sufficiently large i:

.[6][7]

Small values[edit]

For a constant c and any sufficiently large positive A, there exists an integer such that .[7] Moreover, n is of the form

for some square-free integer .[6]

Image of the function[edit]

The set of values of the Carmichael function has counting function

where ….[8]

Use in cryptography[edit]

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

See also[edit]

Notes[edit]

  1. ^ Robert Daniel Carmichael. The Theory of Numbers. Nabu Press. ISBN 1144400341.
  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]