Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Showing content from https://en.wikipedia.org/wiki/Carmichael_function below:

Carmichael function - Wikipedia

Function in mathematical number theory

In number theory, a branch of mathematics, the Carmichael function λ(n) of a positive integer n is the smallest positive integer m such that

a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}}

holds for every integer a coprime to n. In algebraic terms, λ(n) is the exponent of the multiplicative group of integers modulo n. As this is a finite abelian group, there must exist an element whose order equals the exponent, λ(n). Such an element is called a primitive λ-root modulo n.

The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910.^[1] 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 n is φ(n), where φ is Euler's totient function. Since the order of an element of a finite group divides the order of the group, λ(n) divides φ(n). The following table compares the first 36 values of λ(n) (sequence A002322 in the OEIS) and φ(n) (in bold if they are different; the values of n such that they are different are listed in OEIS: A033949).

• n = 5. The set of numbers less than and coprime to 5 is {1,2,3,4}. Hence Euler's totient function has value φ(5) = 4 and the value of Carmichael's function, λ(5), must be a divisor of 4. The divisor 1 does not satisfy the definition of Carmichael's function since a 1 ≢ 1 ( mod 5 ) {\displaystyle a^{1}\not \equiv 1{\pmod {5}}} except for a ≡ 1 ( mod 5 ) {\displaystyle a\equiv 1{\pmod {5}}} . Neither does 2 since 2 2 ≡ 3 2 ≡ 4 ≢ 1 ( mod 5 ) {\displaystyle 2^{2}\equiv 3^{2}\equiv 4\not \equiv 1{\pmod {5}}} . Hence λ(5) = 4. Indeed, 1 4 ≡ 2 4 ≡ 3 4 ≡ 4 4 ≡ 1 ( mod 5 ) {\displaystyle 1^{4}\equiv 2^{4}\equiv 3^{4}\equiv 4^{4}\equiv 1{\pmod {5}}} . Both 2 and 3 are primitive λ-roots modulo 5 and also primitive roots modulo 5.
• n = 8. The set of numbers less than and coprime to 8 is {1,3,5,7} . Hence φ(8) = 4 and λ(8) must be a divisor of 4. In fact λ(8) = 2 since 1 2 ≡ 3 2 ≡ 5 2 ≡ 7 2 ≡ 1 ( mod 8 ) {\displaystyle 1^{2}\equiv 3^{2}\equiv 5^{2}\equiv 7^{2}\equiv 1{\pmod {8}}} . The primitive λ-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 λ of the product is the least common multiple of the λ of the prime power factors. Specifically, λ(n) is given by the recurrence

