Carmichael function

Template:Short description In number theory, a branch of mathematics, the Carmichael function Template:Math of a positive integer Template:Mvar is the smallest positive integer Template:Mvar such that

<math>a^m \equiv 1 \pmod{n}</math>

holds for every integer Template:Mvar coprime to Template:Mvar. In algebraic terms, Template:Math is the exponent of the [[multiplicative group of integers modulo n|multiplicative group of integers modulo Template:Mvar]]. As this is a finite abelian group, there must exist an element whose order equals the exponent, Template:Math. Such an element is called a primitive Template:Math-root modulo Template:Mvar.

File:CarmichaelLambda.svg

Carmichael Template:Mvar function: Template:Math for Template:Math (compared to Euler Template:Mvar function)

The Carmichael function is named after the American mathematician Robert Carmichael who defined it in 1910.<ref> Template:Cite journal </ref> 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 Template:Mvar is Template:Math, where Template:Mvar is Euler's totient function. Since the order of an element of a finite group divides the order of the group, Template:Math divides Template:Math. The following table compares the first 36 values of Template:Math (sequence A002322 in the OEIS) and Template:Math (in bold if they are different; the values ofTemplate:Mvar such that they are different are listed in Template:Oeis).

Template:Mvar	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
Template:Math	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
Template:Math	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

Numerical examples

• Template:Math. The set of numbers less than and coprime to 5 is Template:Math}. Hence Euler's totient function has value Template:Math and the value of Carmichael's function, Template:Math, must be a divisor of 4. The divisor 1 does not satisfy the definition of Carmichael's function since <math>a^1 \not\equiv 1\pmod{5}</math> except for <math>a\equiv1\pmod{5}</math>. Neither does 2 since <math>2^2 \equiv 3^2 \equiv 4 \not\equiv 1\pmod{5}</math>. Hence Template:Math. Indeed, <math>1^4\equiv 2^4\equiv 3^4\equiv 4^4\equiv1\pmod{5}</math>. Both 2 and 3 are primitive Template:Mvar-roots modulo 5 and also primitive roots modulo 5.
• Template:Math. The set of numbers less than and coprime to 8 is Template:Math. Hence Template:Math and Template:Math must be a divisor of 4. In fact Template:Math since <math>1^2\equiv 3^2\equiv 5^2\equiv 7^2\equiv1\pmod{8}</math>. The primitive Template:Mvar-roots modulo 8 are 3, 5, and 7. There are no primitive roots modulo 8.

Recurrence for Template:Math

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 Template:Mvar of the product is the least common multiple of the Template:Mvar of the prime power factors. Specifically, Template:Math 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,}\\ \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}</math> Euler's totient for a prime power, that is, a number Template:Math with Template:Math prime and Template:Math, is given by

<math>\varphi(p^r) = p^{r-1}(p-1).</math>

Carmichael's theorems

Template:Anchor Carmichael proved two theorems that, together, establish that if Template:Math 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 Template:Mvar such that <math>a^m\equiv 1\pmod{n}</math> for all Template:Mvar relatively prime to Template:Mvar. Template:Math theorem This implies that the order of every element of the multiplicative group of integers modulo Template:Mvar divides Template:Math. Carmichael calls an element Template:Mvar for which <math>a^{\lambda(n)}</math> is the least power of Template:Mvar congruent to 1 (mod Template:Mvar) a primitive λ-root modulo n.<ref>Carmichael (1914) p.54</ref> (This is not to be confused with a [[primitive root modulo n|primitive root modulo Template:Mvar]], which Carmichael sometimes refers to as a primitive <math>\varphi</math>-root modulo Template:Mvar.) Template:Math theorem If Template:Mvar is one of the primitive Template:Mvar-roots guaranteed by the theorem, then <math>g^m\equiv1\pmod{n}</math> has no positive integer solutions Template:Mvar less than Template:Math, showing that there is no positive Template:Math such that <math>a^m\equiv 1\pmod{n}</math> for all Template:Mvar relatively prime to Template:Mvar.

The second statement of Theorem 2 does not imply that all primitive Template:Mvar-roots modulo Template:Mvar are congruent to powers of a single root Template:Mvar.<ref>Carmichael (1914) p.56</ref> For example, if Template:Math, then Template:Math while <math>\varphi(n)=8</math> and <math>\varphi(\lambda(n))=2</math>. There are four primitive Template:Mvar-roots modulo 15, namely 2, 7, 8, and 13 as <math>1\equiv2^4\equiv8^4\equiv7^4\equiv13^4</math>. 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 <math>4\equiv2^2\equiv8^2\equiv7^2\equiv13^2</math>), 11, and 14, are not primitive Template:Mvar-roots modulo 15.

