Carmichael function

In number theory, the Carmichael function of a positive

integer n, denoted (n) , is dened as the smallest positive
integer m such that (pk ) = pk1 (p 1).

By the fundamental theorem of arithmetic any n > 1 can

a m
1 (mod n) be written in a unique way

for every integer a that is coprime to n. In more alge-

braic terms, it denes the exponent of the multiplicative n = pa1 pa2 . . . pa(n)
1 2 (n)
group of integers modulo n. The Carmichael function is
also known as the reduced totient function or the least where p < p < ... < p are primes and the ai > 0. (n =
1 2
universal exponent function, and is sometimes also de- 1 corresponds to the empty product.)
noted (n) .
For general n, (n) is the least common multiple of of
The rst 36 values of (n) (sequence A002322 in the each of its prime power factors:
OEIS) compared to Eulers totient function . (in bold
if they are dierent, the ns such that they are dierent are
listed in A033949) a(n)
(n) = lcm[(pa1 1 ), (pa2 2 ), . . . , (p(n) )].

Carmichaels theorem states that if a is coprime to n, then

1 Numerical example
Carmichaels function at 8 is 2 because for any x co-prime
a(n) 1 (mod n),
to 8 it holds that x2 1 (mod 8). For example, 72 = 49
1 (mod 8), where 7 and 8 are coprime (their greatest
where is the Carmichael function dened above. In
common divisor equals 1; they have no common factors).
other words, it asserts the correctness of the formulas.
Eulers totient function is 4 at 8 because there are 4 num-
This can be proven by considering any primitive root
bers lesser than and coprime to 8 (1, 3, 5, and 7). Whilst
modulo n and the Chinese remainder theorem.
it is true that 74 = 2401 1 (mod 8), as shown by Eulers
theorem, raising 7 to the fourth power is unnecessary be-
cause the Carmichael function indicates that 7 squared is
congruent to 1 (mod 8). Raising 7 to exponents greater 3 Proofs
than 2 only repeats the cycle 7, 1, 7, 1, ... . Because the
same holds true for 3 and 5, the Carmichael number is 2
The following proofs proceed by induction.
rather than 4. [1]

3.1 Proof for Odd Prime Powers

2 Carmichaels theorem
From Fermats little theorem, we have ap1 = 1 + hp .
For a power of an odd prime, twice the power of an odd For k = 1, h an integer:
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: k1
ap (p1) = 1 + hpk

