Ordine moltiplicativo

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

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

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

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

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

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

Per ogni numero primo $n$ si ha che $U(n)$ è generato da un elemento, ma questo non è vero per ogni numero intero positivo. Se un numero $n$ ammette un generatore modulo $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 $n$:

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

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

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

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

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

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

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

Da quest'ultima proprietà discende che

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

dove $r$ è il resto della divisione di $h$ per $\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.