For a contrasting example, if Template:Math, then <math>\lambda(n)=\varphi(n)=6</math> and <math>\varphi(\lambda(n))=2</math>. There are two primitive Template:Mvar-roots modulo 9, namely 2 and 5, each of which is congruent to the fifth power of the other. They are also both primitive <math>\varphi</math>-roots modulo 9.

Properties of the Carmichael function

In this section, an integer <math>n</math> is divisible by a nonzero integer <math>m</math> if there exists an integer <math>k</math> such that <math>n = km</math>. This is written as

<math>m \mid n.</math>

A consequence of minimality of Template:Math

Suppose Template:Math for all numbers Template:Mvar coprime with Template:Mvar. Then Template:Math.

Proof: If Template:Math with Template:Math, then

<math>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}</math>

for all numbers Template:Mvar coprime with Template:Mvar. It follows that Template:Math since Template:Math and Template:Math is the minimal positive exponent for which the congruence holds for all Template:Mvar coprime with Template:Mvar.

Template:Math divides Template:Math

This follows from elementary group theory, because the exponent of any finite group must divide the order of the group. Template:Math is the exponent of the multiplicative group of integers modulo Template:Mvar while Template:Math 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.

Divisibility

<math> a\,|\,b \Rightarrow \lambda(a)\,|\,\lambda(b) </math>

Proof.

By definition, for any integer <math>k</math> with <math>\gcd(k,b) = 1</math> (and thus also <math>\gcd(k,a) = 1</math>), we have that <math> b \,|\, (k^{\lambda(b)} - 1)</math> , and therefore <math> a \,|\, (k^{\lambda(b)} - 1)</math>. This establishes that <math>k^{\lambda(b)}\equiv1\pmod{a}</math> for all Template:Mvar relatively prime to Template:Mvar. By the consequence of minimality proved above, we have <math> \lambda(a)\,|\,\lambda(b) </math>.

Composition

For all positive integers Template:Mvar and Template:Mvar it holds that

<math>\lambda(\mathrm{lcm}(a,b)) = \mathrm{lcm}(\lambda(a), \lambda(b))</math>.

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

Exponential cycle length

If <math>r_{\mathrm{max}}=\max_i\{r_i\}</math> is the biggest exponent in the prime factorization <math> n= p_1^{r_1}p_2^{r_2} \cdots p_{k}^{r_k} </math> of Template:Mvar, then for all Template:Mvar (including those not coprime to Template:Mvar) and all Template:Math,

<math>a^r \equiv a^{\lambda(n)+r} \pmod n.</math>

In particular, for square-free Template:Mvar (Template:Math), for all Template:Mvar we have

<math>a \equiv a^{\lambda(n)+1} \pmod n.</math>

Average value

For any Template:Math:<ref>Theorem 3 in Erdős (1991)</ref><ref name=HBII194>Sándor & Crstici (2004) p.194</ref>

<math>\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) }</math>

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

<math>B := e^{-\gamma} \prod_{p\in\mathbb P} \left({1 - \frac{1}{(p-1)^2(p+1)}}\right) \approx 0.34537 </math>

and Template:Math, the Euler–Mascheroni constant.

The following table gives some overview over the first Template:Math values of the Template:Mvar function, for both, the exact average and its Erdős-approximation.

Additionally given is some overview over the more easily accessible Template:Nowrap Template:Math with

• Template:Math.

There, the table entry in row number 26 at column

• Template:Math Template:Pad → 60.49

indicates that 60.49% (≈ Template:Val) of the integers Template:Math have Template:Math meaning that the majority of the Template:Mvar values is exponential in the length Template:Math of the input Template:Mvar, namely

<math>\left(2^\frac45\right)^l = 2^\frac{4l}{5} = \left(2^l\right)^\frac45 = n^\frac45.</math>

