{"history":[],"article":{"id":"d83af5dc-9d41-40d2-84a8-f0aa49aeccdd","title":"Carmichael function","slug":"carmichael-function","content":":::summary\n:::\n\n# \n[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael λ function:\nλ(n)\nfor\n1 ≤ n ≤ 1000\n(compared to Euler φ function)]]\nIn [number theory](https://bliptext.com/articles/number-theory), a branch of [mathematics](https://bliptext.com/articles/mathematics), the **Carmichael function**\nλ(n)\nof a [positive integer](https://bliptext.com/articles/positive-integer) n is the smallest [positive integer](https://bliptext.com/articles/positive-integer) m such that\nholds for every integer a [coprime](https://bliptext.com/articles/coprime) to n. In algebraic terms,\nλ(n)\nis the [exponent](https://bliptext.com/articles/exponent-of-a-group) of the [multiplicative group of integers modulo n](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n).\nAs this is a [finite abelian group](https://bliptext.com/articles/abelian-group), there must exist an element whose [order](https://bliptext.com/articles/cyclic-group) equals the exponent,\nλ(n)\n. Such an element is called a '''primitive\nλ\n-root modulo n'''.\nThe Carmichael function is named after the American mathematician [Robert Carmichael](https://bliptext.com/articles/robert-daniel-carmichael) who defined it in 1910.\nIt is also known as **Carmichael's λ function**, the **reduced totient function**, and the **least universal exponent function**.\nThe order of the multiplicative group of integers modulo n is\nφ(n)\n, where φ is [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function).\nSince the order of an element of a finite group divides the order of the group,\nλ(n)\ndivides\nφ(n)\n. The following table compares the first 36 values of\nλ(n)\nand\nφ(n)\n(in **bold** if they are different; the ns such that they are different are listed in ).\n\n# Numerical examples\n. The set of numbers less than and coprime to 5 is\n{1,2,3,4}\n. Hence Euler's totient function has value\nand the value of Carmichael's function,\nλ(5)\n, must be a divisor of 4.\nThe divisor 1 does not satisfy the definition of Carmichael's function since except for.\nNeither does 2 since.\nHence\n. Indeed,.\nBoth 2 and 3 are primitive λ-roots modulo 5 and also [primitive roots](https://bliptext.com/articles/primitive-root-modulo-n) modulo 5.\n. The set of numbers less than and coprime to 8 is\n{1,3,5,7}\n. Hence\nand\nλ(8)\nmust be a divisor of 4.\nIn fact\nsince.\nThe primitive λ-roots modulo 8 are 3, 5, and 7.\nThere are no primitive roots modulo 8.\n\n# Recurrence for \n\nλ(n)\nThe Carmichael lambda function of a prime power can be expressed in terms of the Euler totient.\nAny 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](https://bliptext.com/articles/least-common-multiple) of the λ of the prime power factors.\nSpecifically,\nλ(n)\nis given by the recurrence\nEuler's totient for a prime power, that is, a number\npr\nwith\np\nprime and\nr ≥ 1\n, is given by\n\n# Carmichael's theorems\nCarmichael proved two theorems that, together, establish that if\nλ(n)\nis 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 for all a relatively prime to n.\nThis implies that the order of every element of the multiplicative group of integers modulo n divides\nλ(n)\n. Carmichael calls an element a for which is the least power of a congruent to 1 (mod n) a primitive λ-root modulo n.\n(This is not to be confused with a [primitive root modulo n](https://bliptext.com/articles/primitive-root-modulo-n), which Carmichael sometimes refers to as a primitive \\varphi-root modulo n.)\nIf g is one of the primitive λ-roots guaranteed by the theorem, then has no positive integer solutions m less than\nλ(n)\n, showing that there is no positive\nm < λ(n)\nsuch that for all a relatively prime to n.\nThe second statement of Theorem 2 does not imply that all primitive λ-roots modulo n are congruent to powers of a single root g. For example, if\n, then\nwhile and.\nThere are four primitive λ-roots modulo 15, namely 2, 7, 8, and 13 as.\nThe 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.\nThe other four elements of the multiplicative group modulo 15, namely 1, 4 (which satisfies ), 11, and 14, are not primitive λ-roots modulo 15.\nFor a contrasting example, if\n, then and.\nThere are two primitive λ-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other.\nThey are also both primitive \\varphi-roots modulo 9.\n\n# Properties of the Carmichael function\nIn this section, an [integer](https://bliptext.com/articles/integer) n is divisible by a nonzero [integer](https://bliptext.com/articles/integer) m if there exists an [integer](https://bliptext.com/articles/integer) k such that n = km. This is written as\n\n## A consequence of minimality of \n\nλ(n)\nSuppose\nam ≡ 1 (mod n)\nfor all numbers a coprime with n. Then\nλ(n)\n.\n**Proof:** If\nwith\n0 ≤ r < λ(n)\n, then\nfor all numbers a coprime with n. It follows that\nr = 0\nsince\nr < λ(n)\nand\nλ(n)\nis the minimal positive exponent for which the congruence holds for all a coprime with n.\n\n## λ(n)\n\n divides \n\nφ(n)\nThis follows from elementary [group theory](https://bliptext.com/articles/group-theory), because the exponent of any [finite group](https://bliptext.com/articles/finite-group) must divide the order of the group.\nλ(n)\nis the exponent of the multiplicative group of integers modulo n while\nφ(n)\nis the order of that group.\nIn particular, the two must be equal in the cases where the multiplicative group is cyclic due to the existence of a [primitive root](https://bliptext.com/articles/primitive-root-modulo-n), which is the case for odd prime powers.\nWe can thus view Carmichael's theorem as a sharpening of [Euler's theorem](https://bliptext.com/articles/euler-s-theorem).\n\n## Divisibility\n**Proof.**\nBy definition, for any integer k with (and thus also ), we have that , and therefore.\nThis establishes that for all k relatively prime to a. By the consequence of minimality proved above, we have.\n\n## Composition\nFor all positive integers a and b it holds that\nThis is an immediate consequence of the recurrence for the Carmichael function.\n\n## Exponential cycle length\nIf is the biggest exponent in the prime factorization of n, then for all a (including those not coprime to n) and all\nr ≥ rmax\n,\nIn particular, for [square-free](https://bliptext.com/articles/square-free-integer) n (\n), for all a we have\n\n## Average value\nFor any\nn ≥ 16\n(called Erdős approximation in the following) with the constant\nand\nγ ≈ 0.57721\n, the [Euler–Mascheroni constant](https://bliptext.com/articles/euler-mascheroni-constant).\nThe following table gives some overview over the first\n226 – 1 = 67,108,863\nvalues of the λ function, for both, the exact average and its Erdős-approximation.\nAdditionally given is some overview over the more easily accessible “logarithm over logarithm” values\nLoL(n) := ln λ(n)⁄ln n\nwith\nLoL(n) > 4⁄5 ⇔ λ(n) > n4⁄5\n. There, the table entry in row number 26 at column\n% LoL > 4⁄5\n→ 60.49 indicates that 60.49% (≈ 40,000,000) of the integers\n1 ≤ n ≤ 67,108,863\nhave\nλ(n) > n4⁄5\nmeaning that the majority of the λ values is exponential in the length\nl := log2(n)\nof the input n, namely\n! ν ||\nn = 2ν – 1\n|| sum\n|| average\n|| Erdős average || Erdős / exact average ||\nLoL\naverage || %\nLoL\n> 4⁄5 || %\nLoL\n> 7⁄8\n\n## Prevailing interval\nFor all numbers N and all but\no(N)\npositive integers\nn ≤ N\n(a \"prevailing\" majority):\nwith the constant\n\n## Lower bounds\nFor any sufficiently large number N and for any\nΔ ≥ (ln ln N)3\n, there are at most\npositive integers\nn ≤ N\nsuch that\nλ(n) ≤ ne−Δ\n.\n\n## Minimal order\nFor any sequence\nn1 < n2 < n3 < ⋯\nof positive integers, any constant\n0 < c < 1⁄ln 2\n, and any sufficiently large i:\n\n## Small values\nFor a constant c and any sufficiently large positive A, there exists an integer\nn > A\nsuch that\nMoreover, n is of the form\nfor some square-free integer\nm < (ln A)c ln ln ln A\n.\n\n## Image of the function\nThe set of values of the Carmichael function has counting function\nwhere\n\n# Use in cryptography\nThe Carmichael function is important in [cryptography](https://bliptext.com/articles/cryptography) due to its use in the [RSA encryption algorithm](https://bliptext.com/articles/rsa-cryptosystem).\n\n# Proof of Theorem 1\nFor\n, a prime, Theorem 1 is equivalent to Fermat's little theorem:\nFor prime powers\npr\n,\nr > 1\n, if holds for some integer h, then raising both sides to the power p gives\nfor some other integer h'.\nBy induction it follows that for all a relatively prime to p and hence to\npr\n. This establishes the theorem for\nor any odd prime power.\n\n## Sharpening the result for higher powers of two\nFor a coprime to (powers of) 2 we have\nfor some integer\nh2\n. Then,\nwhere h_3 is an integer.\nWith\nr = 3\n, this is written\nSquaring both sides gives\nwhere h_{r+1} is an integer.\nIt follows by induction that\nfor all r\\ge3 and all a coprime to 2^r.\n\n## Integers with multiple prime factors\nBy the [unique factorization theorem](https://bliptext.com/articles/unique-factorization-theorem), any\nn > 1\ncan be written in a unique way as where\np1 < p2 < ...\n< pk\nare primes and\nr1, r2, ..., rk\nare positive integers.\nThe results for prime powers establish that, for 1\\le j\\le k, From this it follows that\nwhere, as given by the recurrence,\nFrom the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem) one concludes that","current_revision":null,"created_by":"kACnuQmH5k9Nr5VNVEpVeg7XpvUmMctD","created_at":"2025-01-25T21:13:25.896Z","updated_at":"2025-01-25T21:13:25.896Z","search_vector":"'carmichael':1 'function':2","search_content":" \n \n\n# \n[[File:carmichaelLambda.svg|thumb|upright=2|Carmichael λ function:\nλ(n)\nfor\n1 ≤ n ≤ 1000\n(compared to Euler φ function)]]\nIn [number theory](https://bliptext.com/articles/number-theory), a branch of [mathematics](https://bliptext.com/articles/mathematics), the **Carmichael function**\nλ(n)\nof a [positive integer](https://bliptext.com/articles/positive-integer) n is the smallest [positive integer](https://bliptext.com/articles/positive-integer) m such that\nholds for every integer a [coprime](https://bliptext.com/articles/coprime) to n. In algebraic terms,\nλ(n)\nis the [exponent](https://bliptext.com/articles/exponent-of-a-group) of the [multiplicative group of integers modulo n](https://bliptext.com/articles/multiplicative-group-of-integers-modulo-n).\nAs this is a [finite abelian group](https://bliptext.com/articles/abelian-group), there must exist an element whose [order](https://bliptext.com/articles/cyclic-group) equals the exponent,\nλ(n)\n. Such an element is called a '''primitive\nλ\n-root modulo n'''.\nThe Carmichael function is named after the American mathematician [Robert Carmichael](https://bliptext.com/articles/robert-daniel-carmichael) who defined it in 1910.\nIt is also known as **Carmichael's λ function**, the **reduced totient function**, and the **least universal exponent function**.\nThe order of the multiplicative group of integers modulo n is\nφ(n)\n, where φ is [Euler's totient function](https://bliptext.com/articles/euler-s-totient-function).\nSince the order of an element of a finite group divides the order of the group,\nλ(n)\ndivides\nφ(n)\n. The following table compares the first 36 values of\nλ(n)\nand\nφ(n)\n(in **bold** if they are different; the ns such that they are different are listed in ).\n\n# Numerical examples\n. The set of numbers less than and coprime to 5 is\n{1,2,3,4}\n. Hence Euler's totient function has value\nand the value of Carmichael's function,\nλ(5)\n, must be a divisor of 4.\nThe divisor 1 does not satisfy the definition of Carmichael's function since except for.\nNeither does 2 since.\nHence\n. Indeed,.\nBoth 2 and 3 are primitive λ-roots modulo 5 and also [primitive roots](https://bliptext.com/articles/primitive-root-modulo-n) modulo 5.\n. The set of numbers less than and coprime to 8 is\n{1,3,5,7}\n. Hence\nand\nλ(8)\nmust be a divisor of 4.\nIn fact\nsince.\nThe primitive λ-roots modulo 8 are 3, 5, and 7.\nThere are no primitive roots modulo 8.\n\n# Recurrence for \n\nλ(n)\nThe Carmichael lambda function of a prime power can be expressed in terms of the Euler totient.\nAny 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](https://bliptext.com/articles/least-common-multiple) of the λ of the prime power factors.\nSpecifically,\nλ(n)\nis given by the recurrence\nEuler's totient for a prime power, that is, a number\npr\nwith\np\nprime and\nr ≥ 1\n, is given by\n\n# Carmichael's theorems\nCarmichael proved two theorems that, together, establish that if\nλ(n)\nis 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 for all a relatively prime to n.\nThis implies that the order of every element of the multiplicative group of integers modulo n divides\nλ(n)\n. Carmichael calls an element a for which is the least power of a congruent to 1 (mod n) a primitive λ-root modulo n.\n(This is not to be confused with a [primitive root modulo n](https://bliptext.com/articles/primitive-root-modulo-n), which Carmichael sometimes refers to as a primitive \\varphi-root modulo n.)\nIf g is one of the primitive λ-roots guaranteed by the theorem, then has no positive integer solutions m less than\nλ(n)\n, showing that there is no positive\nm 4⁄5 ⇔ λ(n) > n4⁄5\n. There, the table entry in row number 26 at column\n% LoL > 4⁄5\n→ 60.49 indicates that 60.49% (≈ 40,000,000) of the integers\n1 ≤ n ≤ 67,108,863\nhave\nλ(n) > n4⁄5\nmeaning that the majority of the λ values is exponential in the length\nl := log2(n)\nof the input n, namely\n! ν ||\nn = 2ν – 1\n|| sum\n|| average\n|| Erdős average || Erdős / exact average ||\nLoL\naverage || %\nLoL\n> 4⁄5 || %\nLoL\n> 7⁄8\n\n## Prevailing interval\nFor all numbers N and all but\no(N)\npositive integers\nn ≤ N\n(a \"prevailing\" majority):\nwith the constant\n\n## Lower bounds\nFor any sufficiently large number N and for any\nΔ ≥ (ln ln N)3\n, there are at most\npositive integers\nn ≤ N\nsuch that\nλ(n) ≤ ne−Δ\n.\n\n## Minimal order\nFor any sequence\nn1 A\nsuch that\nMoreover, n is of the form\nfor some square-free integer\nm 1\n, if holds for some integer h, then raising both sides to the power p gives\nfor some other integer h'.\nBy induction it follows that for all a relatively prime to p and hence to\npr\n. This establishes the theorem for\nor any odd prime power.\n\n## Sharpening the result for higher powers of two\nFor a coprime to (powers of) 2 we have\nfor some integer\nh2\n. Then,\nwhere h_3 is an integer.\nWith\nr = 3\n, this is written\nSquaring both sides gives\nwhere h_{r+1} is an integer.\nIt follows by induction that\nfor all r\\ge3 and all a coprime to 2^r.\n\n## Integers with multiple prime factors\nBy the [unique factorization theorem](https://bliptext.com/articles/unique-factorization-theorem), any\nn > 1\ncan be written in a unique way as where\np1 < p2 < ...\n< pk\nare primes and\nr1, r2, ..., rk\nare positive integers.\nThe results for prime powers establish that, for 1\\le j\\le k, From this it follows that\nwhere, as given by the recurrence,\nFrom the [Chinese remainder theorem](https://bliptext.com/articles/chinese-remainder-theorem) one concludes that","revisionCount":0},"hasMore":false,"nextCursor":null}

History