λ ( n ) = { φ ( n ) if  n  is 1, 2, 4, or an odd prime power, 1 2 φ ( n ) if  n = 2 r ,   r ≥ 3 , lcm ⁡ ( λ ( n 1 ) , λ ( n 2 ) , … , λ ( n k ) ) if  n = n 1 n 2 … n k  where  n 1 , n 2 , … , n k  are powers of distinct primes. {\displaystyle \lambda (n)={\begin{cases}\varphi (n)&{\text{if }}n{\text{ is 1, 2, 4, or an odd prime power,}}\\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=2^{r},\ r\geq 3,\\\operatorname {lcm} {\Bigl (}\lambda (n_{1}),\lambda (n_{2}),\ldots ,\lambda (n_{k}){\Bigr )}&{\text{if }}n=n_{1}n_{2}\ldots n_{k}{\text{ where }}n_{1},n_{2},\ldots ,n_{k}{\text{ are powers of distinct primes.}}\end{cases}}}

Euler's totient for a prime power, that is, a number p^r with p prime and r ≥ 1, is given by

φ ( p r ) = p r − 1 ( p − 1 ) . {\displaystyle \varphi (p^{r}){=}p^{r-1}(p-1).}

Carmichael proved two theorems that, together, establish that if λ(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 m such that a m ≡ 1 ( mod n ) {\displaystyle a^{m}\equiv 1{\pmod {n}}} for all a relatively prime to n.

Theorem 1—If a is relatively prime to n then a λ ( n ) ≡ 1 ( mod n ) {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}} .^[2]

This implies that the order of every element of the multiplicative group of integers modulo n divides λ(n). Carmichael calls an element a for which a λ ( n ) {\displaystyle a^{\lambda (n)}} is the least power of a congruent to 1 (mod n) a primitive λ-root modulo n.^[3] (This is not to be confused with a primitive root modulo n, which Carmichael sometimes refers to as a primitive φ {\displaystyle \varphi } -root modulo n.)

Theorem 2—For every positive integer n there exists a primitive λ-root modulo n. Moreover, if g is such a root, then there are φ ( λ ( n ) ) {\displaystyle \varphi (\lambda (n))} primitive λ-roots that are congruent to powers of g.^[4]

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

The second statement of Theorem 2 does not imply that all primitive λ-roots modulo n are congruent to powers of a single root g.^[5] For example, if n = 15, then λ(n) = 4 while φ ( n ) = 8 {\displaystyle \varphi (n)=8} and φ ( λ ( n ) ) = 2 {\displaystyle \varphi (\lambda (n))=2} . There are four primitive λ-roots modulo 15, namely 2, 7, 8, and 13 as 1 ≡ 2 4 ≡ 8 4 ≡ 7 4 ≡ 13 4 {\displaystyle 1\equiv 2^{4}\equiv 8^{4}\equiv 7^{4}\equiv 13^{4}} . The roots 2 and 8 are congruent to powers of each other and the roots 7 and 13 are congruent 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 4 ≡ 2 2 ≡ 8 2 ≡ 7 2 ≡ 13 2 {\displaystyle 4\equiv 2^{2}\equiv 8^{2}\equiv 7^{2}\equiv 13^{2}} ), 11, and 14, are not primitive λ-roots modulo 15.

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

In this section, an integer n {\displaystyle n} is divisible by a nonzero integer m {\displaystyle m} if there exists an integer k {\displaystyle k} such that n = k m {\displaystyle n=km} . This is written as

m ∣ n . {\displaystyle m\mid n.}

Suppose a^m ≡ 1 (mod n) for all numbers a coprime with n. Then λ(n) | m.

Proof: If m = kλ(n) + r with 0 ≤ r < λ(n), then

a r = 1 k ⋅ a r ≡ ( a λ ( n ) ) k ⋅ a r = a k λ ( n ) + r = a m ≡ 1 ( mod n ) {\displaystyle 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}}}

for all numbers a coprime with n. It follows that r = 0 since r < λ(n) and λ(n) is the minimal positive exponent for which the congruence holds for all a coprime with n.

This follows from elementary group theory, because the exponent of any finite group must divide the order of the group. λ(n) is the exponent of the multiplicative group of integers modulo n while φ(n) is the order of that group. In particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a primitive root, which is the case for odd prime powers.

We can thus view Carmichael's theorem as a sharpening of Euler's theorem.

a | b ⇒ λ ( a ) | λ ( b ) {\displaystyle a\,|\,b\Rightarrow \lambda (a)\,|\,\lambda (b)}

Proof.

By definition, for any integer k {\displaystyle k} with gcd ( k , b ) = 1 {\displaystyle \gcd(k,b)=1} (and thus also gcd ( k , a ) = 1 {\displaystyle \gcd(k,a)=1} ), we have that b | ( k λ ( b ) − 1 ) {\displaystyle b\,|\,(k^{\lambda (b)}-1)} , and therefore a | ( k λ ( b ) − 1 ) {\displaystyle a\,|\,(k^{\lambda (b)}-1)} . This establishes that k λ ( b ) ≡ 1 ( mod a ) {\displaystyle k^{\lambda (b)}\equiv 1{\pmod {a}}} for all k relatively prime to a. By the consequence of minimality proved above, we have λ ( a ) | λ ( b ) {\displaystyle \lambda (a)\,|\,\lambda (b)} .

