Funzione di Carmichael
In matematica, e in particolare nella teoria dei numeri, la funzione di Carmichael
λ
(
n
)
{\displaystyle \lambda (n)}
è una funzione aritmetica che prende nome dal matematico statunitense Robert Daniel Carmichael (1879-1967).
== Definizione ==
La funzione di Carmichael associa a ogni intero positivo
n
{\displaystyle n}
un intero positivo
λ
(
n
)
{\displaystyle \lambda (n)}
, definito come il più piccolo intero positivo
m
{\displaystyle m}
tale che
a
m
≡
1
(
mod
n
)
{\displaystyle a^{m}\equiv 1{\pmod {n}}}
per ogni intero
a
{\displaystyle a}
coprimo con
n
.
{\displaystyle n.}
== Calcolo della funzione di Carmichael ==
Sia
n
{\displaystyle n}
intero positivo e sia
n
=
p
1
a
1
⋅
…
⋅
p
r
a
r
{\displaystyle n=p_{1}^{a_{1}}\cdot \ldots \cdot p_{r}^{a_{r}}}
la fattorizzazione in primi di
n
{\displaystyle n}
. Si ha:
λ
(
n
)
=
mcm
(
λ
(
p
1
a
1
)
,
λ
(
p
2
a
2
)
,
…
,
λ
(
p
k
a
k
)
)
,
{\displaystyle \lambda (n)=\operatorname {mcm} {\big (}\lambda (p_{1}^{a_{1}}),\lambda (p_{2}^{a_{2}}),\ldots ,\lambda (p_{k}^{a_{k}}){\big )},}
dove
mcm
{\displaystyle \operatorname {mcm} }
indica il minimo comune multiplo in
Z
{\displaystyle \mathbb {Z} }
.
Il teorema di Carmicheal indica come calcolare
λ
(
n
)
{\displaystyle \lambda (n)}
se
n
=
p
k
,
{\displaystyle n=p^{k},}
con
p
{\displaystyle p}
primo e
k
{\displaystyle k}
intero positivo:
λ
(
p
k
)
=
{
1
2
φ
(
p
k
)
se
p
=
2
e
k
≥
3
,
φ
(
p
k
)
altrimenti,
{\displaystyle \lambda (p^{k})={\begin{cases}{\tfrac {1}{2}}\varphi (p^{k})&{\text{se }}p=2{\text{ e }}k\geq 3,\\\varphi (p^{k})&{\text{altrimenti,}}\end{cases}}}
dove
φ
{\displaystyle \varphi }
è la funzione φ di Eulero che per una potenza di un primo è data da:
φ
(
p
k
)
=
p
k
−
1
(
p
−
1
)
.
{\displaystyle \varphi (p^{k})=p^{k-1}(p-1).}
== Proprietà ==
Sia
φ
{\displaystyle \varphi }
la funzione φ di Eulero, si ha che
λ
(
n
)
{\displaystyle \lambda (n)}
è un divisore di
φ
(
n
)
{\displaystyle \varphi (n)}
.
Si ha che
λ
(
n
)
{\displaystyle \lambda (n)}
è l'esponente (minimo comune multiplo degli ordini degli elementi) del gruppo delle unità, ossia del (gruppo moltiplicativo degli elementi invertibili) di
Z
/
n
Z
{\displaystyle \mathbb {Z} /n\mathbb {Z} }
.
== Voci correlate ==
Minimo comune multiplo
Numero di Carmichael
Numero primo
Funzione φ di Eulero
== Altri progetti ==
Wikimedia Commons contiene immagini o altri file su Funzione di Carmichael
== Collegamenti esterni ==
(EN) Eric W. Weisstein, Carmichael Function, su MathWorld, Wolfram Research.