Carmichael function: Difference between revisions

Revision as of 22:40, 7 March 2025

Latest revision as of 01:52, 8 August 2025

(2 intermediate revisions by 2 users not shown)

Line 4:

holds for every integer {{mvar | a}} [[coprime]] to {{mvar | n}}. In algebraic terms, {{math | ''λ''(''n'')}} is the [[exponent of a group|exponent]] of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo {{mvar | n}}]]. As this is a [[Abelian group#Finite abelian groups|finite abelian group]], there must exist an element whose [[Cyclic group#Definition and notation|order]] equals the exponent, {{math | ''λ''(''n'')}}. Such an element is called a '''primitive {{math | ''λ''}}-root modulo {{mvar | n}}'''.

[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael {{mvar | λ}} function: {{math | ''λ''(''n'')}} for {{math | 1 ≤ ''n'' ≤ 1000}} (compared to Euler {{mvar | φ}} function)|none]]

The Carmichael function is named after the American mathematician [[Robert Daniel Carmichael|Robert Carmichael]] who defined it in 1910.<ref>

Line 10:

</ref> It is also known as '''Carmichael's λ function''', the '''reduced totient function''', and the '''least universal exponent function'''.

The order of the multiplicative group of integers modulo {{mvar | n}} is {{math | ''φ''(''n'')}}, where {{mvar | φ}} is [[Euler's totient function]]. Since the order of an element of a finite group divides the order of the group, {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}}. The following table compares the first 36 values of {{math | ''λ''(''n'')}} {{OEIS|id=A002322}} and {{math | ''φ''(''n'')}} (in '''bold''' if they are different; the values of{{mvar | n}}s such that they are different are listed in {{oeis|A033949}}).

{| class="wikitable" style="text-align: center;"

Line 60:

==Numerical examples==

* {{math | ''n'' {{=}} 5}}. The set of numbers less than and coprime to 5 is {{math | {1,2,3,4}}}. Hence Euler's totient function has value {{math | ''φ''(5) {{=}} 4}} and the value of Carmichael's function, {{math | ''λ''(5)}}, must be a [[divisor]] of 4. The divisor 1 does not satisfy the definition of Carmichael's function since <math>a^1 \not\equiv 1\pmod{5}</math> except for <math>a\equiv1\pmod{5}</math>. Neither does 2 since <math>2^2 \equiv 3^2 \equiv 4 \not\equiv 1\pmod{5}</math>. Hence {{math | ''λ''(5) {{=}} 4}}. Indeed, <math>1^4\equiv 2^4\equiv 3^4\equiv 4^4\equiv1\pmod{5}</math>. Both 2 and 3 are primitive {{mvar | λ}}-roots modulo 5 and also [[Primitive root modulo n|primitive roots]] modulo 5.

* {{math | ''n'' {{=}} 8}}. The set of numbers less than and coprime to 8 is {{math | {1,3,5,7} }}. Hence {{math | ''φ''(8) {{=}} 4}} and {{math | ''λ''(8)}} must be a divisor of 4. In fact {{math | ''λ''(8) {{=}} 2}} since <math>1^2\equiv 3^2\equiv 5^2\equiv 7^2\equiv1\pmod{8}</math>. The primitive {{mvar | λ}}-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

== Recurrence for {{math | ''λ''(''n'')}} ==

The Carmichael lambda function of a [[prime power]] can be expressed in terms of the Euler totient. Any number that is not 1 or a prime power can be written uniquely as the product of distinct prime powers, in which case {{mvar | λ}} of the product is the [[least common multiple]] of the {{mvar | λ}} of the prime power factors. Specifically, {{math | ''λ''(''n'')}} is given by the recurrence

:<math>\lambda(n) = \begin{cases}

\varphi(n) & \text{if }n\text{ is 1, 2, 4, or an odd prime power,}\\

Line 244:

==Proof of Theorem 1==

For {{math | ''n'' {{=}} ''p''}}, a prime, Theorem 1 is equivalent to [[Fermat's little theorem]]:

:<math>a^{p-1}\equiv1\pmod{p}\qquad\text{for all }a\text{ coprime to }p.</math>

For prime powers {{math | ''p''^''r''}}, {{math | ''r'' > 1}}, if