Funzione di Carmichael

In matematica, e in particolare nella teoria dei numeri, la funzione di Carmichael ${\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 ${\displaystyle n}$ un intero positivo ${\displaystyle \lambda (n)}$, definito come il più piccolo intero positivo ${\displaystyle m}$ tale che

${\displaystyle a^{m}\equiv 1{\pmod {n}}}$

per ogni intero ${\displaystyle a}$ coprimo con ${\displaystyle n.}$

Calcolo della funzione di Carmichael

Sia ${\displaystyle n}$ intero positivo e sia ${\displaystyle n=p_{1}^{a_{1}}\cdot \ldots \cdot p_{r}^{a_{r}}}$ la fattorizzazione in primi di ${\displaystyle n}$. Si ha:

${\displaystyle \lambda (n)=\operatorname {mcm} {\big (}\lambda (p_{1}^{a_{1}}),\lambda (p_{2}^{a_{2}}),\ldots ,\lambda (p_{k}^{a_{k}}){\big )},}$

dove ${\displaystyle \operatorname {mcm} }$ indica il minimo comune multiplo in ${\displaystyle \mathbb {Z} }$.

Il teorema di Carmicheal indica come calcolare ${\displaystyle \lambda (n)}$ se ${\displaystyle n=p^{k},}$ con ${\displaystyle p}$ primo e ${\displaystyle k}$ intero positivo:

${\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:

${\displaystyle \varphi (p^{k})=p^{k-1}(p-1).}$

Proprietà

Sia ${\displaystyle \varphi }$ la funzione φ di Eulero, si ha che ${\displaystyle \lambda (n)}$ è un divisore di ${\displaystyle \varphi (n)}$.

Si ha che ${\displaystyle \lambda (n)}$ è l'esponente (minimo comune multiplo degli ordini degli elementi) del gruppo delle unità, ossia del (gruppo moltiplicativo degli elementi invertibili) di ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$.

Voci correlate

• Minimo comune multiplo
• Numero di Carmichael
• Numero primo
• Funzione φ di Eulero

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su Funzione di Carmichael

Collegamenti esterni

• (EN) Eric W. Weisstein, Funzione di Carmichael, su MathWorld, Wolfram Research.