Ordine moltiplicativo

Template:F 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(\mathrm{mod}n).$

L'ordine di $a$ modulo $n$ è generalmente indicato con ${\mathrm{o}\mathrm{r}\mathrm{d}}_n(a)$, oppure $O_n(a)$.

Per esempio, per determinare l'ordine moltiplicativo di $4$ modulo $7$, calcoliamo $4^2=16\equiv 2(\mathrm{mod}7)$ e $4^3=4^2\cdot 4\equiv 2\cdot 4\equiv 8\equiv 1(\mathrm{mod}7)$, quindi ${\mathrm{o}\mathrm{r}\mathrm{d}}_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\dots$ 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{o}\mathrm{r}\mathrm{d}}_n(a)$ è sempre un divisore di φ(n). Se in particolare ${\mathrm{o}\mathrm{r}\mathrm{d}}_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\ge 2$ intero. Se $a\equiv b(\mathrm{mod}n)$, allora ${\mathrm{o}\mathrm{r}\mathrm{d}}_n(a)={\mathrm{o}\mathrm{r}\mathrm{d}}_n(b)$.
• Siano $a,b,m\in \mathbb{Z},m\ge 1,n\ge 2$ intero. Allora:

(a) ${\mathrm{o}\mathrm{r}\mathrm{d}}_n(a^m)=\frac{{\mathrm{o}\mathrm{r}\mathrm{d}}_n(a)}{({\mathrm{o}\mathrm{r}\mathrm{d}}_n(a),m)}$, dove con $(a,b)$ si intende il massimo comune divisore tra $a$ e $b;$

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

(c) se $({\mathrm{o}\mathrm{r}\mathrm{d}}_n(a),{\mathrm{o}\mathrm{r}\mathrm{d}}_n(b))=1$, allora ${\mathrm{o}\mathrm{r}\mathrm{d}}_n(a\cdot b)={\mathrm{o}\mathrm{r}\mathrm{d}}_n(a)\cdot {\mathrm{o}\mathrm{r}\mathrm{d}}_n(b);$

(d) se $n,m\ge 2$ sono due interi coprimi e $a\in \mathbb{Z}$ è coprimo con $m\cdot n$, allora ${\mathrm{o}\mathrm{r}\mathrm{d}}_{m\cdot n}(a)=[{\mathrm{o}\mathrm{r}\mathrm{d}}_m(a),{\mathrm{o}\mathrm{r}\mathrm{d}}_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\ge 1,n\ge 2$ e $(a,n)=1$. Allora

$a^h\equiv a^k(\mathrm{mod}n)\iff h\equiv k(\mathrm{mod}{\mathrm{o}\mathrm{r}\mathrm{d}}_n(a)).$

Da quest'ultima proprietà discende che

$a^h\equiv a^r(\mathrm{mod}n),$

dove $r$ è il resto della divisione di $h$ per ${\mathrm{o}\mathrm{r}\mathrm{d}}_n(a).$

Voci correlate

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

Collegamenti esterni

• Template:Collegamenti esterni