Carmichael function

In number theory, the Carmichael function of a positive integer n, denoted $\lambda (n)$ , is defined as the smallest positive integer m such that

a^{m}\equiv 1{\pmod {n}}

for every integer a that is coprime to n. In more algebraic terms, it defines the exponent of the multiplicative group of integers modulo n. The Carmichael function is also known as the reduced totient function or the least universal exponent function, and is sometimes also denoted $\psi (n)$ .

The first 36 values of $\lambda (n)$ (sequence A002322 in the OEIS) compared to Euler's totient function $\varphi$ . (in bold if they are different)

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
$\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
$\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

Numerical example

7² = 49 ≡ 1 (mod 8) because 7 and 8 are coprime (their greatest common divisor equals 1; they have no common factors) and the value of Carmichael's function at 8 is 2. Euler's totient function is 4 at 8 because there are 4 numbers lesser than and coprime to 8 (1, 3, 5, and 7). Whilst it is true that 7⁴= 2401 ≡ 1 (mod 8), as shown by Euler's theorem, raising 7 to the fourth power is unnecessary because the Carmichael function indicates that 7 squared is congruent to 1 (mod 8). Raising 7 to exponents greater than 2 only repeats the cycle 7, 1, 7, 1, ... . Because the same holds true for 3 and 5, the Carmichael number is 2 rather than 4. ^[1]

Carmichael's theorem

For a power of an odd prime, twice the power of an odd prime, and for 2 and 4, λ(n) is equal to the Euler totient φ(n); for powers of 2 greater or equal than 4 it is equal to one half of the Euler totient:

\lambda (n)={\begin{cases}\;\;\varphi (n)&{\mbox{if }}n=2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,\dots \\{\tfrac {1}{2}}\varphi (n)&{\text{if }}n=8,16,32,64,128,256,\dots \end{cases}}

Euler's function for prime powers is given by

\varphi (p^{k})=p^{{k-1}}(p-1).\;

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

n=p_{1}^{{a_{1}}}p_{2}^{{a_{2}}}\dots p_{{\omega (n)}}^{{a_{{\omega (n)}}}}

where p₁ < p₂ < ... < p_ω are primes and the a_i > 0. (n = 1 corresponds to the empty product.)

For general n, λ(n) is the least common multiple of λ of each of its prime power factors:

\lambda (n)=\operatorname {lcm}[\lambda (p_{1}^{{a_{1}}}),\;\lambda (p_{2}^{{a_{2}}}),\dots ,\lambda (p_{{\omega (n)}}^{{a_{{\omega (n)}}}})].

Carmichael's theorem states that if a is coprime to n, then

a^{{\lambda (n)}}\equiv 1{\pmod {n}},

where $\lambda$ is the Carmichael function defined above. In other words, it asserts the correctness of the formulas. This can be proven by considering any primitive root modulo n and the Chinese remainder theorem.

Proofs

The following proofs proceed by induction.

Proof for Odd Prime Powers

From Fermat's little theorem, we have $a^{p-1}=1+hp$ . For k = 1, h an integer:

a^{p^{k-1}(p-1)}=1+hp^k

a^{p^{k}(p-1)}=(1+hp^{k})^{p}=1+hp^{k+1}+\dots =1+h_{0}p^{k+1}

for some integer h₀.

By induction, we have $a^{p^{k-1}(p-1)}\equiv 1\pmod{p^k}$ .

Proof for Powers of Two

For a coprime to powers of 2 we have $a=1+2h$ . Then,

a^2=1+4h(h+1)=1+8C_{h+1}^2

where we take advantage of the fact that $C_{h+1}^{2}={(h+1)h}/2$ is an integer.

So, for k = 3, h an integer:

a^{2^{k-2}}=1+2^k h

a^{2^{k-1}}=(1+2^k h)^2=1+2^{k+1}(h+2^{k-1}h^2)

By induction, when k ≥ 3, we have $a^{2^{k-2}}\equiv 1\pmod{2^k}$ .

Hierarchy of results

