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:
m
=:
λ
(
n
)
{\ displaystyle m =: \ lambda (n)}
G
m
≡
1
mod
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 .
G
{\ displaystyle g}
n
{\ displaystyle n}
λ
(
n
)
{\ displaystyle \ lambda (n)}
(
Z
/
n
Z
)
×
{\ 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 .
1
/
n
{\ displaystyle 1 / n}
G
{\ displaystyle g}
calculation
The Carmichael function can be calculated according to the following scheme:
λ
(
1
)
=
1
λ
(
2
)
=
1
λ
(
4th
)
=
2
λ
(
2
k
)
=
2
k
-
2
f
u
¨
r
k
>
2
λ
(
p
k
)
=
p
k
-
1
⋅
(
p
-
1
)
f
u
¨
r
p
≥
3
p
r
i
m
,
k
>
0
λ
(
p
1
k
1
p
2
k
2
⋅
⋅
⋅
p
s
k
s
)
=
LCM
(
λ
(
p
1
k
1
)
,
λ
(
p
2
k
2
)
,
.
.
.
,
λ
(
p
s
k
s
)
)
{\ 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.
p
i
{\ displaystyle p_ {i}}
k
i
{\ displaystyle k_ {i}}
The following formula comes to the same result:
Let be the prime factorization of (with , if even):
m
=
p
1
k
1
p
2
k
2
⋅
⋅
⋅
p
s
k
s
{\ displaystyle m = p_ {1} ^ {k_ {1}} p_ {2} ^ {k_ {2}} \ cdot \ cdot \ cdot p_ {s} ^ {k_ {s}}}
m
∈
N
{\ displaystyle m \ in \ mathbb {N}}
p
1
=
2
{\ displaystyle p_ {1} = 2}
m
{\ displaystyle m}
λ
(
m
)
=
LCM
(
φ
(
p
1
k
1
)
,
φ
(
p
2
k
2
)
,
.
.
.
,
φ
(
p
s
k
s
)
)
{\ displaystyle \ lambda (m) = \ operatorname {kgV} {\ bigl (} \ varphi (p_ {1} ^ {k_ {1}}), \ varphi (p_ {2} ^ {k_ {2}}) , ..., \ varphi (p_ {s} ^ {k_ {s}}) {\ bigr)}}
if
m
≢
0
mod
8th
{\ displaystyle m \ not \ equiv 0 {\ bmod {8}}}
λ
(
m
)
=
LCM
(
φ
(
p
1
k
1
)
/
2
,
φ
(
p
2
k
2
)
,
.
.
.
,
φ
(
p
s
k
s
)
)
{\ displaystyle \ lambda (m) = \ operatorname {kgV} {\ bigl (} \ varphi (p_ {1} ^ {k_ {1}}) / 2, \ varphi (p_ {2} ^ {k_ {2} }), ..., \ varphi (p_ {s} ^ {k_ {s}}) {\ bigr)}}
if
m
≡
0
mod
8th
{\ displaystyle m \ equiv 0 {\ bmod {8}}}
Here called the Euler's φ function . The following applies to powers of odd prime numbers
φ
(
x
)
{\ displaystyle \ varphi (x)}
p
{\ displaystyle p}
λ
(
p
k
)
=
φ
(
p
k
)
{\ displaystyle \ lambda (p ^ {k}) = \ varphi (p ^ {k})}
example
λ
(
15th
)
=
λ
(
3
⋅
5
)
=
LCM
(
φ
(
3
)
,
φ
(
5
)
)
=
LCM
(
2
,
4th
)
=
4th
{\ displaystyle \ lambda (15) = \ lambda (3 \ cdot 5) = \ operatorname {kgV} {\ bigl (} \ varphi (3), \ varphi (5) {\ bigr)} = \ operatorname {kgV} {\ bigl (} 2,4 {\ bigr)} = 4}
G
4th
≡
1
mod
1
5
{\ displaystyle g ^ {4} \ equiv 1 {\ bmod {1}} 5}
applies to all who are relatively prime to the number 15.
G
{\ 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 .
λ
(
n
)
=
φ
(
n
)
{\ displaystyle \ lambda (n) = \ varphi (n)}
n
{\ displaystyle n}
λ
(
n
)
{\ displaystyle \ lambda (n)}
φ
(
n
)
{\ displaystyle \ varphi (n)}
Euler's φ function:
φ
(
105
)
=
φ
(
3
⋅
5
⋅
7th
)
=
φ
(
3
)
⋅
φ
(
5
)
⋅
φ
(
7th
)
=
2
⋅
4th
⋅
6th
=
48
{\ 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:
λ
(
105
)
=
λ
(
3
⋅
5
⋅
7th
)
=
LCM
(
φ
(
3
)
,
φ
(
5
)
,
φ
(
7th
)
)
=
LCM
(
2
,
4th
,
6th
)
=
12
{\ 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:
n
{\ displaystyle n}
m
=
λ
(
n
)
{\ displaystyle m = \ lambda (n)}
G
m
≡
1
mod
n
{\ displaystyle g ^ {m} \ equiv 1 {\ bmod {n}}}
G
{\ displaystyle g \}
n
{\ displaystyle n \}
c
{\ displaystyle c}
c
-
1
{\ displaystyle c-1 \}
λ
(
c
)
{\ displaystyle \ lambda (c)}
G
λ
(
c
)
≡
1
mod
c
{\ displaystyle g ^ {\ lambda (c)} \ equiv 1 {\ bmod {c}}}
also
G
c
-
1
≡
1
mod
c
{\ displaystyle g ^ {c-1} \ equiv 1 {\ bmod {c}}}
.
For a Carmichael number , the number is
c
{\ displaystyle c}
d
: =
c
-
1
λ
(
c
)
{\ displaystyle d: = {\ tfrac {c-1} {\ lambda (c)}}}
so completely, and it applies to all to be coprime
c
{\ displaystyle c}
G
{\ displaystyle g}
G
c
-
1
=
G
λ
(
c
)
⋅
d
≡
1
mod
c
{\ displaystyle g ^ {c-1} = g ^ {\ lambda (c) \ cdot d} \ equiv 1 {\ bmod {c}}}
.
See also
Web links
<img src="https://de.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">