Carmichael function: Difference between revisions

Revision as of 02:17, 13 November 2023

Revision as of 04:31, 13 November 2023

Line 62:

# Carmichael's function at 8 is 2, {{math | ''λ''(8) {{=}} 2}}, because for any number {{mvar | a}} coprime to 8, i.e. <math>a\in \{1, 3, 5, 7\}~,</math> it holds that {{math | ''a''² ≡ 1 (mod 8)}}. Namely, {{math | 1^1⋅2 {{=}} 1² ≡ 1 (mod 8)}}, {{math | 3² {{=}} 9 ≡ 1 (mod 8)}}, {{math | 5² {{=}} 25 ≡ 1 (mod 8)}} and {{math | 7² {{=}} 49 ≡ 1 (mod 8)}}.<br />Euler's [[totient function]] at 8 is 4, {{math | ''φ''(8) {{=}} 4}}, because there are exactly 4 numbers less than and coprime to 8 (1, 3, 5, and 7). Moreover, [[Euler's theorem]] assures that {{math | ''a''⁴ ≡ 1 (mod 8)}} for all {{mvar | a}} coprime to 8, but 4 is not the smallest such exponent.

== ComputingEvaluation of {{math | ''λ''(''n'')}} with Carmichael's theorem ==

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

:<math>\lambda(p^rn) = \begin{cases}

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

\tfrac12\varphi(n) & \text{if }n=2^r,\ r\ge3\\

\operatorname{lcm}\Bigl(\lambda(n_1),\lambda(n_2),\ldots,\lambda(n_k)\Bigr) & \text{if }n=n_1n_2\ldots n_k\text{ where }n_1,n_2,\ldots,n_k\text{ are powers of distinct primes.}

\end{cases}</math>

Euler's functiontotient for a prime powerspower, that is, a number {{math | ''p''^''r''}} with {{math | ''p''}} prime and {{math | ''r'' ≥ 1}}, is given by

:<math>\varphi(p^r) {{=}} p^{r-1}(p-1).</math>

== Carmichael's theorems ==

By the [[unique factorization theorem]], any {{math | ''n'' > 1}} can be written in a unique way as

Carmichael proved two theorems that, together, establish that if {{math | ''λ''(''n'')}} is considered as defined by the expressions in 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> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math>

{{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>Carmichaael (1914) p.40</ref>}}

where {{math | ''p''₁ < ''p''₂ < ... < ''p_k''}} are [[Prime number|prime]]s and {{math | ''r''₁, ''r''₂, ..., ''r_k''}} are positive integers. Then {{math | ''λ''(''n'')}} is the [[least common multiple]] of the {{mvar | λ}} of each of its prime power factors:

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>\lambda(n) = \operatorname{lcm}\Bigl(\lambda\left(p_1^{r_1}\right),\lambda\left(p_2^{r_2}\right),\ldots,\lambda\left(p_k^{r_k}\right)\Bigr).</math>

{{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>}}

This can be proved using the [[Chinese remainder theorem]].

If {{mvar | g}} is one of the primitive {{mvar | λ}}-roots guaranteed by the theorem, the <math>g^m\equiv1\pmod{n}</math> has no positive integer solutions {{mvar | m}} less than {{math | ''λ''(''n'')}}, showing that there is no positive {{math | ''m'' < ''λ''(''n'')}} such that <math>a^m\equiv 1\pmod{n}</math> for all {{mvar | a}} relatively prime to {{mvar | n}}.

The second statement of Theorem 2 does not imply that all primitive {{mvar | λ}}-roots modulo {{mvar | n}} are congruent to powers of a single root {{mvar | g}}.<ref>Carmichael (1914) p.56</ref> For example, if {{math | ''n'' {{=}} 15}}, then {{math | ''λ''(''n'') {{=}} 4}} while <math>\varphi(n)=8</math> and <math>\varphi(\lambda(n))=2</math>. There are four primitive {{mvar | λ}}-roots modulo 15, namely 2, 7, 8, and 13 as <math>1\equiv2^4\equiv8^4\equiv7^4\equiv13^4</math>. The roots 2 and 8 are congruent to powers of each other and the roots 7 and 13 are congruent t to powers of each other, but neither 7 nor 13 is congruent to a power of 2 or 8. The other four elements of the multiplicative group modulo 15, namely 1, 4 (which satisfies <math>4\equiv2^2\equiv8^2\equiv7^2\equiv13^2</math>), 11, and 14, are not primitive {{mvar | λ}}-roots modulo 15.

'''Carmichael's theorem''' explains how to compute {{mvar | λ}} of a prime power {{math | ''p''^''r''}}: for a power of an odd prime and for 2 and 4, {{math | ''λ''(''p''^''r'')}} is equal to the [[Euler totient]] {{math | ''φ''(''p''^''r'')}}; for powers of 2 greater than 4 it is equal to half of the Euler totient:

For a contrasting example, if {{math | ''n'' {{=}} 9}}, then <math>\lambda(n)=\varphi(n)=6</math> and <math>\varphi(\lambda(n))=2</math>. There are two primitive {{mvar | λ}}-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other. They are also both primitive <math>\varphi</math>-roots modulo 9.

:<math>\lambda(p^r) = \begin{cases}

\tfrac12\varphi\left(p^r\right)&\text{if }p=2\land r\geq 3 \;(\mbox{i.e. }p^r = 8,16,32,64,128,256,\dots)\\

\varphi\left(p^r\right) &\mbox{otherwise}\;(\mbox{i.e. }p^r = 2,4,3^r,5^r,7^r,11^r,13^r,17^r,19^r,23^r,29^r,31^r,\dots)

\end{cases}</math>

Euler's function for prime powers {{math | ''p''^''r''}} is given by

:<math>\varphi(p^r) = p^{r-1}(p-1).</math>

==Properties of the Carmichael function==

In this section, an [[integer]] <math>n</math> is divisible by a nonzero integer <math>m</math> if there exists an integer <math>k</math> such that <math>n = km</math>. This is written as

:<math>m \mid n.</math>

===Order of elements modulo ''{{mvar | n}}''===

Let {{mvar | a}} and {{mvar | n}} be [[coprime]] and let {{mvar | m}} be the smallest exponent with {{math | ''a^m'' ≡ 1 (mod ''n'')}}, then it holds that

:<math>m \,|\, \lambda(n)</math>.

That is, the [[Multiplicative order|order]] {{mvar | m :{{=}} ord_''n''(''a'')}} of a [[unit (ring theory)|unit]] {{mvar | a}} in the ring of integers modulo {{mvar | n}} divides {{math | ''λ''(''n'')}} and

:<math> \lambda(n) = \max\{\operatorname{ord}_n(a) \, \colon \, \gcd(a,n)=1\}</math>

===Minimality===