For all positive integers a and b it holds that

λ ( l c m ( a , b ) ) = l c m ( λ ( a ) , λ ( b ) ) {\displaystyle \lambda (\mathrm {lcm} (a,b))=\mathrm {lcm} (\lambda (a),\lambda (b))} .

This is an immediate consequence of the recurrence for the Carmichael function.

If r m a x = max i { r i } {\displaystyle r_{\mathrm {max} }=\max _{i}\{r_{i}\}} is the biggest exponent in the prime factorization n = p 1 r 1 p 2 r 2 ⋯ p k r k {\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}} of n, then for all a (including those not coprime to n) and all r ≥ r_max,

a r ≡ a λ ( n ) + r ( mod n ) . {\displaystyle a^{r}\equiv a^{\lambda (n)+r}{\pmod {n}}.}

In particular, for square-free n ( r_max = 1), for all a we have

a ≡ a λ ( n ) + 1 ( mod n ) . {\displaystyle a\equiv a^{\lambda (n)+1}{\pmod {n}}.}

For any n ≥ 16:^[6][7]

1 n ∑ i ≤ n λ ( i ) = n ln ⁡ n e B ( 1 + o ( 1 ) ) ln ⁡ ln ⁡ n / ( ln ⁡ ln ⁡ ln ⁡ n ) {\displaystyle {\frac {1}{n}}\sum _{i\leq n}\lambda (i)={\frac {n}{\ln n}}e^{B(1+o(1))\ln \ln n/(\ln \ln \ln n)}}

(called Erdős approximation in the following) with the constant

B := e − γ ∏ p ∈ P ( 1 − 1 ( p − 1 ) 2 ( p + 1 ) ) ≈ 0.34537 {\displaystyle B:=e^{-\gamma }\prod _{p\in \mathbb {P} }\left({1-{\frac {1}{(p-1)^{2}(p+1)}}}\right)\approx 0.34537}

and γ ≈ 0.57721, the Euler–Mascheroni constant.

The following table gives some overview over the first 2²⁶ – 1 = 67108863 values of the λ function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible “logarithm over logarithm” values LoL(n) := ⁠ln λ(n)/ln n⁠ with

• LoL(n) > ⁠4/5⁠ ⇔ λ(n) > n^⁠4/5⁠.

There, the table entry in row number 26 at column

•  % LoL > ⁠4/5⁠   → 60.49

indicates that 60.49% (≈ 40000000) of the integers 1 ≤ n ≤ 67108863 have λ(n) > n^⁠4/5⁠ meaning that the majority of the λ values is exponential in the length l := log₂(n) of the input n, namely

( 2 4 5 ) l = 2 4 l 5 = ( 2 l ) 4 5 = n 4 5 . {\displaystyle \left(2^{\frac {4}{5}}\right)^{l}=2^{\frac {4l}{5}}=\left(2^{l}\right)^{\frac {4}{5}}=n^{\frac {4}{5}}.}

For all numbers N and all but o(N)^[8] positive integers n ≤ N (a "prevailing" majority):

λ ( n ) = n ( ln ⁡ n ) ln ⁡ ln ⁡ ln ⁡ n + A + o ( 1 ) {\displaystyle \lambda (n)={\frac {n}{(\ln n)^{\ln \ln \ln n+A+o(1)}}}}

with the constant^[7]

A := − 1 + ∑ p ∈ P ln ⁡ p ( p − 1 ) 2 ≈ 0.2269688 {\displaystyle A:=-1+\sum _{p\in \mathbb {P} }{\frac {\ln p}{(p-1)^{2}}}\approx 0.2269688}

For any sufficiently large number N and for any Δ ≥ (ln ln N)³, there are at most

