Carmichael function: Difference between revisions

Revision as of 05:28, 9 March 2024

Latest revision as of 01:52, 8 August 2025

(11 intermediate revisions by 9 users not shown)

Line 1:

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

In [[File:carmichaelLambda.svg|thumb|upright=2|Carmichaelnumber {{mvartheory]], |a λ}}branch of [[mathematics]], the '''Carmichael function:''' {{math | ''λ''(''n'')}} forof a [[positive integer]] {{mathmvar | 1 ≤ ''n'' ≤ 1000}} (comparedis tothe Eulersmallest positive integer {{mvar | φm}} function)]]such that

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}} with [[Euler's totient function]]and {{mvarmath | ''φ''(''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==

# Carmichael's function at 5 is 4,* {{math | ''λn''(5) {{=}} 45}},. becauseThe forset anyof numbernumbers <math>0<a<5</math>less than and coprime to 5, i.e.is <{{math>a\in \| {1, 2, 3, 4\}~,</math>}}. thereHence isEuler's <math>a^mtotient \equivfunction 1has \,(\text{mod } 5)</math> with <math>m=4,</math> namely,value {{math | 1^1⋅4''φ''(5) {{=}} 1⁴ ≡ 1 (mod 5)}}, {{mathand |the 2⁴value {{=}}of 16Carmichael's ≡ 1 (mod 5)}}function, {{math | 3⁴ {{=}} 81 ≡ 1 ''λ''(mod 5)}}, andmust {{mathbe |a 4^2⋅2[[divisor]] {{=}}of 16² ≡ 1² (mod 5)}}4. The Anddivisor this1 {{mathdoes |not ''m'' {{=}} 4}} issatisfy the smallestdefinition exponentof withCarmichael's thisfunction property, becausesince <math>2a^2 =41 \not\equiv 1\pmod{5}</math> except for <math>a\,(equiv1\textpmod{mod } 5)}</math>. (andNeither does 2 since <math>2^2 \equiv 3^2 =\equiv 94 \not\equiv 1 \,(\textpmod{mod 5} 5)</math> as well.)<br />Moreover, Euler's [[totient function]] at 5 is 4,Hence {{math | ''φλ''(5) {{=}} 4}}. Indeed, because there are exactly <math>1^4 numbers less than and coprime to 5 (1,\equiv 2,^4\equiv 3, and^4\equiv 4). [[Euler's theorem]] assures that ^4\equiv1\pmod{{math | ''a''<sup>45}</supmath> ≡ 1 (mod 5)}} for all {{mvar | a}} coprime to 5, and 4 is the smallest such exponent. Both 2 and 3 are primitive {{mvar | λ}}-roots modulo 5 and also [[Primitive root modulo n|primitive roots]] modulo 5.

# Carmichael's function at 8 is 2,* {{math | ''λn''(8) {{=}} 28}},. becauseThe forset anyof numbernumbers {{mvarless |than a}}and coprime to 8, i.e.is <{{math>a\in \| {1, 3, 5, 7\}~,</math> it holds}}. thatHence {{math | ''aφ''² ≡ 1 (mod 8)}}. Namely, {{math | 1^1⋅2 {{=}} 1² ≡ 1 (mod 8)4}}, {{math | 3² {{=}} 9 ≡ 1 (mod 8)}},and {{math | 5² {{=}} 25 ≡ 1 ''λ''(mod 8)}} andmust {{mathbe |a 7²divisor {{=}}of 49 ≡ 1 (mod 8)}}4.<br />Euler'sIn [[totient function]] at 8 is 4,fact {{math | ''φλ''(8) {{=}} 42}}, becausesince there are exactly 4 numbers less than and coprime to 8 (<math>1,^2\equiv 3,^2\equiv 5, and^2\equiv 7). Moreover, [[Euler's theorem]] assures that ^2\equiv1\pmod{{math | ''a''<sup>48}</supmath> ≡ 1 (mod 8)}} for all {{mvar | a}} coprime to 8, but 4 is not the smallest such exponent. 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 73 ⟶ 74:

== Carmichael's theorems ==

{{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 242 ⟶ 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