# Carmichael function

Values ​​of the Carmichael function λ (black) and the Euler φ function (red) for the first 356 numbers. The point ( nλ (n) ) is two-colored if λ (n) = φ (n)

The Carmichael function from the field of mathematics is a number theoretic function that determines the smallest of every natural number n , so that: ${\ displaystyle m =: \ lambda (n)}$

${\ displaystyle g ^ {m} \ equiv 1 {\ bmod {n}}}$

each holds, the prime to be. In group-theoretic way of speaking is the torsion group of the (prime) residue class group . ${\ displaystyle g}$${\ displaystyle n}$${\ displaystyle \ lambda (n)}$ ${\ displaystyle (\ mathbb {Z} / n \ mathbb {Z}) ^ {\ times}}$

The Carmichael function goes back to the mathematician Robert Daniel Carmichael . It is the maximum period length of the fraction in its -adic representations and plays a role in prime numbers and Fermat's pseudoprime numbers . ${\ displaystyle 1 / n}$${\ displaystyle g}$

## calculation

The Carmichael function can be calculated according to the following scheme:

{\ displaystyle {\ begin {aligned} \ lambda (1) & = 1 \\\ lambda (2) & = 1 \\\ lambda (4) & = 2 \\ lambda (2 ^ {k}) & = 2 ^ {k-2} \ quad \ mathrm {f {\ ddot {u}} r} \ k> 2 \\\ lambda (p ^ {k}) & = p ^ {k-1} \ cdot (p -1) \ quad \ mathrm {f {\ ddot {u}} r} \ p \ geq 3 \ \ mathrm {prim}, k> 0 \\\ lambda (p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} \ cdot \ cdot \ cdot p_ {s} ^ {k_ {s}}) & = \ operatorname {kgV} {\ bigl (} \ lambda (p_ {1} ^ {k_ {1}}), \ lambda (p_ {2} ^ {k_ {2}}), ..., \ lambda (p_ {s} ^ {k_ {s}}) {\ bigr)} \ end {aligned }}}

The stand for pairwise different prime numbers and those for positive whole numbers. ${\ displaystyle p_ {i}}$${\ displaystyle k_ {i}}$

The following formula comes to the same result:

Let be the prime factorization of (with , if even): ${\ displaystyle m = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} \ cdot \ cdot \ cdot p_ {s} ^ {k_ {s}}}$${\ displaystyle m \ in \ mathbb {N}}$${\ displaystyle p_ {1} = 2}$${\ displaystyle m}$

• ${\ displaystyle \ lambda (m) = \ operatorname {kgV} {\ bigl (} \ varphi (p_ {1} ^ {k_ {1}}), \ varphi (p_ {2} ^ {k_ {2}}) , ..., \ varphi (p_ {s} ^ {k_ {s}}) {\ bigr)}}$ if ${\ displaystyle m \ not \ equiv 0 {\ bmod {8}}}$
• ${\ displaystyle \ lambda (m) = \ operatorname {kgV} {\ bigl (} \ varphi (p_ {1} ^ {k_ {1}}) / 2, \ varphi (p_ {2} ^ {k_ {2} }), ..., \ varphi (p_ {s} ^ {k_ {s}}) {\ bigr)}}$ if ${\ displaystyle m \ equiv 0 {\ bmod {8}}}$

Here called the Euler's φ function . The following applies to powers of odd prime numbers${\ displaystyle \ varphi (x)}$${\ displaystyle p}$${\ displaystyle \ lambda (p ^ {k}) = \ varphi (p ^ {k})}$

## example

${\ displaystyle \ lambda (15) = \ lambda (3 \ cdot 5) = \ operatorname {kgV} {\ bigl (} \ varphi (3), \ varphi (5) {\ bigr)} = \ operatorname {kgV} {\ bigl (} 2,4 {\ bigr)} = 4}$
${\ displaystyle g ^ {4} \ equiv 1 {\ bmod {1}} 5}$applies to all who are relatively prime to the number 15.${\ displaystyle g}$

## The Carmichael function and Euler's φ function

For the numbers one, two, four, for every odd prime power and for all doubles of odd prime powers, the Carmichael function and Euler's φ function are identical. If and only then do primitive roots also exist modulo . In general, both functions are different; is always a factor of . ${\ displaystyle \ lambda (n) = \ varphi (n)}$${\ displaystyle n}$${\ displaystyle \ lambda (n)}$${\ displaystyle \ varphi (n)}$

• Euler's φ function:
${\ displaystyle \ varphi (105) = \ varphi (3 \ cdot 5 \ cdot 7) = \ varphi (3) \ cdot \ varphi (5) \ cdot \ varphi (7) = 2 \ cdot 4 \ cdot 6 = 48 }$
• Carmichael function:
${\ displaystyle \ lambda (105) = \ lambda (3 \ cdot 5 \ cdot 7) = \ operatorname {kgV} {\ bigl (} \ varphi (3), \ varphi (5), \ varphi (7) {\ bigr)} = \ operatorname {kgV} {\ bigl (} 2,4,6 {\ bigr)} = 12}$

## The Carmichael Function and the Carmichael Number

Since the Carmichael function determines the smallest for every natural number , so that for everything that is relatively prime and the difference is divisible by for every Carmichael number , it follows from: ${\ displaystyle n}$${\ displaystyle m = \ lambda (n)}$${\ displaystyle g ^ {m} \ equiv 1 {\ bmod {n}}}$${\ displaystyle g \}$${\ displaystyle n \}$ ${\ displaystyle c}$${\ displaystyle c-1 \}$${\ displaystyle \ lambda (c)}$

${\ displaystyle g ^ {\ lambda (c)} \ equiv 1 {\ bmod {c}}}$

also

${\ displaystyle g ^ {c-1} \ equiv 1 {\ bmod {c}}}$.

For a Carmichael number , the number is ${\ displaystyle c}$

${\ displaystyle d: = {\ tfrac {c-1} {\ lambda (c)}}}$

so completely, and it applies to all to be coprime${\ displaystyle c}$${\ displaystyle g}$

${\ displaystyle g ^ {c-1} = g ^ {\ lambda (c) \ cdot d} \ equiv 1 {\ bmod {c}}}$.