[N] An introduction to primitive roots.

Boll · Messaggio da **Boll** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-23 16:00, HiTLeuLeR wrote:
 PREMESSE: siano a, n € Z tali che: n > 1 e gcd(a, n) = 1. E allora, per il th. di Euler-Fermat: aphi(n) = 1 mod n, ove phi(·) denota, al solito, la totiente di Eulero. Ergo, l\'insieme X := {x € N0: ax = 1 mod n} è non vuoto. Del resto, per costruzione, X è un sottoinsieme di N, sicché, per il teorema del buon ordine, X ammette di certo un elemento minimo assoluto (peraltro, unico).
 
 Posto x0 := min(X), si dice che x0 rappresenta l\'ordine moltiplicativo di n alla base a, e si scrive orda(n), o equivalentemente il gaussiano di n alla base a, e si indica con gss(n,a).
 -------
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ma non è l\'ordine moltiplicativo di a alla base n??? Nel caso, credo che dovresti rivedere anche gli esercizi [ Questo Messaggio è stato Modificato da: Boll il 23-11-2004 16:21 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-23 16:17, Boll wrote:
 Ma non è l\'ordine moltiplicativo di a alla base n??? Nel caso, credo che dovresti rivedere anche gli esercizi.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 ...Eeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeeh?!?!?!?!?...
 
 
 \"No, Boll, direi proprio di no! Prova a prenderti a schiaffi, su... magari ti svegli un po\' e torni a vederci chiaro! In fondo, tentar non nuoce...\" - HiTLeuLeR <IMG SRC="images/forum/icons/icon_eek.gif">

talpuz · Messaggio da **talpuz** » 01 gen 1970, 01:33

in effetti sulla notazione c\'è un po\' di confusione...
 
 magari la notazione classica è quella, ma ad esempio il divin gobbino indica l\'ordine di a modulo m (cioè il minimo intero positivo k tale che ak==1 (m)) con ordm(a)
 
 è solo una questione di convenzioni, in ogni caso... la sostanza dei problemi non cambia <IMG SRC="images/forum/icons/icon_wink.gif">

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-23 17:01, talpuz wrote:
 in effetti sulla notazione c\'è un po\' di confusione...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Ma quale confusione, scusa? Mi pare di aver definito in modo chiaro ed inequivocabile la simbologia adottata nel testo dei miei problemi!!! Non vedo pertanto in che modo ci si possa confondere! Baaah, che blandizie...
 
 
 \"C.: «Giornata storta, Sa\'?!» S.: «Ma cosa te lo fa pensare?» C.: «No, niente, così... un\'impressione.» S.: «Beh, tu e le tue impressioni vedete di farvi i c***i vostri, intesi? Grazie!!!»\" - HiTLeuLeR durante il ciclo [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 23-11-2004 22:05 ]

Messaggio da **ma_go** » 01 gen 1970, 01:33

in effetti, euler, la notazione è ambigua, o quantomeno non-standard.
 anche se l\'hai definita due righe sopra, poco conta.
 il mio consiglio è di adeguarsi alla notazione gobbiniana (che tra l\'altro è più chiara e più diretta, almeno a parer mio).

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

N0 C0MM3NT!!!
 
 
 \"C\'è nel mio cuore più di quel che ho sulle labbra, c\'è nel mio desiderio più di quel che ho tra le mani.\" - Gibran Kahlil, Sabbia e schiuma

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-24 15:03, ma_go wrote:
 in effetti, euler, la notazione è ambigua, o quantomeno non-standard.
 anche se l\'hai definita due righe sopra, poco conta.
 il mio consiglio è di adeguarsi alla notazione gobbiniana (che tra l\'altro è più chiara e più diretta, almeno a parer mio).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Beh, a dire il vero ho cambiato idea... che uomo volubile, ve\'? Orbene, pensavo... e sì, qualche volta capita anche a me! Se magari, anziché affaticarti le dita e spendere soltanto parole vane, anche tu (l\'altro son io) ti concentrassi un po\' di più sulla risoluzione dei problemi, non credi che, in fondo, sarebbe molto più edificante e costruttivo per tutti? Magari, di questo passo, arriverai persino a suggerirmi di utilizzare preferenzialmente le lettere x, y, z per indicare le incognite di un\'equazione solo perché sulla massima parte dei testi in circolo è adottata questa sorta di convenzione del non-senso... Dai, ti prego, dimmi che riesci a trovarlo, per certi versi, persino ragionevole!!! Suuu, sii buono, levami pure quest\'ultimo dubbio...
 
 EDIT: non commettiate l\'errore di pensare che non amo le critiche, perché non è questo il caso, vogliate fidarvi! Le critiche vanno accolte, quando sono supportate dal buon senso. Tuttavia, in quanto alla circostanza attuale, beh... ho il diritto o no di ritenere che certi discorsi siano offensivi contro Dio e il decoro, uhm?
 
 
 \"E\' proprio vero quando si dice ch\'è sempre un piacere avere a che fare con persone mooolto più intelligenti di noi stessi...\" - HiTLeuLeR [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 25-11-2004 13:26 ]

Marco · Messaggio da **Marco** » 01 gen 1970, 01:33

Ciao.
 
 Beh, dato che ho contribuito (seppur indirettamente e involontariamente) alla nascita di questo thread, mi sembra giusto dare il mio piccolo apporto. La dimostrazione è forse lunghetta e probabilmente si può abbreviare qui e là. Spero di non aver scritto troppe castronerie. In caso contrario, so di poter contare sull\'amabile Hit per essere ricondotto sulla buona strada. So, here it goes...
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-11-23 16:00, HiTLeuLeR wrote:
 Problema 5: se p è un numero primo naturale > 2, a un intero primo con p e
 pr la massima potenza che divide a^orda(p) - 1, allora - essendo s € N0:
 orda(ps) = orda(p), se s <= r; orda(ps) = ps-r · orda(p), se s > r.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Notazione: per tagliare la testa al toro, denoto il minimo intero positivo k t.c. ak = 1 mod n, ord a mod n. Inoltre pq || n significa \"divide esattamente\" (i.e. pq è la massima potenza di p che divide n).
 
 
 Caso s <= r.
 
 Sia k = ord a mod p.
 
 k >= ord a mod ps; infatti ak = 1 (mod pr) ==> ak = 1 (mod ps).
 
 k <= ord a mod ps; infatti se ah = 1 (mod ps) ==> ah = 1 (mod p), e quindi h >= k.
 
 
 Caso s => r.
 
 Definisco t = s-r. Dimostro il seguente claim per induzione su t:
 
 ps || ak pt - 1.
 
 t = 0 è già dimostrato dalla parte precedente.
 
 Sia la tesi vera per un certo s.
 
 ak pt+1 - 1 = [ ak pt - 1 ] [ ak pt(p-1) + ak pt(p-2) + ... + ak pt + 1 ] [differenza di due p-esime potenze].
 
 La potenza di p che divide esattamente il primo membro è il prodotto delle potenze che d.e. i fattori del secondo. ps || il primo fattore. Dico che p || il secondo. Vediamo mod. p2. Pongo ak = 1 + bp. Allora amk = 1 + mb p (mod p2) [Teo. del Binomio]. Da questo,
 
 2°f. = sum ( 1 + ptib p ) = p + bpt+2(p-1)/2 = p (mod p2).
 
 Quindi p2 non | 2°f., cioè p || 2°f. Questo dimostra il mio claim. Si noti che è qui e solo qui che serve l\'ipotesi p>2.
 
 Chiaramente, il claim implica che k pt >= ord a mod ps.
 
 Vedo che vale il <=. Di nuovo, per induzione su t. t = 0 è ancora dimostrato dal primo caso.
 
 Passo induttivo. Sia h = ord a mod ps+1. ah = 1 (mod ps+1) ==> = 1 (mod ps). Da questo e dal claim, si ha che k pt | h | k pt+1. Quindi h = k pt oppure h = k pt+1.
 
 La prima non può valere. Infatti, se fosse, avremmo ps+1 | ak ps-r - 1. Del resto per il Claim, ps || ak ps-r - 1; questi due fatti sono in contraddizione. Quindi vale la seconda e questo conclude. []
 
 Ciao.
 
 M.
 
 P.S.: sulla questione se sia meglio dire l\'ordine di \"a con base n\" o viceversa, io direi che è meglio considerare a la base e n il modulo (i.e. aord = 1 mod n). Questo per uniformarsi alla dizione standard che vuole l\'ordine di un elemento di un gruppo come la minima potenza per cui si ottiene 1. Qui l\'elemento è a (e il gruppo gli interi invertibili mod. n) e quindi preferisco dire l\'\"ordine [moltiplicativo] di a mod. n\" e non già l\'\"ordine di n con base a\" o similari. [ Questo Messaggio è stato Modificato da: marco il 25-11-2004 12:50 ]

HiTLeuLeR · Messaggio da **HiTLeuLeR** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 25-11-2004 11:35, marco wrote:
 [...] denoto il minimo intero positivo k t.c. ak = 1 mod n, ord a mod n. [...]
 Caso s => r. Definisco t = s-r. Dimostro il seguente claim per induzione su t:
 ps || ak pt - 1.
 t = 0 è già dimostrato dalla parte precedente.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Quando t = 0, ovvero r = s: ps || ak pt - 1 sse: pr || ak - 1, il che è vero perché così si è assunto. In tutta sincerità, non vedo adesso in che modo tu voglia sperare, per quanto zelante e industrioso, di poter dimostrare un fatto che è vero per ipotesi, o meglio dedurlo da tue precedenti considerazioni!!! Vabbe\', suvvia, si è trattato soltanto di un lapis: non è strettamente necessario, per questa volta, che tu ti autoinfligga sanguinolente pene corporali, credimi... Sul resto, nulla da eccepire!!!
 
 <TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 25-11-2004 11:35, marco added:
 [...] spero di non aver scritto troppe castronerie. In caso contrario, so di poter contare sull\'amabile Hit per essere ricondotto sulla buona strada.
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 Amabile?!? IO?!? Macché castronerrrrrrie... Sai che le spari proprio grosse, alcune volte, marco? Asdasdasd...
 
 
 \"Gianni, l\'ottimismo è il profumo della vita!\" - la tv [ Questo Messaggio è stato Modificato da: HiTLeuLeR il 25-11-2004 13:26 ]