Cerco di commentare la tua dimostrazione, HumanTorch, al solo scopo di renderla più leggibile: non volermene se te lo dico, maaa... scrivi davvero coi piedi.
E' un'opinione personale, non darle troppo peso! Dunque, maniche in su...
HumanTorch ha scritto:Per assurdo supponiamo che non ci siano $ a,p $ con tali proprietà; siano tali residui $ r_i $, ovviamente tutti diversi da $ 1 $; ad un certo punto, dovendo essere si $ >1 $ ma anche $ <p $, per il principio dei piccioni nei cassetti o pigeonhole che dir si voglia, si avrà un resto $ r_g=r_f $ dove $ r_f $ si è già incontrato nella precedente successione; ma allora il residuo precedente deve essere uguale a quello che precede $ r_f $ e così via (questo perche ottenuti moltiplicando per lo stesso fattore $ a $); quindi si giungerà a un resto $ r_t $ uguale a $ 1 $ ma dato da un esponente diverso da $ 0 $ (che noi chiameremo appunto $ t $) poichè fra $ r_g $ e $ r_f $ ci saranno sicuramente altri residui (non so se mi sono spiegato..)
Supponiamo ch'esistano $ p\in\mathfrak{P} $ ed $ a\in\mathbb{Z} $, con $ \gcd(a,p) = 1 $, tali che: $ a^k \not\equiv 1 \bmod p $, per ogni $ k = 1, 2, \ldots, p-1 $. Del resto, siccome $ a $ è coprimo con $ p $, nondimeno $ a^k \not\equiv 0 \bmod p $, qual che sia $ k = 1, 2, \ldots, p-1 $. Detto dunque $ r_k $ il resto della divisione intera di $ a^k $ per $ p $, quando $ k = 1, 2, \ldots, p-1 $, può dedursi dal principio dei cassetti ch'esistono $ f, g = 1, 2, \ldots, p-1 $, con $ f < g $, tali che $ r_f = r_g $. E allora $ a^f \equiv a^g \bmod p $, ovvero $ a^{g-f} \equiv 1 \bmod p $, come consegue dal lemma di Euclide stante che $ \gcd(a^f,p) = 1 $. Ne risulta provata l'esistenza di un intero $ t > 0 $, essendo $ x := g - f $, per cui $ a^x \equiv 1 \bmod p $, di contro l'assunto iniziale. Ne segue che, comunque scelti $ p\in\mathfrak{P} $ ed $ a\in\mathbb{Z} $, con $ \gcd(a,p) = 1 $, l'insieme $ \Omega := \{x\in\mathbb{N}_0: a^x \equiv 1 \bmod p\} $ è non vuoto, e come tale possiede elemento minimo. Si ponga $ t := \min \Omega $ per dedurne con lineare semplicità il seguente risultato notevole:
Se $ p\in\mathfrak{P} $, $ a\in\mathbb{Z} $ e $ p\nmid a $, esiste allora un intero minimale $ t > 0 $ tale che: $ a^t \equiv 1 \bmod p $. Si dice che $ t $ rappresenta l'ordine moltiplicativo di $ p $ alla base $ a $, e si denota fra l'altro con $ \mbox{ord}_p(a) $.
In proposito, consiglio pure di dare un'occhiatina
qui. In effetti, la discussione che abbiamo portato avanti in questo
thread andrebbe spostata di là, giusto per ragioni d'
ordine pubblico!