Carmichael function

from Wikipedia, the free encyclopedia
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:

each holds, the prime to be. In group-theoretic way of speaking is the torsion group of the (prime) residue class group .

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 .

calculation

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

The stand for pairwise different prime numbers and those for positive whole numbers.

The following formula comes to the same result:

Let be the prime factorization of (with , if even):

  • if
  • if

Here called the Euler's φ function . The following applies to powers of odd prime numbers

example

applies to all who are relatively prime to the number 15.

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 .

  • Euler's φ function:
  • Carmichael function:

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:

also

.

For a Carmichael number , the number is

so completely, and it applies to all to be coprime

.

See also

Web links