Carmichael function

In number theory, the Carmichael function associates to every positive integer n a positive integer λ ( n ) {displaystyle lambda (n)} , defined as the smallest positive integer m such that In number theory, the Carmichael function associates to every positive integer n a positive integer λ ( n ) {displaystyle lambda (n)} , defined as the smallest positive integer m such that (Dropping the phrase 'between 1 and n' leads to an equivalent definition.) In algebraic terms, λ ( n ) {displaystyle lambda (n)} 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 λ ( n ) {displaystyle lambda (n)} (sequence A002322 in the OEIS) compared to Euler's totient function φ {displaystyle varphi } . (in bold if they are different, the ns such that they are different are listed in OEIS: A033949) Carmichael's function at 8 is 2, i.e. λ ( 8 ) = 2 {displaystyle lambda (8)=2} , 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. φ ( 8 ) = 4 {displaystyle varphi (8)=4} , 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. By the fundamental theorem of arithmetic 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: