In number theory, the Carmichael function of a positive integer n, denoted λ(n), is defined as the smallest integer m such that To meet Wikipedias quality standards, this article or section may require cleanup. ... Natural number can mean either a positive integer (1, 2, 3, 4, ...) or a non-negative integer (0, 1, 2, 3, 4, ...). Natural numbers have two main purposes: they can be used for counting (there are 3 apples on the table), or they can be used for ordering (this is...

for every integer a that is coprime to n. Coprime - Wikipedia /**/ @import /skins-1. ...

In other words, in more algebraic terms, it defines the exponent of the multiplicative group of residues modulo n. In group theory in mathematics, a periodic group is a group in which each element has finite order. ... In mathematics, the multiplicative group of integers modulo n is the group with multiplication as group operation and as elements the units in the ring for a given integer . ...

Carmichael's theorem

This function can also be defined recursively, as follows.

For prime p and positive integer k such that or :

λ(p^k) = p^{k − 1}(p − 1). (This is equal to φ(p^k) )

For integer ,

λ(2^k) = 2^{k − 2} .

For distinct primes and positive integers :

where lcm denotes the least common multiple. In arithmetic and number theory the least common multiple or lowest common multiple (lcm) or smallest common multiple of two integers a and b is the smallest positive integer that is a multiple of both a and b. ...

Carmichael's theorem states that if a is coprime to n, then Coprime - Wikipedia /**/ @import /skins-1. ...

,

where λ is the Carmichael function defined recursively. In other words, it asserts the correctness of the recursion. In theoretical computer science, correctness of an algorithm is asserted when it is said that the algorithm is correct with respect to a specification. ...

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. In number theory, Eulers theorem (also known as the Fermat-Euler theorem or Eulers totient theorem) states that if n is a positive integer and a is coprime to n, then aφ(n) ≡ 1 (mod n) where φ(n) is Eulers totient function and mod denotes the congruence... In number theory, the totient φ(n) of a positive integer n is defined to be the number of positive integers less or equal than n and coprime to n. ... In mathematics, an abelian group, also called a commutative group, is a group (G, *) such that a * b = b * a for all a and b in G. In other words, the order of elements in a product doesnt matter. ...

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. Fermats little theorem (not to be confused with Fermats last theorem) states that if p is a prime number, then for any integer a, This means that if you take some number a, multiply it by itself p times and subtract a, the result is divisible by p... In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na...

Properties of the Carmichael function

Average and typical value

Theorem 3 in [1]: For any x > 16, and a constant :

.

Theorem 2 in [1]: For all numbers N and all except o(N) positive integers :

λ(n) = n / (lnn)^{lnlnlnn + A + o(1)}

where A is a constant, .

Lower bounds

Theorem 5 in [2]: For any sufficiently large number N and for any , there are at most

positive integers such that .

Theorem 1 in [1]: For any sequence of positive integers, any constant 0 < c < 1 / ln2, and any sufficiently large i:

.

Small values

Theorem 1 in [1]: For a constant c and any sufficiently large positive A, there exists an integer n > A such that λ(n) < (lnA)^clnlnlnA. Moreover, n is of the form

n =	∏	q
	(q − 1) | m and q is prime

for some square-free integer m < (lnA)^clnlnlnA.

See also

• Carmichael number

In number theory, a Carmichael number is a composite positive integer n which satisfies the congruence bn âˆ’ 1 ≡ 1 (mod n) for all integers b which are relatively prime to n (see modular arithmetic). ...

References

[1] Paul Erdős, Carl Pomerance, Eric Schmutz, Carmichael's lambda function, Acta Arithmetica, vol. 58, 363--385, 1991 Paul ErdÅ‘s, pictured in lecture, late in life. ... One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ...

[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 One of the top number theorists of our time, Carl Pomerance received his PhD from Harvard University in 1972 and immediately joined the faculty at the University of Georgia, becoming full professor in 1982. ...