Content deleted Content added
Will Orrick (talk | contribs) Compress and consolidate the material on computing lambda to try to make it more accessible. Then expand on what Carmichael proved about these expressions, mentioning his notion of primitive lambda-roots. Remove some now-redundant sections. |
Will Orrick (talk | contribs) Incorporate notion of primitive lambda-root into the introduction and numerical examples. Give more accurate title to subsection "Minimality". Slightly elaborate proof in subsection "Divisibility". Small wording changes and typo corrections, |
||
Line 3:
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}}'''.
The Carmichael function is named after the American mathematician [[Robert Daniel Carmichael|Robert Carmichael]] who defined it in 1910.<ref>
Line 59:
==Numerical examples==
# Carmichael's function at 5 is 4, {{math | ''λ''(5) {{=}} 4}}, because for any number <math>0<a<5</math> coprime to 5, i.e. <math>a\in \{1, 2, 3, 4\}~,</math> there is <math>a^m \equiv 1 \,(\text{mod } 5)</math> with <math>m=4,</math> namely, {{math | 1<sup>1⋅4</sup> {{=}} 1<sup>4</sup> ≡ 1 (mod 5)}}, {{math | 2<sup>4</sup> {{=}} 16 ≡ 1 (mod 5)}}, {{math | 3<sup>4</sup> {{=}} 81 ≡ 1 (mod 5)}} and {{math | 4<sup>2⋅2</sup> {{=}} 16<sup>2</sup> ≡ 1<sup>2</sup> (mod 5)}}. And this {{math | ''m'' {{=}} 4}} is the smallest exponent with this property, because <math>2^2 =4 \not\equiv 1 \,(\text{mod } 5)</math> (and <math>3^2 = 9 \not\equiv 1 \,(\text{mod } 5)</math> as well.)<br />Moreover, Euler's [[totient function]] at 5 is 4, {{math | ''φ''(5) {{=}} 4}}, because there are exactly 4 numbers less than and coprime to 5 (1, 2, 3, and 4). [[Euler's theorem]] assures that {{math | ''a''<sup>4</sup> ≡ 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 | ''λ''(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''<sup>2</sup> ≡ 1 (mod 8)}}. Namely, {{math | 1<sup>1⋅2</sup> {{=}} 1<sup>2</sup> ≡ 1 (mod 8)}}, {{math | 3<sup>2</sup> {{=}} 9 ≡ 1 (mod 8)}}, {{math | 5<sup>2</sup> {{=}} 25 ≡ 1 (mod 8)}} and {{math | 7<sup>2</sup> {{=}} 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''<sup>4</sup> ≡ 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.
== Evaluation of {{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,}\\
\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>
Line 73:
== Carmichael's theorems ==
Carmichael proved two theorems that, together, establish that if {{math | ''λ''(''n'')}} is considered as defined by the
{{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>}}
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>}}
If {{mvar | g}} is one of the primitive {{mvar | λ}}-roots guaranteed by the theorem,
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 and vice versa. 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.
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.
Line 87:
:<math>m \mid n.</math>
===A consequence of minimality of {{math | ''λ''(''n'')}}===
Suppose {{math | ''a<sup>m</sup>'' ≡ 1 (mod ''n'')}} for all numbers {{mvar | a}} coprime with {{mvar | n}}. Then {{math | ''λ''(''n'') {{!}} ''m''}}.
Line 93:
'''Proof:''' If {{math | ''m'' {{=}} ''kλ''(''n'') + ''r''}} with {{math | 0 ≤ ''r'' < ''λ''(''n'')}}, then
:<math>a^r = 1^k \cdot a^r \equiv \left(a^{\lambda(n)}\right)^k\cdot a^r = a^{k\lambda(n)+r} = a^m \equiv 1\pmod{n}</math>
for all numbers {{mvar | a}} coprime with {{mvar | n}}. It follows that {{math | 1=''r'' = 0}}
=== {{math | ''λ''(''n'')}} divides {{math | ''φ''(''n'')}} ===
Line 106:
'''Proof.'''
By definition, for any integer <math>k</math> with <math>\gcd(k,b) = 1</math> (and thus also <math>\gcd(k,a) = 1</math>), we have that <math> b \,|\, (k^{\lambda(b)} - 1)</math> , and therefore <math> a \,|\, (k^{\lambda(b)} - 1)</math>. This establishes that <math>k^{\lambda(b)}\equiv1\pmod{a}</math> for all {{mvar | k}} relatively prime to {{mvar | a}}. By the consequence of minimality
===Composition===
Line 112:
For all positive integers {{mvar | a}} and {{mvar | b}} it holds that
:<math>\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}(\lambda(a), \lambda(b))</math>.
This is an immediate consequence of the
<!--
Proof goes as follows:
| |||