Template:Mvar	Template:Math	sum <math>\sum_{i\le n} \lambda(i) </math>	average <math>\tfrac1n \sum_{i\le n} \lambda(i) </math>	Erdős average	Erdős / exact average	Template:Math average	% Template:Math > Template:Sfrac	% Template:Math > Template:Sfrac
5	31	270	8.709677	68.643	7.8813	0.678244	41.94	35.48
6	63	964	15.301587	61.414	4.0136	0.699891	38.10	30.16
7	127	3574	28.141732	86.605	3.0774	0.717291	38.58	27.56
8	255	12994	50.956863	138.190	2.7119	0.730331	38.82	23.53
9	511	48032	93.996086	233.149	2.4804	0.740498	40.90	25.05
10	1023	178816	174.795699	406.145	2.3235	0.748482	41.45	26.98
11	2047	662952	323.865169	722.526	2.2309	0.754886	42.84	27.70
12	4095	2490948	608.290110	1304.810	2.1450	0.761027	43.74	28.11
13	8191	9382764	1145.496765	2383.263	2.0806	0.766571	44.33	28.60
14	16383	35504586	2167.160227	4392.129	2.0267	0.771695	46.10	29.52
15	32767	134736824	4111.967040	8153.054	1.9828	0.776437	47.21	29.15
16	65535	513758796	7839.456718	15225.43Template:0	1.9422	0.781064	49.13	28.17
17	131071	1964413592	14987.40066Template:0	28576.97Template:0	1.9067	0.785401	50.43	29.55
18	262143	7529218208	28721.79768Template:0	53869.76Template:0	1.8756	0.789561	51.17	30.67
19	524287	28935644342	55190.46694Template:0	101930.9Template:0	1.8469	0.793536	52.62	31.45
20	1048575	111393101150	106232.8409Template:0	193507.1Template:0	1.8215	0.797351	53.74	31.83
21	2097151	429685077652	204889.9090Template:0	368427.6Template:0	1.7982	0.801018	54.97	32.18
22	4194303	1660388309120	395867.5158Template:0	703289.4Template:0	1.7766	0.804543	56.24	33.65
23	8388607	6425917227352	766029.1187Template:0	1345633Template:0	1.7566	0.807936	57.19	34.32
24	16777215	24906872655990	1484565.386Template:0	2580070Template:0	1.7379	0.811204	58.49	34.43
25	33554431	96666595865430	2880889.140Template:0	4956372Template:0	1.7204	0.814351	59.52	35.76
26	67108863	375619048086576	5597160.066Template:0	9537863Template:0	1.7041	0.817384	60.49	36.73

Prevailing interval

For all numbers Template:Mvar and all but Template:Math<ref>Theorem 2 in Erdős (1991) 3. Normal order. (p.365)</ref> positive integers Template:Math (a "prevailing" majority):

<math>\lambda(n) = \frac{n} {(\ln n)^{\ln\ln\ln n + A + o(1)}}</math>

with the constant<ref name=HBII194/>

<math>A := -1 + \sum_{p\in\mathbb P} \frac{\ln p}{(p-1)^2} \approx 0.2269688 </math>

Lower bounds

For any sufficiently large number Template:Mvar and for any Template:Math, there are at most

<math>N\exp\left(-0.69(\Delta\ln\Delta)^\frac13\right)</math>

positive integers Template:Math such that Template:Math.<ref>Theorem 5 in Friedlander (2001)</ref>

Minimal order

For any sequence Template:Math of positive integers, any constant Template:Math, and any sufficiently large Template:Mvar:<ref name="Theorem 1 in Erdős (1991)">Theorem 1 in Erdős (1991)</ref><ref name=HBII193>Sándor & Crstici (2004) p.193</ref>

<math>\lambda(n_i) > \left(\ln n_i\right)^{c\ln\ln\ln n_i}.</math>

Small values

For a constant Template:Mvar and any sufficiently large positive Template:Mvar, there exists an integer Template:Math such that<ref name=HBII193/>

<math>\lambda(n)<\left(\ln A\right)^{c\ln\ln\ln A}.</math>

Moreover, Template:Mvar is of the form

<math>n=\mathop{\prod_{q \in \mathbb P}}_{(q-1)|m}q</math>

for some square-free integer Template:Math.<ref name="Theorem 1 in Erdős (1991)"/>

Image of the function

The set of values of the Carmichael function has counting function<ref>Template:Cite journal</ref>

<math>\frac{x}{(\ln x)^{\eta+o(1)}} ,</math>

where

<math>\eta=1-\frac{1+\ln\ln2}{\ln2} \approx 0.08607</math>

Use in cryptography

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

Proof of Theorem 1

For Template:Math, 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 Template:Math, Template:Math, if

<math>a^{p^{r-1}(p-1)}=1+hp^r</math>

holds for some integer Template:Mvar, then raising both sides to the power Template:Mvar 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 Template:Mvar relatively prime to Template:Mvar and hence to Template:Math. This establishes the theorem for Template:Math or any odd prime power.

Sharpening the result for higher powers of two

For Template:Mvar coprime to (powers of) 2 we have Template:Math for some integer Template:Math. Then,

<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 Template:Math, this is written

<math>a^{2^{r-2}} = 1+2^r h_r.</math>

Squaring both sides gives

<math>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},</math>

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 Template:Mvar coprime to <math>2^r</math>.<ref>Carmichael (1914) pp.38–39</ref>

Integers with multiple prime factors

By the unique factorization theorem, any Template:Math 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 Template:Math are primes and Template:Math 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

• Carmichael number

Notes

<references/>

References

• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Gutenberg