Carmichael Function - Carmichael's Theorem

Carmichael's Theorem

For a power of an odd prime, twice the power of an odd prime, and for 2 and 4, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater than 4 it is equal to one half of the Euler totient:

$\lambda(n) = \begin{cases} \;\;\varphi(n) &\mbox{if }n = 2,3,4,5,7,9,11,13,17,19,23,25,27,\dots\\ \tfrac12\varphi(n)&\text{if }n=8,16,32,64,\dots \end{cases}$

Euler's function for prime powers is given by

$\varphi(p^k) = p^{k-1}(p-1).\;$

By the fundamental theorem of arithmetic any n > 1 can be written in a unique way

$n= p_1^{a_1}p_2^{a_2} \dots p_{\omega(n)}^{a_{\omega(n)}}$

where p₁ < p₂ < ... < p_ω are primes and the a_i > 0. (n = 1 corresponds to the empty product.)

For general n λ(n) is the least common multiple of λ of each of its prime power factors:

$\lambda(n) = \operatorname{lcm}.$

Carmichael's theorem states that if a is coprime to n, then

where is the Carmichael function defined above. In other words, it asserts the correctness of the formulas. This can be proven by considering any primitive root modulo n and the Chinese remainder theorem.

Read more about this topic: Carmichael Function

Famous quotes containing the words carmichael and/or theorem:

“An impersonal and scientific knowledge of the structure of our bodies is the surest safeguard against prurient curiosity and lascivious gloating.”
—Marie Carmichael Stopes (1880–1958)

“To insure the adoration of a theorem for any length of time, faith is not enough, a police force is needed as well.”
—Albert Camus (1913–1960)