Content deleted Content added
m avoid bad wrapping |
Owen Reich (talk | contribs) Link suggestions feature: 3 links added. |
||
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''<sup>''r''</sup>}}, {{math | ''r'' > 1}}, if
| |||