Ordine moltiplicativo

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.

Proprietà fondamentali

Presentiamo ora alcune delle proprietà più importanti degli ordini moltiplicativi modulo ${\displaystyle n}$:

• Siano ${\displaystyle a,b\in \mathbb {Z} }$ e sia ${\displaystyle n\geq 2}$ intero. Se ${\displaystyle a\equiv b{\pmod {n}}}$, allora ${\displaystyle \mathrm {ord} _{n}(a)=\mathrm {ord} _{n}(b)}$.
• Siano ${\displaystyle a,b,m\in \mathbb {Z} ,m\geq 1,n\geq 2}$ intero. Allora:

(a) ${\displaystyle \mathrm {ord} _{n}(a^{m})={\frac {\mathrm {ord} _{n}(a)}{(\mathrm {ord} _{n}(a),m)}}}$, dove con ${\displaystyle (a,b)}$ si intende il massimo comune divisore tra ${\displaystyle a}$ e ${\displaystyle b;}$

(b) ${\displaystyle \mathrm {ord} _{n}(a)=\mathrm {ord} _{n}(a^{-1})}$, dove ${\displaystyle a^{-1}}$ è l'inverso moltiplicativo di ${\displaystyle a}$ modulo ${\displaystyle n;}$

(c) se ${\displaystyle (\mathrm {ord} _{n}(a),\mathrm {ord} _{n}(b))=1}$, allora ${\displaystyle \mathrm {ord} _{n}(a\cdot b)=\mathrm {ord} _{n}(a)\cdot \mathrm {ord} _{n}(b);}$

(d) se ${\displaystyle n,m\geq 2}$ sono due interi coprimi e ${\displaystyle a\in \mathbb {Z} }$ è coprimo con ${\displaystyle m\cdot n}$, allora ${\displaystyle \mathrm {ord} _{m\cdot n}(a)=[\mathrm {ord} _{m}(a),\mathrm {ord} _{n}(a)]}$ (dove con ${\displaystyle [a,b]}$ si intende il minimo comune multiplo tra ${\displaystyle a}$ e ${\displaystyle b}$).

• Siano ${\displaystyle a,h,k,n\in \mathbb {Z} ,h,k\geq 1,n\geq 2}$ e ${\displaystyle (a,n)=1}$. Allora

${\displaystyle a^{h}\equiv a^{k}{\pmod {n}}\Leftrightarrow h\equiv k{\pmod {\mathrm {ord} _{n}(a)}}.}$

Da quest'ultima proprietà discende che

${\displaystyle a^{h}\equiv a^{r}{\pmod {n}},}$

dove ${\displaystyle r}$ è il resto della divisione di ${\displaystyle h}$ per ${\displaystyle \mathrm {ord} _{n}(a).}$

Voci correlate

• Aritmetica modulare
• Radice primitiva modulo n
• Ordine di un elemento di un gruppo

Collegamenti esterni

• (EN) Eric W. Weisstein, Ordine moltiplicativo, su MathWorld, Wolfram Research.