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 modifica

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$ ).