Carmichael 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

Carmichael λ function: λ(n) for 1 ≤ n ≤ 1000 (compared to Euler φ function)

holds for every integer a 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 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 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 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) 11224262641021264416618461022220121862843081016126
φ(n) 112242646410412688166188121022820121812288301620162412

Numerical examples

  1. Carmichael's function at 5 is 4, λ(5) = 4, because for any number coprime to 5, i.e. there is with namely, 11⋅4 = 14 ≡ 1 (mod 5), 24 = 16 ≡ 1 (mod 5), 34 = 81 ≡ 1 (mod 5) and 42⋅2 = 162 ≡ 12 (mod 5). And this m = 4 is the smallest exponent with this property, because (and as well.)
    Moreover, Euler's totient function at 5 is 4, φ(5) = 4, because there are exactly 4 numbers less than and coprime to 5 (1, 2, 3, and 4). Euler's theorem assures that a4 ≡ 1 (mod 5) for all a coprime to 5, and 4 is the smallest such exponent.
  2. Carmichael's function at 8 is 2, λ(8) = 2, because for any number a coprime to 8, i.e. it holds that a2 ≡ 1 (mod 8). Namely, 11⋅2 = 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 exactly 4 numbers less than and coprime to 8 (1, 3, 5, and 7). Moreover, 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

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

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

Order of elements modulo n

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

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.

λ(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. 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

Proof.

By definition, for any integer with (and thus also ), we have that , and therefore . By the minimality property above, we have .

Composition

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

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

Extension for powers of two

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.[2]

Average value

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

(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ν – 1sum
average
Erdős averageErdős /
exact average
LoL average % LoL > 4/5 % LoL > 7/8
5312708.70967768.6437.88130.67824441.9435.48
66396415.30158761.4144.01360.69989138.1030.16
7127357428.14173286.6053.07740.71729138.5827.56
82551299450.956863138.1902.71190.73033138.8223.53
95114803293.996086233.1492.48040.74049840.9025.05
101023178816174.795699406.1452.32350.74848241.4526.98
112047662952323.865169722.5262.23090.75488642.8427.70
1240952490948608.2901101304.8102.14500.76102743.7428.11
13819193827641145.4967652383.2632.08060.76657144.3328.60
1416383355045862167.1602274392.1292.02670.77169546.1029.52
15327671347368244111.9670408153.0541.98280.77643747.2129.15
16655355137587967839.45671815225.4301.94220.78106449.1328.17
17131071196441359214987.40066028576.9701.90670.78540150.4329.55
18262143752921820828721.79768053869.7601.87560.78956151.1730.67
195242872893564434255190.466940101930.9001.84690.79353652.6231.45
201048575111393101150106232.840900193507.1001.82150.79735153.7431.83
212097151429685077652204889.909000368427.6001.79820.80101854.9732.18
2241943031660388309120395867.515800703289.4001.77660.80454356.2433.65
2383886076425917227352766029.1187001345633.0001.75660.80793657.1934.32
2416777215249068726559901484565.3860002580070.0001.73790.81120458.4934.43
2533554431966665958654302880889.1400004956372.0001.72040.81435159.5235.76
26671088633756190480865765597160.0660009537863.0001.70410.81738460.4936.73

Prevailing interval

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

with the constant[4]

Lower bounds

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

Minimal order

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

Small values

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

Moreover, n is of the form

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

Image of the function

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

where

Use in cryptography

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

See also

Notes

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

References

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