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)}$