Carmichael function




In number theory, the Carmichael function associates to every positive integer n a positive integer λ(n){displaystyle lambda (n)}lambda (n), defined as the smallest positive integer m such that



am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}}a^{m}equiv 1{pmod {n}} for every integer a between 1 and n that is coprime to n.

(Dropping the phrase "between 1 and n" leads to an equivalent definition.)
In algebraic terms, λ(n){displaystyle lambda (n)}lambda (n) equals the exponent of the multiplicative group of integers modulo n.


The Carmichael function is named after the American mathematician Robert Carmichael and is also known as the reduced totient function or the least universal exponent function.


The first 36 values of λ(n){displaystyle lambda (n)}lambda (n) (sequence A002322 in the OEIS) compared to Euler's totient function φ{displaystyle varphi }varphi . (in bold if they are different, the ns such that they are different are listed in OEIS: A033949)

























































































































n
 1
 2
 3
 4
 5
 6
 7
 8
 9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36

λ(n){displaystyle lambda (n)}lambda (n)
 1 1 2 2 4 2 6 2 6 4 10 2 12 6 4 4 16 6 18 4 6 10 22 2 20 12 18 6 28 4 30 8 10 16 12
6

φ(n){displaystyle varphi (n)}varphi (n)
 1 1 2 2 4 2 6 4 6 4 10 4 12 6 8 8 16 6 18 8 12 10 22 8 20 12 18 12 28 8 30 16 20 16 24
12



Contents






  • 1 Numerical example


  • 2 Computing λ(n){displaystyle lambda (n)}lambda (n) with Carmichael's theorem


  • 3 Properties of the Carmichael function


    • 3.1 λ(n) divides φ(n)


    • 3.2 Minimality


    • 3.3 Divisibility


    • 3.4 Composition


    • 3.5 Primitive m-th roots of unity


    • 3.6 Exponential cycle length


    • 3.7 Average and typical value


    • 3.8 Lower bounds


    • 3.9 Small values


    • 3.10 Image of the function




  • 4 Use in cryptography


  • 5 See also


  • 6 Notes


  • 7 References





Numerical example


Carmichael's function at 8 is 2, i.e. λ(8)=2{displaystyle lambda (8)=2}{displaystyle lambda (8)=2}, because for any number a co-prime to 8 it holds that a2 ≡ 1 (mod 8). Namely, 12 = 1 (mod 8), 32 = 9 ≡ 1 (mod 8), 52 = 25 ≡ 1 (mod 8) and 72 = 49 ≡ 1 (mod 8). Euler's totient function at 8 is 4, i.e. φ(8)=4{displaystyle varphi (8)=4}varphi (8)=4, because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Euler's theorem assures that a4 ≡ 1 (mod 8) for all a coprime to 8, but 4 is not the smallest such exponent.



Computing λ(n){displaystyle lambda (n)}lambda (n) with Carmichael's theorem


By the fundamental theorem of arithmetic any n > 1 can be written in a unique way as


n=p1r1p2r2…pkrk{displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}dots p_{k}^{r_{k}}}{displaystyle n=p_{1}^{r_{1}}p_{2}^{r_{2}}dots p_{k}^{r_{k}}}

where p1 < p2 < ... < pk are primes and r1 , ..., rk are positive integers. It is then the case that λ(n) is the least common multiple of the λ of each of its prime power factors:


λ(n)=lcm⁡(λ(p1r1),λ(p2r2),…,λ(pkrk)).{displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}.}{displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}.}

This can be proved using the Chinese Remainder Theorem.


Carmichael's theorem explains how to compute λ of a prime power: for a power of an odd prime and for 2 and 4, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater than 4 it is equal to half of the Euler totient.


Euler's function for prime powers is given by


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


Properties of the Carmichael function



λ(n) divides φ(n)


This follows from elementary group theory, because the exponent of any finite abelian 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.


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



Minimality


Suppose am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}}{displaystyle a^{m}equiv 1{pmod {n}}} for all numbers a coprime with n. Then λ(n)|m{displaystyle lambda (n)|m}{displaystyle lambda (n)|m}.


Proof. If m=kλ(n)+r{displaystyle m=k;lambda (n)+r}{displaystyle m=k;lambda (n)+r} with 0≤r<λ(n){displaystyle 0leq r<lambda (n)}{displaystyle 0leq r<lambda (n)}, then ar=1k⋅ar≡(aλ(n))k⋅ar=akλ(n)+r=am≡1(modn){displaystyle a^{r}=1^{k}cdot a^{r}equiv (a^{lambda (n)})^{k}cdot a^{r}=a^{k;lambda (n)+r}=a^{m}equiv 1{pmod {n}}}{displaystyle a^{r}=1^{k}cdot a^{r}equiv (a^{lambda (n)})^{k}cdot a^{r}=a^{k;lambda (n)+r}=a^{m}equiv 1{pmod {n}}} for all numbers a coprime with n. It follows r=0{displaystyle r=0}{displaystyle r=0} , since r<λ(n){displaystyle r<lambda (n)}{displaystyle r<lambda (n)} and λ(n){displaystyle lambda (n)}lambda (n) the minimal positive such number.



