Carmichael function

In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that : a^m \equiv 1 \pmod{n} holds for every integer coprime to . In algebraic terms, is the exponent of the multiplicative group of integers modulo . As this is a finite abelian group, there must exist an element whose order equals the exponent, . Such an element is called a primitive -root modulo . The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910. 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 is , where is Euler's totient function. Since the order of an element of a finite group divides the order of the group, divides . The following table compares the first 36 values of and (in bold if they are different; the values of such that they are different are listed in ).

In number theory, a branch of mathematics, the Carmichael function of a positive integer is the smallest positive integer such that a^m \equiv 1 \pmod{n} holds for every integer coprime to . In algebraic terms, is the exponent of the multiplicative group of integers modulo . As this is a finite abelian group, there must exist an element whose order equals the exponent, . Such an element is called a primitive -root modulo . The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910. 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 is , where is Euler's totient function. Since the order of an element of a finite group divides the order of the group, divides . The following table compares the first 36 values of and (in bold if they are different; the values of such that they are different are listed in ). ==Numerical examples== . The set of numbers less than and coprime to 5 is . Hence Euler's totient function has value and the value of Carmichael's function, , must be a divisor of 4. The divisor 1 does not satisfy the definition of Carmichael's function since a^1 \not\equiv 1\pmod{5} except for a\equiv1\pmod{5} . Neither does 2 since 2^2 \equiv 3^2 \equiv 4 \not\equiv 1\pmod{5} . Hence . Indeed, 1^4\equiv 2^4\equiv 3^4\equiv 4^4\equiv1\pmod{5} . Both 2 and 3 are primitive -roots modulo 5 and also primitive roots modulo 5. . The set of numbers less than and coprime to 8 is . Hence and must be a divisor of 4. In fact since 1^2\equiv 3^2\equiv 5^2\equiv 7^2\equiv1\pmod{8} . The primitive -roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8. \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} Euler's totient for a prime power, that is, a number with prime and , is given by \varphi(p^r) p^{r-1}(p-1). The second statement of Theorem 2 does not imply that all primitive -roots modulo are congruent to powers of a single root . For example, if , then while \varphi(n)=8 and \varphi(\lambda(n))=2 . There are four primitive -roots modulo 15, namely 2, 7, 8, and 13 as 1\equiv2^4\equiv8^4\equiv7^4\equiv13^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\equiv2^2\equiv8^2\equiv7^2\equiv13^2 ), 11, and 14, are not primitive -roots modulo 15. For a contrasting example, if , then \lambda(n)=\varphi(n)=6 and \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 \varphi -roots modulo 9. The numbers of primitive -roots modulo for n=1,2,3,\cdots are 1, 1, 1, 1, 2, 1, 2, 3, 2, 2, 4, 3, 4, 2, 4, 4, 8, 2, 6, 4, 6, 4, 10, 7, 8, 4, 6, 6, 12, 4, 8, 8, 12, 8, 8, 6, 12, 6, 8, 8, 16, 6, 12, 12, 8, 10, 22, 8, 12, 8, ... ==Properties of the Carmichael function== In this section, an integer n is divisible by a nonzero integer m if there exists an integer k such that n = km . This is written as m \mid n. 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 coprime with . It follows that since and is the minimal positive exponent for which the congruence holds for all coprime with . ===Divisibility=== a\,|\,b \Rightarrow \lambda(a)\,|\,\lambda(b) Proof. By definition, for any integer k with \gcd(k,b) = 1 (and thus also \gcd(k,a) = 1 ), we have that b \,|\, (k^{\lambda(b)} - 1) , and therefore a \,|\, (k^{\lambda(b)} - 1) . This establishes that k^{\lambda(b)}\equiv1\pmod{a} for all relatively prime to . By the consequence of minimality proved above, we have \lambda(a)\,|\,\lambda(b) . ===Composition=== For all positive integers and it holds that \lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}(\lambda(a), \lambda(b)) . This is an immediate consequence of the recurrence for the Carmichael function. ===Exponential cycle length=== If r_{\mathrm{max}}=\max_i\{r_i\} is the biggest exponent in the prime factorization n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} of , then for all (including those not coprime to ) and all , a^r \equiv a^{\lambda(n)+r} \pmod n. In particular, for square-free ( ), for all we have a \equiv a^{\lambda(n)+1} \pmod n. ===Average value=== For any : \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^{-\gamma} \prod_{p\in\mathbb P} \left({1 - \frac{1}{(p-1)^2(p+1)}}\right) \approx 0.34537 and , the Euler–Mascheroni constant. The following table gives some overview over the first values of the function, for both, the exact average and its Erdős-approximation. Additionally given is some overview over the more easily accessible with . There, the table entry in row number 26 at column → 60.49 indicates that 60.49% (≈ ) of the integers have meaning that the majority of the values is exponential in the length of the input , namely \left(2^\frac45\right)^l = 2^\frac{4l}{5} = \left(2^l\right)^\frac45 = n^\frac45. ===Prevailing interval=== For all numbers and all but positive integers (a "prevailing" majority): \lambda(n) = \frac{n} {(\ln n)^{\ln\ln\ln n + A + o(1)}} with the constant A := -1 + \sum_{p\in\mathbb P} \frac{\ln p}{(p-1)^2} \approx 0.2269688 ===Lower bounds=== For any sufficiently large number and for any , there are at most N\exp\left(-0.69(\Delta\ln\Delta)^\frac13\right) positive integers such that . ===Minimal order=== For any sequence of positive integers, any constant , and any sufficiently large : \lambda(n_i) > \left(\ln n_i\right)^{c\ln\ln\ln n_i}. ===Small values=== For a constant and any sufficiently large positive , there exists an integer such that \lambda(n) Moreover, is of the form n=\mathop{\prod_{q \in \mathbb P}}_{(q-1)|m}q for some square-free integer . ===Image of the function=== The set of values of the Carmichael function has counting function \frac{x}{(\ln x)^{\eta+o(1)}} , where \eta=1-\frac{1+\ln\ln2}{\ln2} \approx 0.08607 ==Use in cryptography== The Carmichael function is important in cryptography due to its use in the RSA encryption algorithm. ==Proof of Theorem 1== For , a prime, Theorem 1 is equivalent to Fermat's little theorem: a^{p-1}\equiv1\pmod{p}\qquad\text{for all }a\text{ coprime to }p. For prime powers , , if a^{p^{r-1}(p-1)}=1+hp^r holds for some integer , then raising both sides to the power gives a^{p^r(p-1)}=1+h'p^{r+1} for some other integer h' . By induction it follows that a^{\varphi(p^r)}\equiv1\pmod{p^r} for all relatively prime to and hence to . This establishes the theorem for or any odd prime power. ===Sharpening the result for higher powers of two=== For coprime to (powers of) 2 we have for some integer . Then, a^2 = 1+4h_2(h_2+1) = 1+8\binom{h_2+1}{2}=:1+8h_3 , where h_3 is an integer. With , this is written a^{2^{r-2}} = 1+2^r h_r. Squaring both sides gives 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} is an integer. It follows by induction that a^{2^{r-2}}=a^{\frac{1}{2}\varphi(2^r)}\equiv 1\pmod{2^r} for all r\ge3 and all coprime to 2^r . ===Integers with multiple prime factors=== By the unique factorization theorem, any can be written in a unique way as n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} where are primes and are positive integers. The results for prime powers establish that, for 1\le j\le k , 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}. From this it follows that a^{\lambda(n)}\equiv1 \pmod{p_j^{r_j}}\qquad\text{for all }a\text{ coprime to }n, where, as given by the recurrence, \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^{\lambda(n)}\equiv1 \pmod{n}\qquad\text{for all }a\text{ coprime to }n. ==See also== Carmichael number ==Notes== ==References==

Text derived from https://en.wikipedia.org/w/index.php?oldid=1375769222 under CC BY-SA 4.0; modifications have been made.