Since λ(n) divides φ(n), Euler's totient function (the quotients are listed in A034380), the Carmichael function is a stronger result than the classical Euler's theorem. Clearly Carmichael's theorem is related to Euler's theorem, because the exponent of a finite abelian group must divide the order of the group, by elementary group theory. The two functions differ already in small cases: λ(15) = 4 while φ(15) = 8 (see A033949 for the associated n).

Fermat's little theorem is the special case of Euler's theorem in which n is a prime number p. Carmichael's theorem for a prime p gives the same result, because the group in question is a cyclic group for which the order and exponent are both p − 1.

Properties of the Carmichael function

Divisibility

a|b\Rightarrow \lambda (a)|\lambda (b)

Composition

For all positive integers $a$ and $b$ it holds

\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$ and $n$ be coprime and let $m$ be the smallest exponent with $a^{m}\equiv 1{\pmod {n}}$ , then it holds

m|\lambda (n)

That is, the orders of primitive roots of unity in the ring of integers modulo $n$ are divisors of $\lambda (n)$ .

Exponential cycle length

For a number $n$ with maximum prime exponent of $x_{{max}}$ under prime factorization, then for all $a$ (including those not co-prime to $n$ ) and all $k\geq x_{{max}}$ ,

a^{k}\equiv a^{{k+\lambda (n)}}{\pmod n}

In particular, for squarefree $n$ ( $x_{{max}}=1$ ), for all $a$

a\equiv a^{{\lambda (n)+1}}{\pmod n}

Average and typical value

For any x > 16:

{\frac {1}{x}}\sum _{{n\leq x}}\lambda (n)={\frac {x}{\ln x}}e^{{B(1+o(1))\ln \ln x/(\ln \ln \ln x)}}

.^[2]^[3]

Where B is a constant,

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:

\lambda (n)=n/(\ln n)^{{\ln \ln \ln n+A+o(1)}}\,

where A is a constant,^[3]^[4]

A=-1+\sum _{p}{\frac {\log p}{(p-1)^{2}}}\approx 0.2269688\ .

Lower bounds

For any sufficiently large number N and for any $\Delta \geq (\ln \ln N)^{3}$ , there are at most

Ne^{{-0.69(\Delta \ln \Delta )^{{1/3}}}}

positive integers $n\leq N$ such that $\lambda (n)\leq ne^{{-\Delta }}$ .^[5]

For any sequence $n_{1}<n_{2}<n_{3}<\cdots$ of positive integers, any constant $0<c<1/\ln 2$ , and any sufficiently large i:

\lambda (n_{i})>(\ln n_{i})^{{c\ln \ln \ln n_{i}}}

.^[6]^[7]

Small values

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

n=\prod _{{(q-1)|m{\text{ and }}q{\text{ is prime}}}}q

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

Image of the function

The set of values of the Carmichael function has counting function

{\frac {x}{(\log x)^{{\eta +o(1)}}}}\ ,

where $\eta =1-{\frac {1+\log \log 2}{\log 2}}=0.08607$ ….^[8]

Notes

↑ "Archived copy". Archived from the original on 2011-06-15. Retrieved 2010-01-05.
↑ Theorem 3 in Erdős (1991)
1 2 Sándor & Crstici (2004) p.194
↑ Theorem 2 in Erdős (1991)
↑ Theorem 5 in Friedlander (2001)
1 2 Theorem 1 in Erdős 1991
1 2 Sándor & Crstici (2004) p.193
↑ Ford, Kevin; Luca, Florian; Pomerance, Carl (27 August 2014). "The image of Carmichael's λ-function". arXiv:1408.6506 [math.NT].

References

Erdős, Paul; Pomerance, Carl; Schmutz, Eric (1991). "Carmichael's lambda function". Acta Arithmetica. 58: 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 1-4020-2546-7. Zbl 1079.11001.
Carmichael, R. D. The Theory of Numbers. Nabu Press. ISBN 1144400341.

Totient function

Euler's totient function $\phi (n)$ Jordan's totient function $J_{k}(n)$ Carmichael function $\lambda (n)$ Nontotient Noncototient Highly totient number Highly cototient number Sparsely totient number

This article is issued from Wikipedia - version of the 11/28/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.