N exp ⁡ ( − 0.69 ( Δ ln ⁡ Δ ) 1 3 ) {\displaystyle N\exp \left(-0.69(\Delta \ln \Delta )^{\frac {1}{3}}\right)}

positive integers n ≤ N such that λ(n) ≤ ne^−Δ.^[9]

For any sequence n₁ < n₂ < n₃ < ⋯ of positive integers, any constant 0 < c < ⁠1/ln 2⁠, and any sufficiently large i:^[10][11]

λ ( n i ) > ( ln ⁡ n i ) c ln ⁡ ln ⁡ ln ⁡ n i . {\displaystyle \lambda (n_{i})>\left(\ln n_{i}\right)^{c\ln \ln \ln n_{i}}.}

For a constant c and any sufficiently large positive A, there exists an integer n > A such that^[11]

λ ( n ) < ( ln ⁡ A ) c ln ⁡ ln ⁡ ln ⁡ A . {\displaystyle \lambda (n)<\left(\ln A\right)^{c\ln \ln \ln A}.}

Moreover, n is of the form

n = ∏ q ∈ P ( q − 1 ) | m ⁡ q {\displaystyle n=\mathop {\prod _{q\in \mathbb {P} }} _{(q-1)|m}q}

for some square-free integer m < (ln A)^{c ln ln ln A}.^[10]

The set of values of the Carmichael function has counting function^[12]

x ( ln ⁡ x ) η + o ( 1 ) , {\displaystyle {\frac {x}{(\ln x)^{\eta +o(1)}}},}

where

η = 1 − 1 + ln ⁡ ln ⁡ 2 ln ⁡ 2 ≈ 0.08607 {\displaystyle \eta =1-{\frac {1+\ln \ln 2}{\ln 2}}\approx 0.08607}

The Carmichael function is important in cryptography due to its use in the RSA encryption algorithm.

For n = p, a prime, Theorem 1 is equivalent to Fermat's little theorem:

a p − 1 ≡ 1 ( mod p ) for all  a  coprime to  p . {\displaystyle a^{p-1}\equiv 1{\pmod {p}}\qquad {\text{for all }}a{\text{ coprime to }}p.}

For prime powers p^r, r > 1, if

a p r − 1 ( p − 1 ) = 1 + h p r {\displaystyle a^{p^{r-1}(p-1)}=1+hp^{r}}

holds for some integer h, then raising both sides to the power p gives

