Content deleted Content added
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, |
Will Orrick (talk | contribs) "Extension for powers of two" is a misleading section heading and out of place, as this section proves a core part of Theorem 1, and is not an extension of anything. I've renamed and moved this, and provided the rest of the proof of Theorem 1. |
||
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''<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.
==
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 136:
:<math>a \equiv a^{\lambda(n)+1} \pmod n.</math>
===Extension for powers of two===▼
For {{mvar | a}} coprime to (powers of) 2 we have {{math | ''a'' {{=}} 1 + 2''h''}} for some {{mvar | h}}. Then,▼
:<math>a^2 = 1+4h(h+1) = 1+8C</math>▼
a^{2^{k-1}}&=\left(1+2^k h\right)^2=1+2^{k+1}\left(h+2^{k-1}h^2\right)▼
:<math>a^{2^{k-2}}\equiv 1\pmod{2^k}.</math>▼
===Average value===
Line 259 ⟶ 240:
The Carmichael function is important in [[cryptography]] due to its use in the [[RSA (cryptosystem)|RSA encryption algorithm]].
==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
holds for some integer {{mvar | h}}, then raising both sides to the power {{mvar | p}} gives
:<math>a^{p^r(p-1)}=1+h'p^{r+1}</math>
for some other integer <math>h'</math>. By induction it follows that <math>a^{\varphi(p^r)}\equiv1\pmod{p^r}</math> for all {{mvar | a}} relatively prime to {{mvar | p}} and hence to {{math | ''p''<sup>''r''</sup>}}. This establishes the theorem for {{math | ''n'' {{=}} 4}} or any odd prime power.
▲For {{mvar | a}} coprime to (powers of) 2 we have {{math | ''a'' {{=}} 1 + 2''h''<sub>2</sub>}} for some integer {{
:<math>a^2 = 1+4h_2(h_2+1) = 1+8\binom{h_2+1}{2}=:1+8h_3</math>,
where <math>h_3</math> is an integer. With {{math | 1=''r'' = 3}}, this is written
Squaring both sides gives
▲:<math>a^{2^{
where <math>h_{r+1}</math> is an integer. It follows by induction that
:<math>a^{2^{r-2}}=a^{\frac{1}{2}\varphi(2^r)}\equiv 1\pmod{2^r}</math>
for all <math>r\ge3</math> and all {{mvar | a}} coprime to <math>2^r</math>.<ref>Carmichael (1914) pp.38–39</ref>
===Integers with multiple prime factors===
By the [[unique factorization theorem]], any {{math | ''n'' > 1}} can be written in a unique way as
:<math> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math>
where {{math | ''p''<sub>1</sub> < ''p''<sub>2</sub> < ... < ''p<sub>k</sub>''}} are primes and {{math | ''r''<sub>1</sub>, ''r''<sub>2</sub>, ..., ''r<sub>k</sub>''}} are positive integers. The results for prime powers establish that, for <math>1\le j\le k</math>,
:<math>a^{\lambda\left(p_j^{r_j}\right)}\equiv1 \pmod{p_j^{r_j}}\qquad\text{for all }a\text{ coprime to }n\text{ and hence to }p_i^{r_i}.</math>
From this it follows that
:<math>a^{\lambda(n)}\equiv1 \pmod{p_j^{r_j}}\qquad\text{for all }a\text{ coprime to }n,</math>
where, as given by the recurrence,
:<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>
From the [[Chinese remainder theorem]] one concludes that
:<math>a^{\lambda(n)}\equiv1 \pmod{n}\qquad\text{for all }a\text{ coprime to }n.</math>
==See also==
| |||