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 other words, in more algebraic terms, it defines the exponent of the multiplicative group of residues modulo n.

The first 25 values of $lambda(n)$ for "n" = 1, 2, 3, ... are 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, ... OEIS|id=A002322

Carmichael's theorem

This function can also be defined recursively, as follows.

For prime $p$ and positive integer $k$ such that $p\; ge\; 3$ or $k\; le\; 2$::$lambda(p^k)\; =\; p^\{k-1\}(p-1).,$ (This is equal to $varphi(p^k),$ )

For integer $k\; ge\; 3$,:$lambda(2^k)\; =\; 2^\{k-2\},$ .

For distinct primes $p\_1,p\_2,ldots,p\_t$ and positive integers $k\_1,k\_2,ldots,k\_t$::$lambda(p\_1^\{k\_1\}\; p\_2^\{k\_2\}\; cdots\; p\_t^\{k\_t\})\; =\; mathrm\{lcm\}(\; lambda(p\_1^\{k\_1\}),\; lambda(p\_2^\{k\_2\}),\; cdots,\; lambda(p\_t^\{k\_t\})\; )$

where $mathrm\{lcm\}$ denotes the least common multiple.

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 recursively. In other words, it asserts the correctness of the recursion. This can be proven by considering any Primitive root modulo n and the Chinese remainder theorem.

Hierarchy of results

The classical Euler's theorem implies that λ("n") divides φ("n"), the Euler's totient function. In fact Carmichael's theorem is related to Euler's theorem, because the exponent of 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.

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" adds nothing to Fermat's theorem, because the group in question is a cyclic group for which the order and exponent are both "p" − 1.

Properties of the Carmichael function

Average and typical value

Theorem 3 in [1] : For any $x>16,$, and a constant $B\; approx\; 0.34537$:

:$frac\{1\}\{x\}\; sum\_\{n\; leq\; x\}\; lambda\; (n)\; =\; frac\{x\}\{ln\; x\}\; e^\{frac\{Blnln\; x\}\{lnlnln\; x\}\; (1+o(1))\}$.

Theorem 2 in [1] : For all numbers $N$ and all except $o(N)$ positive integers $n\; leq\; N$: :$lambda(n)\; =\; n\; /\; (ln\; n)^\{lnlnln\; n\; +\; A\; +\; o(1)\},$where $A$ is a constant, $A\; approx\; 0.226969$.

Lower bounds

Theorem 5 in [2] : For any sufficiently large number $N$ and for any $Delta\; geq\; (lnln\; N)^3$, there are at most

:$Ne^\{-0.69(DeltalnDelta)^\{1/3$

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

Theorem 1 in [1] : For any sequence

:$lambda(n\_i)\; >\; (ln\; n\_i)^\{clnlnln\; n\_i\}$.

mall values

Theorem 1 in [1] : For a constant $c$ and any sufficiently large positive $A$, there exists an integer $n>A$ such that .Moreover, $n$ is of the form

:$n=prod\_\{(q-1)|m\; ext\{\; and\; \}\; q\; ext\{\; is\; primeq$ for some square-free integer .

ee also

* Carmichael number

References

[1] Paul Erdős, Carl Pomerance, Eric Schmutz, "Carmichael's lambda function", Acta Arithmetica, vol. 58, 363--385, 1991

[2] John Friedlander, Carl Pomerance, Igor E. Shparlinski, "Period of the power generator and small values of the Carmichael function", Mathematics of Computation, vol. 70 no. 236, pp. 1591-1605, 2001