a p r ( p − 1 ) = 1 + h ′ p r + 1 {\displaystyle a^{p^{r}(p-1)}=1+h'p^{r+1}}

for some other integer h ′ {\displaystyle h'} . By induction it follows that a φ ( p r ) ≡ 1 ( mod p r ) {\displaystyle a^{\varphi (p^{r})}\equiv 1{\pmod {p^{r}}}} for all a relatively prime to p and hence to p^r. This establishes the theorem for n = 4 or any odd prime power.

For a coprime to (powers of) 2 we have a = 1 + 2h₂ for some integer h₂. Then,

a 2 = 1 + 4 h 2 ( h 2 + 1 ) = 1 + 8 ( h 2 + 1 2 ) =: 1 + 8 h 3 {\displaystyle a^{2}=1+4h_{2}(h_{2}+1)=1+8{\binom {h_{2}+1}{2}}=:1+8h_{3}} ,

where h 3 {\displaystyle h_{3}} is an integer. With r = 3, this is written

a 2 r − 2 = 1 + 2 r h r . {\displaystyle a^{2^{r-2}}=1+2^{r}h_{r}.}

Squaring both sides gives

a 2 r − 1 = ( 1 + 2 r h r ) 2 = 1 + 2 r + 1 ( h r + 2 r − 1 h r 2 ) =: 1 + 2 r + 1 h r + 1 , {\displaystyle a^{2^{r-1}}=\left(1+2^{r}h_{r}\right)^{2}=1+2^{r+1}\left(h_{r}+2^{r-1}h_{r}^{2}\right)=:1+2^{r+1}h_{r+1},}

where h r + 1 {\displaystyle h_{r+1}} is an integer. It follows by induction that

a 2 r − 2 = a 1 2 φ ( 2 r ) ≡ 1 ( mod 2 r ) {\displaystyle a^{2^{r-2}}=a^{{\frac {1}{2}}\varphi (2^{r})}\equiv 1{\pmod {2^{r}}}}

for all r ≥ 3 {\displaystyle r\geq 3} and all a coprime to 2 r {\displaystyle 2^{r}} .^[13]

By the unique factorization theorem, any n > 1 can be written in a unique way as

n = p 1 r 1 p 2 r 2 ⋯ p k r k {\displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}\cdots p_{k}^{r_{k}}}

where p₁ < p₂ < ... < p_k are primes and r₁, r₂, ..., r_k are positive integers. The results for prime powers establish that, for 1 ≤ j ≤ k {\displaystyle 1\leq j\leq k} ,

a λ ( p j r j ) ≡ 1 ( mod p j r j ) for all  a  coprime to  n  and hence to  p i r i . {\displaystyle a^{\lambda \left(p_{j}^{r_{j}}\right)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n{\text{ and hence to }}p_{i}^{r_{i}}.}

From this it follows that

a λ ( n ) ≡ 1 ( mod p j r j ) for all  a  coprime to  n , {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {p_{j}^{r_{j}}}}\qquad {\text{for all }}a{\text{ coprime to }}n,}

where, as given by the recurrence,

λ ( n ) = lcm ⁡ ( λ ( p 1 r 1 ) , λ ( p 2 r 2 ) , … , λ ( p k r k ) ) . {\displaystyle \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 )}.}

From the Chinese remainder theorem one concludes that

a λ ( n ) ≡ 1 ( mod n ) for all  a  coprime to  n . {\displaystyle a^{\lambda (n)}\equiv 1{\pmod {n}}\qquad {\text{for all }}a{\text{ coprime to }}n.}

• Carmichael number

1. ^ Carmichael, Robert Daniel (1910). "Note on a new number theory function". Bulletin of the American Mathematical Society. 16 (5): 232–238. doi:10.1090/S0002-9904-1910-01892-9.
2. ^ Carmichael (1914) p.40
3. ^ Carmichael (1914) p.54
4. ^ Carmichael (1914) p.55
5. ^ Carmichael (1914) p.56
6. ^ Theorem 3 in Erdős (1991)
7. ^ ^{a b} Sándor & Crstici (2004) p.194
8. ^ Theorem 2 in Erdős (1991) 3. Normal order. (p.365)
9. ^ Theorem 5 in Friedlander (2001)
10. ^ ^{a b} Theorem 1 in Erdős (1991)
11. ^ ^{a b} Sándor & Crstici (2004) p.193
12. ^ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". Algebra & Number Theory. 8 (8): 2009–2026. arXiv:1408.6506. doi:10.2140/ant.2014.8.2009. S2CID 50397623.
13. ^ Carmichael (1914) pp.38–39

• Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica. 58 (4): 363–385. doi:10.4064/aa-58-4-363-385. ISSN 0065-1036. MR 1121092. Zbl 0734.11047.
• Friedlander, John B.; Pomerance, Carl; Shparlinski, Igor E. (2001). "Period of the power generator and small values of the Carmichael function". Mathematics of Computation. 70 (236): 1591–1605, 1803–1806. doi:10.1090/s0025-5718-00-01282-5. ISSN 0025-5718. MR 1836921. Zbl 1029.11043.
• Sándor, Jozsef; Crstici, Borislav (2004). Handbook of number theory II. Dordrecht: Kluwer Academic. pp. 32–36, 193–195. ISBN 978-1-4020-2546-4. Zbl 1079.11001.
• Carmichael, Robert D. [1914]. The Theory of Numbers at Project Gutenberg

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4