Divisibility


a|b⇒λ(a)|λ(b){displaystyle a|bRightarrow lambda (a)|lambda (b)}a|bRightarrow lambda (a)|lambda (b)

Proof. The result follows from the formula


λ(n)=lcm⁡(λ(p1r1),λ(p2r2),…,λ(pkrk)){displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}}{displaystyle lambda (n)=operatorname {lcm} {big (}lambda (p_{1}^{r_{1}}),,lambda (p_{2}^{r_{2}}),,ldots ,,lambda (p_{k}^{r_{k}}){big )}}


mentioned above.



Composition


For all positive integers a{displaystyle a}a and b{displaystyle b}b it holds



λ(lcm(a,b))=lcm(λ(a),λ(b)){displaystyle lambda (mathrm {lcm} (a,b))=mathrm {lcm} (lambda (a),lambda (b))}lambda ({mathrm {lcm}}(a,b))={mathrm {lcm}}(lambda (a),lambda (b)) .

This is an immediate consequence of the recursive definition of the Carmichael function.



Primitive m-th roots of unity


Let a{displaystyle a}a and n{displaystyle n}n be coprime and
let m{displaystyle m}m be the smallest exponent with am≡1(modn){displaystyle a^{m}equiv 1{pmod {n}}}a^{m}equiv 1{pmod {n}},
then it holds



m|λ(n){displaystyle m|lambda (n)}m|lambda (n) .

That is, the orders of primitive roots of unity in the ring of integers modulo n{displaystyle n}n are divisors of λ(n){displaystyle lambda (n)}lambda (n).



Exponential cycle length


If n{displaystyle n}n has maximum prime exponent rmax{displaystyle r_{rm {max}}}r_{rm max} under prime factorization, then for all a{displaystyle a}a (including those not co-prime to n{displaystyle n}n) and all r≥rmax{displaystyle rgeq r_{rm {max}}}{displaystyle rgeq r_{rm {max}}},


ar≡ar+λ(n)(modn){displaystyle a^{r}equiv a^{r+lambda (n)}{pmod {n}}}{displaystyle a^{r}equiv a^{r+lambda (n)}{pmod {n}}}

In particular, for squarefree n{displaystyle n}n (rmax=1{displaystyle r_{rm {max}}=1}{displaystyle r_{rm {max}}=1}), for all a{displaystyle a}a


a≡aλ(n)+1(modn){displaystyle aequiv a^{lambda (n)+1}{pmod {n}}}aequiv a^{{lambda (n)+1}}{pmod n}


Average and typical value


For any x > 16:



1x∑n≤xλ(n)=xln⁡xeB(1+o(1))ln⁡ln⁡x/(ln⁡ln⁡ln⁡x){displaystyle {frac {1}{x}}sum _{nleq x}lambda (n)={frac {x}{ln x}}e^{B(1+o(1))ln ln x/(ln ln ln x)}}{frac {1}{x}}sum _{{nleq x}}lambda (n)={frac {x}{ln x}}e^{{B(1+o(1))ln ln x/(ln ln ln x)}}.[1][2]

Where B is a constant,


B=e−γ∏p(1−1(p−1)2(p+1))≈0.34537 .{displaystyle B=e^{-gamma }prod _{p}left({1-{frac {1}{(p-1)^{2}(p+1)}}}right)approx 0.34537 .}B=e^{{-gamma }}prod _{p}left({1-{frac {1}{(p-1)^{2}(p+1)}}}right)approx 0.34537 .

For all numbers N and all except o(N) positive integers n ≤ N:


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

where A is a constant,[2][3]


A=−1+∑plog⁡p(p−1)2≈0.2269688 .{displaystyle A=-1+sum _{p}{frac {log p}{(p-1)^{2}}}approx 0.2269688 .}A=-1+sum _{p}{frac {log p}{(p-1)^{2}}}approx 0.2269688 .


Lower bounds


For any sufficiently large number N and for any Δ≥(ln⁡ln⁡N)3{displaystyle Delta geq (ln ln N)^{3}}Delta geq (ln ln N)^{3}, there are at most


Ne−0.69(Δln⁡Δ)1/3{displaystyle Ne^{-0.69(Delta ln Delta )^{1/3}}}Ne^{{-0.69(Delta ln Delta )^{{1/3}}}}

positive integers n≤N{displaystyle nleq N}nleq N such that λ(n)≤ne−Δ{displaystyle lambda (n)leq ne^{-Delta }}lambda (n)leq ne^{{-Delta }}.[4]


For any sequence n1<n2<n3<⋯{displaystyle n_{1}<n_{2}<n_{3}<cdots }n_{1}<n_{2}<n_{3}<cdots of positive integers, any constant 0<c<1/ln⁡2{displaystyle 0<c<1/ln 2}0<c<1/ln 2, and any sufficiently large i:



