OliForum Matematico

Siano $ n\in\mathbb{N}_0 $ ed $ a\in\mathbb{Z} $. Se $ \gcd(a,n) = 1 $, il teorema di Euler-Fermat garantisce l'esistenza di un qualche $ u\in\mathbb{N}_0 $ tale che: $ a^u \equiv 1 \bmod n $. In tal senso, è sufficiente assumere infatti $ u := \varphi(n) $, ove $ \varphi(\cdot) $ rappresenta la totiente di Eulero. Ergo, l'insieme $ \mathcal{E}_n := \{u\in\mathbb{N}_0: a^u \equiv 1 \bmod n\} $ è non vuoto, poiché almeno $ \varphi(n) \in \mathcal{E}_n $.

Del resto, $ \mathcal{E}_n $ è banalmente un sottoinsieme di $ \mathbb{N} $, e in quanto tale possiede (in accordo al principio del buon ordine dei naturali) un elemento minimo assoluto (peraltro unico). Ebbene, posto $ \omega := \min(\mathcal{E}_n) $, si dice che $ \omega $ rappresenta l'ordine (moltiplicativo) di $ n $ alla base $ a $, e si denota con $ \mbox{ord}_n(a) $, ovvero il gaussiano di $ n $ alla base $ a $, e si indica con $ \mbox{gss}(n,a) $.

Un proof dell'esistenza dell'ordine moltiplicativo indipendente dal teorema di Euler-Fermat, nel caso di un modulo primo, si può trovare cliccando qui. Adattarla al caso di un modulo qualsiasi non vi sarà difficile! Inoltre, siccome HumanT ha avviato altrove un certo dibattito, colgo l'occasione per aggiungere al glossario il seguente:

Teorema #1: siano $ a\in\mathbb{Z} $ e $ p\in\mathfrak{P} $ tali che $ p \nmid a $. Se dunque $ n\in\mathbb{N} $ ed $ a^n \equiv 1 \bmod p $, necessariamente $ \mbox{ord}_p(a) \mid n $.

Dim.: per il teorema della divisione, essendo $ \mbox{ord}_p(a) > 0 $, esistono (univocamente determinati) $ q, r \in\mathbb{N} $, con $ 0 \leq r < \mbox{ord}_p(a) $ tali che $ n = q\cdot \mbox{ord}_p(a) + r $. E allora: $ 1 \equiv a^n \equiv a^{q \cdot \mbox{ord}_p(a) + r} \equiv $ $ {(a^{\mbox{ord}_p(a)})^q \cdot a^r \equiv a^r \bmod p $. Tuttavia, $ \mbox{ord}_p(a) $ rappresenta per definizione l'elemento minimo dell'insieme $ \{x\in\mathbb{N}_0: a^x \equiv 1 \bmod p\} $. Ergo, siccome $ 0 \leq r < \mbox{ord}_p(a) $ ed $ a^r \equiv 1 \bmod p $, necessariamente $ r = 0 $, e dunque $ n = q \cdot \mbox{ord}_p(a) $. Di qui la tesi, q.e.d.

In particolare, allora: $ \mbox{ord}_p(a) \mid (p-1) $. Capito, HumanTorch?

Lo stesso teorema si può poi adattare, chiaramente, al caso in cui il modulo non sia un numero primo.