Carmichael function λ(n): smallest k with aᵏ≡1 (mod n) for all gcd(a,n)=1. Always divides φ(n), equals φ(n) iff (Z/nZ)* is cyclic. λ(pᵏ)=φ(pᵏ) for odd p, λ(2)=1, λ(4)=2, λ(2ᵏ)=2ᵏ⁻². For n=p₁ᵉ¹·...·pₖᵉᵏ: λ(n)=lcm(λ(pᵢᵉⁱ)).
How to Use
Enter n:
- λ(n): Carmichael function
- φ(n): Euler's totient
- Ratio: φ(n)/λ(n)
Formula
- λ(1)=1, λ(2)=1, λ(4)=2
- λ(pᵏ) = φ(pᵏ) = pᵏ⁻¹(p−1) for odd p
- λ(2ᵏ) = 2ᵏ⁻² for k≥3
- λ(n) = lcm(λ(pᵢᵉⁱ))
Carmichael Numbers
n is Carmichael if aⁿ≡a (mod n) for all a, but n is composite. Equivalently: λ(n)|(n−1). First: 561=3·11·17. Infinitely many exist (Alford-Granville-Pomerance, 1994).
Step-by-Step Instructions
- 1Enter n.
- 2Get λ(n).
- 3Compare φ(n).
- 4Check Carmichael.
- 5See factorization.