Versione delle 09:55, 25 lug 2018 modifica IrishBot (discussione \| contributi) Bot, Bot con diritti di amministratore 966 966 modifiche m Bot: orfanizzo redirect Funzione di Eulero ← Differenza precedente		Versione delle 16:34, 21 mar 2019 modifica annulla Gggg100 (discussione \| contributi) 6 modifiche correzione della definizione e del calcolo della funzione di Carmicheal, fonte pagina in inglese e Wolframalpha Etichetta: Modifica visuale: commutato Differenza successiva →
Riga 4: == Definizione == In [[Teoria dei numeri]], la '''funzione di Carmichael''' associa a ogni [[Numero naturale \|intero positivo]] ''n'', un intero positivo <math>\lambda(n)</math>, definito come il più piccolo intero positivo ''m'' tale che :<math>a^m \equiv 1 \pmod{n}</math>▼ == Calcolare <math>\lambda(n)</math> con il Teorema di Carmichael == Sia <math>n\in\mathbb{N}\backslash\left\{0\right\}</math> e sia <math>n=p_1^{a_1}\cdot\ldots\cdot p_r^{a_r}</math> la [[fattorizzazione]] in [[fattore primo\|primi]] di <math>n</math>. Si ha: :<math> ~~<math>\lambda\ :\ \mathbb{N}\backslash\left\{0\right\}\ \rightarrow\ \mathbb{Z}</math>~~ \lambda(n) = \operatorname{mcm}\big(\lambda(p_1^{a_1}),\,\lambda(p_2^{a_2}),\,\ldots,\,\lambda(p_k^{a_k}) \big). </math> dove ''mcm'' indica il [[minimo comune multiplo]] in <math>\mathbb{Z}</math> ~~e <math>\varphi</math> la [[funzione φ di Eulero]]~~.▼ ~~<math>\lambda(n):=\text{mcm}(\left\{\varphi(p_i^{a_i})\right\})</math>~~ '''Il teorema di Carmicheal''' spiega come calcolare ''λ'' di una potenza di un numero primo: per una potenza di un primo dispari e per 2 e 4, ''λ''(''n'') e uguale alla [[funzione φ di Eulero]] ''φ''(''n''); per le potenze di due maggiori di 4 è uguale a metà della funzione di Eulero. ▲dove ''mcm'' indica il [[minimo comune multiplo]] in <math>\mathbb{Z}</math> e <math>\varphi</math> la [[funzione φ di Eulero]]. :<math>\lambda(n) = Dunque, <math>\lambda(n)</math> è l'''esponente'' (minimo comune multiplo degli ''ordini'' o ''periodi'' degli [[Elemento_(insiemistica)\|elementi]]) del ''gruppo delle unità'' ([[gruppo (matematica)\|gruppo]] moltiplicativo degli elementi [[Elemento_invertibile#Elementi_invertibili\|invertibili]]) di <math>\mathbb{Z}_n</math>.▼ \begin{cases} \;\;\varphi(n) &\mbox{if }n = 2,3,4,5,6,7,9,10,11,13,14,17,18,19,22,23,25,26,27,29,31,34,\dots\\ \tfrac12\varphi(n)&\text{if }n=8,16,32,64,128,256,\dots \end{cases} </math> ~~== Teorema di Carmichael ==~~ Sia <math>n</math> un [[numero intero]] [[numero dispari\|dispari]], sia <math>a</math> un intero [[coprimo]] con <math>n</math>. Si ha allora che la funzione di Carmichael di <math>n</math> è il più piccolo [[numero intero positivo]] <math>m</math> tale che: La funzione di Eulero di una potenza di un primo è data da ▲<math>a^m\equiv 1\pmod{n}</math> :<math> \varphi(p^r) = p^{r-1}(p-1).\; </math> ▲Dunque, <math>\lambda(n)</math> è l'''esponente'' (minimo comune multiplo degli ''ordini'' o ''periodi'' degli [[Elemento_(insiemistica)\|elementi]]) del ''gruppo delle unità'' ([[gruppo (matematica)\|gruppo]] moltiplicativo degli elementi [[Elemento_invertibile#Elementi_invertibili\|invertibili]]) di <math>\mathbb{Z}_n</math>. == Proprietà ==

Funzione di Carmichael: differenze tra le versioni