Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Carmichael function
Summary
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.
The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910. 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) with Euler's totient function φ (in bold if they are different; the ns such that they are different are listed in ).
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.
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.
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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.