Ordine moltiplicativo

Questa voce o sezione sull'argomento matematica non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. Segui i suggerimenti del progetto di riferimento.

In teoria dei numeri, dati un intero ${\displaystyle a}$ e un intero positivo ${\displaystyle n}$ il cui massimo comune divisore sia 1, l'ordine moltiplicativo di ${\displaystyle a}$ modulo ${\displaystyle n}$ è il più piccolo intero positivo ${\displaystyle k}$ tale che

${\displaystyle a^{k}\equiv 1{\pmod {n}}.}$

L'ordine di ${\displaystyle a}$ modulo ${\displaystyle n}$ è generalmente indicato con ${\displaystyle \mathrm {ord} _{n}(a)}$, oppure ${\displaystyle O_{n}(a)}$.

Per esempio, per determinare l'ordine moltiplicativo di ${\displaystyle 4}$ modulo ${\displaystyle 7}$, calcoliamo ${\displaystyle 4^{2}=16\equiv 2{\pmod {7}}}$ e ${\displaystyle 4^{3}=4^{2}\cdot 4\equiv 2\cdot 4\equiv 8\equiv 1{\pmod {7}}}$, quindi ${\displaystyle \mathrm {ord} _{7}(4)=3}$.

Questa nozione è un caso di quella più generale di ordine degli elementi di un gruppo: se ${\displaystyle (G,*)}$ è un gruppo scritto con in notazione moltiplicativa (in modo che ${\displaystyle a^{t}}$ rappresenti il prodotto ${\displaystyle a\cdot a\cdot a\ldots }$ ripetuto ${\displaystyle t}$ volte), l'ordine di un elemento ${\displaystyle a}$ di ${\displaystyle G}$ è il minimo intero positivo ${\displaystyle k}$ tale che ${\displaystyle a^{k}=e}$ (dove ${\displaystyle e}$ denota l'elemento neutro di ${\displaystyle G}$). L'ordine moltiplicativo di un numero ${\displaystyle a}$ modulo ${\displaystyle n}$ non è altro che l'ordine di ${\displaystyle a}$ nel gruppo ${\displaystyle U(n)}$, i cui elementi sono le classi resto modulo ${\displaystyle n}$ dei numeri coprimi con ${\displaystyle n}$, rispetto all'operazione di moltiplicazione modulo ${\displaystyle n}$. Questo è il gruppo delle unità dell'anello ${\displaystyle \mathbb {Z} /n\mathbb {Z} }$; esso è composto da φ(n) elementi, dove φ è la funzione totiente di Eulero.

Come conseguenza del teorema di Lagrange, ${\displaystyle \mathrm {ord} _{n}(a)}$ è sempre un divisore di φ(n). Se in particolare ${\displaystyle \mathrm {ord} _{n}(a)}$ è uguale a φ(n) e, quindi, più grande possibile, allora ${\displaystyle a}$ è chiamato generatore modulo ${\displaystyle n}$ Ciò implica che ${\displaystyle U(n)}$ è ciclico e la classe di residui di ${\displaystyle a}$ è un suo generatore.

Per ogni numero primo ${\displaystyle n}$ si ha che ${\displaystyle U(n)}$ è generato da un elemento, ma questo non è vero per ogni numero intero positivo. Se un numero ${\displaystyle n}$ ammette un generatore modulo ${\displaystyle n}$, allora ne esistono φ(φ(n)) distinti. Questo è un caso particolare di un'affermazione molto più generale sul numero di generatori dei gruppi ciclici.