{ k
(n) ap 18,
if n = 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 17,
(p1)
19,=22,
(1+hp k p
23, 25,)26,=27,
1+hp k+1
+ . . .= 1+h0 pk+1
29, 31, 34,
(n) = 1
2 (n) ifn = 8, 16, 32, 64, 128, 256, . . .
for some integer h0 .
k1
Eulers function for prime powers is given by By induction, we have ap (p1)
1 (mod pk ) .

1
2 5 PROPERTIES OF THE CARMICHAEL FUNCTION

3.2 Proof for Powers of Two The above proof is wrong because the element coprime to
a need not be coprime to b, and hence one can not write
For a coprime to powers of 2 we have a = 1+2h . Then, m(b) = k2 b + 1. In particular, take a = 3, b = 6 and
m = 2, then 22 is not congruent to 1 mod 6.
Proof. Using the following result
a2 = 1 + 4h(h + 1) = 1 + 8Ch+1
2

2
where we take advantage of the fact that Ch+1 =
a(n)
(h + 1)h/2 is an integer. (n) = lcm[(pa1 1 ), (pa2 2 ), . . . , (p(n) )].
So, for k = 3, h an integer:
the result follows.

k2
a2 = 1 + 2k h
5.3 Composition
2k1 k 2 k+1 k1 2
a = (1 + 2 h) = 1 + 2 (h + 2 h )
For all positive integers a and b it holds
2k2
By induction, when k 3, we have a 1 (mod 2k )
.
(lcm(a, b)) = lcm((a), (b))
4 Hierarchy of results This is an immediate consequence of the recursive de-
nition of the Carmichael function.
Since (n) divides (n), Eulers totient function (the
quotients are listed in A034380), the Carmichael func-
tion is a stronger result than the classical Eulers theo- 5.4 Primitive m-th roots of unity
rem. Clearly Carmichaels theorem is related to Eulers
theorem, because the exponent of a nite abelian group Let a and n be coprime and let m be the smallest exponent
must divide the order of the group, by elementary group with am 1 (mod n) , then it holds
theory. The two functions dier already in small cases:
(15) = 4 while (15) = 8 (see A033949 for the asso-
ciated n). m|(n)
Fermats little theorem is the special case of Eulers theo-
That is, the orders of primitive roots of unity in the ring
rem in which n is a prime number p. Carmichaels theo-
of integers modulo n are divisors of (n) .
rem for a prime p gives the same result, because the group
in question is a cyclic group for which the order and ex-
ponent are both p 1.
5.5 Exponential cycle length

For a number n with maximum prime exponent of xmax

5 Properties of the Carmichael under prime factorization, then for all a (including those
function not co-prime to n ) and all k xmax ,

5.1 Minimality
ak ak+(n) (mod n)
Suppose m 1 (mod a) for all m coprime with a.
c

Then (a)|c In particular, for squarefree n ( xmax = 1 ), for all a

Proof. If c = k(a) + r with 0 < r < (a) then

mc 1mr 1 (mod a) for all m, since r < (a) and
(a) minimal such number a a(n)+1 (mod n)

5.2 Divisibility 5.6 Average and typical value

a|b (a)|(b) For any x > 16:

Wrong Proof: Since b = k1 a we get m(b) = k2 b + 1 =
1 x B(1+o(1)) ln ln x/(ln ln ln x)
k1 k2 a + 1 for all m coprime with a. Statement follows x nx (n) = ln x e
[2][3]
from minimality. .
 3

Where B is a constant, 6 See also

Carmichael number
( 1
)

B=e 1 0.34537 .
p
(p 1)2 (p + 1)
7 Notes
For all numbers N and all except o(N) positive integers n
N: [1] Archived copy. Archived from the original on 2011-06-
15. Retrieved 2010-01-05.

[2] Theorem 3 in Erds (1991)

(n) = n/(ln n)ln ln ln n+A+o(1)
[3] Sndor & Crstici (2004) p.194
where A is a constant,[3][4]
[4] Theorem 2 in Erds (1991)

log p [5] Theorem 5 in Friedlander (2001)

A = 1 + 0.2269688 .
p
(p 1)2 [6] Theorem 1 in Erds 1991

[7] Sndor & Crstici (2004) p.193

5.7 Lower bounds [8] Ford, Kevin; Luca, Florian; Pomerance, Carl (27 Au-
gust 2014). The image of Carmichaels -function.
For any suciently large number N and for any arXiv:1408.6506 [[Link]].
(ln ln N )3 , there are at most

8 References
N e0.69( ln )
1/3

positive integers n N such that (n) ne .[5] Erds, Paul; Pomerance, Carl; Schmutz, Eric
(1991). Carmichaels lambda function. Acta
For any sequence n1 < n2 < n3 < of positive inte- Arithmetica. 58: 363385. ISSN 0065-1036. MR
gers, any constant 0 < c < 1/ ln 2 , and any suciently 1121092. Zbl 0734.11047.
large i:
Friedlander, John B.; Pomerance, Carl; Shparlinski,
(ni ) > (ln ni ) c ln ln ln ni [6][7]
. Igor E. (2001). Period of the power generator and
small values of the Carmichael function. Math-
ematics of Computation. 70 (236): 15911605,
5.8 Small values 18031806. ISSN 0025-5718. MR 1836921. Zbl
1029.11043. doi:10.1090/s0025-5718-00-01282-
For a constant c and any suciently large positive A, there 5.
exists an integer n > A such that (n) < (ln A)c ln ln ln A
Sndor, Jozsef; Crstici, Borislav (2004). Handbook
.[7] Moreover, n is of the form
of number theory II. Dordrecht: Kluwer Academic.
pp. 3236,193195. ISBN 1-4020-2546-7. Zbl
1079.11001.
n= q
(q1)|m and qprime is Carmichael, R. D. The Theory of Numbers. Nabu
Press. ISBN 1144400341.
for some square-free integer m < (ln A)c ln ln ln A .[6]

5.9 Image of the function

The set of values of the Carmichael function has counting
function

x
,
(log x)+o(1)
1+log log 2
where = 1 log 2 = 0.08607 .[8]
4 9 TEXT AND IMAGE SOURCES, CONTRIBUTORS, AND LICENSES

9 Text and image sources, contributors, and licenses

9.1 Text
Carmichael function Source: [Link] Contributors: Michael Hardy, Iso-
morphic, Dominus, Chinju, Silversh, Charles Matthews, Giftlite, Numerao, Tromer, Grutness, Ling Kah Jai, Oleg Alexandrov, Arbol01,
Hello5959us, Rjwilmsi, Joan, Gregh3285, Zanetu, [Link], Model Math, Tawkerbot2, CRGreathouse, HenningThielemann, Myasuda,
MaxEnt, Mon4, Joh5n, Nilisco, TomyDuby, Doctahdrey, El bot de la dieta, Diophantine, Virginia-American, Bryant124, Addbot, Luckas-
bot, Yobot, ArthurBot, Liorma, Raulshc, D'ohBot, Kalanchoea, Tttfkkk, Icakir, Onrandom, Deltahedron, SBareSSomErMig, Apnorton,
Gmkwo, Georey Lamont Critzer, InternetArchiveBot, MC1228, Rnd2000, Bhavinmoriya and Anonymous: 45

9.2 Images
File:[Link] Source: [Link] License: CC0 Contributors: en:File:
Free-to-read_lock_75.svg Original artist: User:Trappist the monk
File:OEISicon_light.svg Source: [Link] License: Public do-
main Contributors: Own work Original artist: <a href='//[Link]/wiki/File:[Link]' class='image'><img
alt='[Link]' src='[Link]
width='40' height='46' srcset='[Link]
1.5x, [Link] 2x' data-le-width='703'
data-le-height='806' /></a> Watchduck (a.k.a. Tilman Piesk)

9.3 Content license

Creative Commons Attribution-Share Alike 3.0