Carmichael function: Difference between revisions

Revision as of 05:43, 17 October 2024

Latest revision as of 01:52, 8 August 2025

(4 intermediate revisions by 4 users not shown)

Line 1:

{{Short description|Function in mathematical number theory}}

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

In [[number theory]], a branch of [[mathematics]], the '''Carmichael function''' {{math | ''λ''(''n'')}} of a [[positive integer]] {{mvar | n}} is the smallest positive integer {{mvar|m}} such that

:<math>a^m \equiv 1 \pmod{n}</math>

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 9 ⟶ 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 59 ⟶ 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 75 ⟶ 76:

{{anchor|Carmichael's theorem}}

Carmichael proved two theorems that, together, establish that if {{math | ''λ''(''n'')}} is considered as defined by the recurrence of the previous section, then it satisfies the property stated in the introduction, namely that it is the smallest positive integer {{mvar | m}} such that <math>a^m\equiv 1\pmod{n}</math> for all {{mvar | a}} relatively prime to {{mvar | n}}.

{{Math theorem |name=Theorem 1|math_statement=If {{mvar | a}} is relatively prime to {{mvar | n}} then <math>a^{\lambda(n)}\equiv 1\pmod{n}</math>.<ref>CarmichaaelCarmichael (1914) p.40</ref>}}

This implies that the order of every element of the multiplicative group of integers modulo {{mvar | n}} divides {{math | ''λ''(''n'')}}. Carmichael calls an element {{mvar | a}} for which <math>a^{\lambda(n)}</math> is the least power of {{mvar | a}} congruent to 1 (mod {{mvar | n}}) a ''primitive λ-root modulo n''.<ref>Carmichael (1914) p.54</ref> (This is not to be confused with a [[primitive root modulo n|primitive root modulo {{mvar | n}}]], which Carmichael sometimes refers to as a primitive <math>\varphi</math>-root modulo {{mvar | n}}.)

{{Math theorem |name=Theorem 2|math_statement=For every positive integer {{mvar | n}} there exists a primitive {{mvar | λ}}-root modulo {{mvar | n}}. Moreover, if {{mvar | g}} is such a root, then there are <math>\varphi(\lambda(n))</math> primitive {{mvar | λ}}-roots that are congruent to powers of {{mvar | g}}.<ref>Carmichael (1914) p.55</ref>}}

Line 243 ⟶ 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