TdN: dell'ordine moltiplicativo di un intero a una data base

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

TdN: dell'ordine moltiplicativo di un intero a una data base

Messaggio da HiTLeuLeR » 05 mar 2005, 14:25

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

Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR » 19 giu 2005, 09:23

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.

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

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

Rispondi