λ(ni)>(ln⁡ni)cln⁡ln⁡ln⁡ni{displaystyle lambda (n_{i})>(ln n_{i})^{cln ln ln n_{i}}}lambda (n_{i})>(ln n_{i})^{{cln ln ln n_{i}}}.[5][6]


Small values


For a constant c and any sufficiently large positive A, there exists an integer n>A{displaystyle n>A}n>A such that λ(n)<(ln⁡A)cln⁡ln⁡ln⁡A{displaystyle lambda (n)<(ln A)^{cln ln ln A}}lambda (n)<(ln A)^{{cln ln ln A}}.[6]
Moreover, n is of the form


n=∏(q−1)|m and q is primeq{displaystyle n=prod _{(q-1)|m{text{ and }}q{text{ is prime}}}q}n=prod _{{(q-1)|m{text{ and }}q{text{ is prime}}}}q

for some square-free integer m<(ln⁡A)cln⁡ln⁡ln⁡A{displaystyle m<(ln A)^{cln ln ln A}}m<(ln A)^{{cln ln ln A}}.[5]



Image of the function


The set of values of the Carmichael function has counting function


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

where η=1−1+log⁡log⁡2log⁡2=0.08607{displaystyle eta =1-{frac {1+log log 2}{log 2}}=0.08607}{displaystyle eta =1-{frac {1+log log 2}{log 2}}=0.08607}….[7]



Use in cryptography


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



See also


  • Carmichael number


Notes




  1. ^ Theorem 3 in Erdős (1991)


  2. ^ ab Sándor & Crstici (2004) p.194


  3. ^ Theorem 2 in Erdős (1991)


  4. ^ Theorem 5 in Friedlander (2001)


  5. ^ ab Theorem 1 in Erdős 1991


  6. ^ ab Sándor & Crstici (2004) p.193


  7. ^ 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..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output q{quotes:"""""""'""'"}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-limited a,.mw-parser-output .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}



References




  • 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, R. D. (2004-10-10). The Theory of Numbers. Nabu Press. ISBN 978-1144400345.









-

Popular posts from this blog

Bressuire

Image
Subprefecture and commune in Nouvelle-Aquitaine, France Bressuire Subprefecture and commune Chateau de Bressuire and the Eglise Notre-Dame Coat of arms Location of Bressuire Bressuire Show map of France Bressuire Show map of Nouvelle-Aquitaine Coordinates: 46°50′27″N 0°29′14″W  /  46.8408°N 0.4872°W  / 46.8408; -0.4872 Coordinates: 46°50′27″N 0°29′14″W  /  46.8408°N 0.4872°W  / 46.8408; -0.4872 Country France Region Nouvelle-Aquitaine Department Deux-Sèvres Arrondissement Bressuire Canton Bressuire Government  • Mayor .mw-parser-output .nobold{font-weight:normal} (2014–20) Jean Michel Bernier Area 1 180.59 km 2 (69.73 sq mi) Population (2014) 2 19,300  • Density 110/km 2 (280/sq mi) Time zone UTC+01:00 (CET)  • Summer (DST) UTC+02:00 (CEST) INSEE/Postal code 79049 /79300 Elevation 98–236 m (322–774 ft) (avg. 173 m or 568 ft) 1 French Land Register data, which exclude...
Read more

Vorschmack

Image
Vorschmack Ukrainian Jewish-style vorschmack served on rye bread Course Hors d'oeuvre Region or state Eastern Europe Associated national cuisine Ashkenazi Jewish, Finnish, German, Ukrainian, Polish, Russian Main ingredients Ground meat and/or fish Cookbook: Vorschmack   Media: Vorschmack Vorschmack or forshmak (Yiddish: פֿאָרשמאַק ‎, from archaic German Vorschmack , "foretaste" [1] or "appetizer" [2] ) is an originally East European dish made of salty minced fish or meat. Different variants of this dish are especially common in Ashkenazi Jewish and Finnish cuisine. Some varieties are also known in Russian and Polish cuisine. Contents 1 In Jewish cuisine 2 In Russian cuisine 3 In Polish cuisine 4 In Finnish cuisine 5 See also 6 References In Jewish cuisine According to Gil Marks, the German name points to the possible Germanic origin of this dish. [1] William Pokhlyobkin descr...
Read more

Quarantine

Image
For other uses, see Quarantine (disambiguation). Signal flag "Lima" called the "Yellow Jack" which when flown in harbor means ship is under quarantine. A simple yellow flag (also called the "Yellow Jack") had historically been used to signal quarantine (it stands for Q among signal flags), but now indicates the opposite, as a signal of a ship free of disease that requests boarding and inspection. A quarantine is used to separate and restrict the movement of people; it is 'a restraint upon the activities or communication of persons or the transport of goods designed to prevent the spread of disease or pests', for a certain period of time. [1] This is often used in connection to disease and illness, such as those who may possibly have been exposed to a communicable disease. [2] The term is often erroneously used to mean medical isolation, which is "to separate ill persons who have a communicable disease from those who are healthy...
Read more