Ordine moltiplicativo

Da Wikipedia, l'enciclopedia libera.

In teoria dei numeri, dati un intero a ed 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

ak ≡ 1 (modulo n).

L'ordine di a modulo n è generalmente indicato con ordn(a), oppure On(a).

Per esempio, per determinare l'ordine moltiplicativo di 4 modulo 7, calcoliamo 42 = 16 ≡ 2 (modulo 7) e 43 ≡ 4×2 = 8 ≡ 1 (modulo 7), quindi ord7(4) = 3.

Questa nozione è un caso di quella più generale di ordine degli elementi di un gruppo: se (G, *) è un gruppo scritto con la comune notazione moltiplicativa (in modo che at rappresenti il prodotto a * a * ... * a ripetuto t volte), l'ordine di un elemento a di G è il minimo intero positivo k tale che ak=e (dove e denota l'elemento neutro di G). Premesso ciò, l'ordine moltiplicativo di un numero a modulo n non è altro che l'ordine di a nel gruppo U(n), i cui elementi sono i residui modulo n dei numeri coprimi con n, sotto l'operazione di moltiplicazione modulo n. Questo è il gruppo delle unità dell'anello Zn; esso è composto da φ(n) elementi, dove φ è la Funzione totiente di Eulero.

Come conseguenza del teorema di Lagrange, ordna è sempre un divisore di φ(n). Se in particolare ordn 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.

Non tutti i numeri n posseggono un generatore in modulo n, ma tutti i numeri primi lo posseggono. 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.

Voci correlate[modifica | modifica sorgente]

matematica Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica