[N] An introduction to primitive roots.

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

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

Messaggio da HiTLeuLeR »

PREMESSE: siano g, n € Z, con n > 1. Diremo che g è una radice primitiva mod n sse: ord<sub>g</sub>(n) = phi(n), ove phi(·) è la funzione omonima di Eulero ed ord<sub>g</sub>(n) denota l\'ordine moltiplicativo di n alla base g, ovvero il più piccolo intero m > 0, là dove esista, tale che: g<sup>m</sup> = 1 mod n.
<BR>
<BR>---
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 1</B><!-- BBCode End --></font>: si dimostri che, se g € Z è una radice primitiva mod n, essendo n un intero > 1, l\'insieme G := {x € Z: x = g<sup>k</sup> mod n, per k = 0, 1, ..., phi(n) - 1} eguaglia l\'insieme T dei totativi<sup>(1)</sup> di n, ove a mod b denota il resto della divisione intera di a per b, per ogni a, b € Z tali che b sia diverso da 0.
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 2</B><!-- BBCode End --></font>: si provi che, se n è un intero > 1 e g € Z una radice primitiva mod n, allora g<sup>k</sup> è essa stessa una radice primitiva mod n, per ogni k = 1, 2, ..., n-1 tale che: gcd(k, phi(n)) = 1.
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 3</B><!-- BBCode End --></font>: si mostri che, se g € Z è una radice primitiva mod n, per qualche n intero > 1, allora n possiede esattamente phi(phi(n)) radici primitive fra gli interi dell\'insieme {1, 2, ..., n-1}.
<BR>
<BR><font color=green><!-- BBCode Start --><B>Problema 4</B><!-- BBCode End --></font>: si esibisca un <!-- BBCode Start --><I>proof</I><!-- BBCode End --> del teorema di Wilson<sup>(2)</sup> che utilizzi la teoria delle radici primitive<sup>(3)</sup>.
<BR>
<BR><sup>(1)</sup>: per ogni n intero > 0, si dicono <!-- BBCode Start --><I>totativi</I><!-- BBCode End --> di n tutti gli interi positivi k <= n tali che: gcd(n, k) = 1. Di qui il nome di \"<!-- BBCode Start --><I>totiente</I><!-- BBCode End -->\" comunemente attribuito all\'indicatore phi(·) di Eulero.
<BR>
<BR><sup>(2)</sup>: ad uso e consumo di quanti non dovessero conoscerne l\'enunciato, il teorema di Wilson stabilisce che, se p è un numero primo naturale, allora:
<BR>p | (p-1)! + 1. Per la cronaca, ricordo che, quantomeno definitivamente, il teorema è pure invertibile, costituendo così una caratterizzazione dei primi in N.
<BR>
<BR><sup>(3)</sup>: questo risultato mi è venuto in mente una mattina di luglio mentre mi spazzolavo i denti!!! Per quanto sia banale, è pur sempre carino... <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>
<BR>EDIT: corretta la traccia del problema n° 1.
<BR>
<BR>
<BR>\"Sempre camminerò per queste spiagge tra la sabbia e la schiuma dell\'onda.
<BR>L\'alta marea cancellerà l\'impronta e il vento svanirà la schiuma.
<BR>Ma sempre spiaggia e mare resteranno.\" - Kahlil Gibran<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 20-11-2004 21:16 ]
Avatar utente
Sisifo
Messaggi: 604
Iscritto il: 01 gen 1970, 01:00
Località: Scorzè (VE)/Pisa

Messaggio da Sisifo »

Problema 1
<BR>Non vorrei dire una stupidaggine <IMG SRC="images/forum/icons/icon_cool.gif"> <IMG SRC="images/forum/icons/icon_cool.gif"> ma...
<BR>Poichè g è radice primitiva tutti i numeri sono distinti, quindi la cardinalità dell\'insieme phi(n). Ma per mla definizione stessa di phi i numeri <=n primi
<BR>con n sono proprio phi(n). Quindi poicè i due insiemi hanno la stessa cardinalità, deve esistere una funzione biunivoca.CVD
<BR>Problema 2
<BR>Se a=g^k con (k,phi(n))=1 e a^j=1 mod n
<BR>a^j=(g^k)^j=g^(jk) mod n e quindi phi(n) divide jk a poichè (k,phi(n))=1, phi(n) divide j, quindi riassumendo se (g^k)^j=1 mod n allora phi(n) divide j, cioè g^k è radice primitiva.
<BR>
<BR>PS Ma come fai a mettere gli apici e i pedici? <IMG SRC="images/forum/icons/icon_eek.gif"> [addsig]
"Non è certo che tutto sia incerto"(B. Pascal)
Membro dell'associazione "Matematici per la messa al bando del sudoku" fondata da fph
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

Così com\'è formulato, il problema n° 1 è <!-- BBCode Start --><I>veramente</I><!-- BBCode End --> banale, ci hai proprio ragione tu, Sisifo! Un attimo solo, ché <!-- BBCode Start --><I>je dò \'na sistemata, va\'</I><!-- BBCode End -->...
<BR>
<BR>Le tue soluzioni sono entrambe ineccepibili, in ogni caso!!! Chiedo scusa per l\'imbarazzante disattenzione e provvedo subitissimo a rimediarle...
<BR>
<BR>P.S.: in quanto ad apici e pedici, prova a usare i <!-- BBCode Start --><I>tag</I><!-- BBCode End --> HTML <_sup>\"esponente\"<_/sup> e <_sub>\"deponente\"<_/sub>, rimossi gli <!-- BBCode Start --><I>underscore</I><!-- BBCode End --> all\'interno delle parentesi angolari.
<BR>
<BR>
<BR>\"Vorrei sedermi vicino a te in silenzio,
<BR>ma non ne ho il coraggio: temo che
<BR>il mio cuore mi salga alle labbra.
<BR>Ecco perche\' parlo stupidamente e nascondo
<BR>il mio cuore dietro le parole.
<BR>Tratto crudelmente il mio dolore per paura
<BR>che tu faccia lo stesso.\"
<BR>
<BR>- Rabindranath Tagore
Biagio
Messaggi: 535
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Biagio »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-19 21:44, HiTLeuLeR wrote:
<BR>
<BR><font color=green><!-- BBCode Start --><B>Problema 4</B><!-- BBCode End --></font>: si esibisca un <!-- BBCode Start --><I>proof</I><!-- BBCode End --> del teorema di Wilson<sup>(2)</sup> che utilizzi la teoria delle radici primitive<sup>(3)</sup>.
<BR>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>sia k una radice primitiva, o generatore, mod p
<BR>==> (p-1)!==k<sup>Sum i </sup>==k<sup> p(p-1)/2 </sup>==-1 in quanto p(p-1)/2 è un multiplo dispari di (p-1)/2
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR><font color=blue><!-- BBCode Start --><B>Problema 1</B><!-- BBCode End --></font>: si dimostri che, se g € Z è una radice primitiva mod n, essendo n un intero > 1, l\'insieme G := {x € Z: x = g<sup>k</sup> mod n, per k = 0, 1, ..., phi(n) - 1} eguaglia l\'insieme T dei totativi<sup>(1)</sup> di n, ove a mod b denota il resto della divisione intera di a per b, per ogni a, b € Z tali che b sia diverso da 0.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Poichè g è una radice primitiva modulo n avremo che il primo intero k tale che g<sup>k</sup> sia congruo a 1 mod n è phi(n). Quindi tutti i numeri g<sup>k</sup> con k < phi(n) hanno tutte congruenze diverse modulo n (e il numero di queste congruenze è, ovviamente, phi(n) poichè contiamo lo 0) poichè se esitessero due numeri distinti di tale forma con la stessa congruenza modulo n, prendiamo g<sup>j</sup> e g<sup>i</sup> allora tutti i numeri della forma g<sup>j+w</sup> g<sup>i+w</sup>, con w variabile negli interi non negativi, avrebbero la stessa congruenza moduolo n e, quando il maggiore di essi arriverà ad essere g<sup>phi(n)</sup> il minore diventerebbe un ordine modulo n minore di phi(n), ciò è evidentemente assurdo poichè g è radice primitiva modulo n. Quindi si hanno phi(n) congruenze distinte e la tesi è dimostrata.<font color=white>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Boll il 21-11-2004 10:32 ]<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 21-11-2004 10:33 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

@Biagio: ok!!! Soltanto che non posso fare a meno di chiedermi perché tu non abbia speso neppure <!-- BBCode Start --><I>una</I><!-- BBCode End --> parola per il caso singolare p = 2...
<BR>
<BR>@Boll: amen!
<BR>
<BR>P.S.: una volta risolto il quesito n° 3, proporrò un\'altra serie di problemi, che ho già confenzionato qualche tempo addietro e che conservavo per le occasioni speciali... I problemi, appunto, riguarderanno alcune interessanti proprietà dell\'ordine moltiplicativo, indispensabili nel <!-- BBCode Start --><I>proof</I><!-- BBCode End --> dell\'esistenza di una radice primitiva mod p, per ogni primo intero p > 2. A presto, dunque...
<BR>
<BR>
<BR>\"Muore la parola
<BR>appena è pronunciata:
<BR>così qualcuno dice.
<BR>Io invece dico
<BR>che comincia a vivere
<BR>proprio in quello stesso istante.\"
<BR>
<BR>- Emily Dickinson<font color=white>
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR><font color=blue><!-- BBCode Start --><B>Problema 3</B><!-- BBCode End --></font>: si mostri che, se g € Z è una radice primitiva mod n, per qualche n intero > 1, allora n possiede esattamente phi(phi(n)) radici primitive fra gli interi dell\'insieme {1, 2, ..., n-1}.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Gli interi dell\'insieme citato formano tutte le possibili congruenze modulo n, tolto lo 0, ma ovvimante in tale caso non si ammettono generatori. Dimostriamo dunque che fra tutte le possibli congruenze modulo n, se n ammette un generatore, allora ne ammette phi(phi(n)).
<BR>Se una congruenza non è coprima alla base, non ammette generatore, perchè ricordiamo che, se n è composto, allora ammettono ordine solo i numeri coprimi a n.
<BR>Analizziamo quindi tutte le congruenze coprime a n.
<BR>Prendiamo questa famigerata g, che è radice primitiva e consideriamo i numeri della forma g<sup>k</sup> con 0< k< =phi(n), questi formano phi(n) congruenze diverse (come dimostrato nel problema 1) e, in particolare, tutte le possibili congruenze coprime a n. Ora, fra queste congruenze, se k e phi(n) sono coprimi avremo che g<sup>k</sup> è generatore modulo n, poichè perchè l\'ordine divida la phi, essendo k coprimo, dobbiamo moltiplicarlo per phi stesso. Se invece phi e k hanno un divisore comune, g<sup>k</sup> ammette ordine (phi(n))/k. Quindi vi sono phi(phi(n)) generatori fra tutte le congruenze possibili modulo n. q.e.d.
<BR>
<BR>EDIT: Riveduto e corretto
<BR><font color=white>
<BR>
<BR>[ Questo Messaggio è stato Modificato da: Boll il 22-11-2004 20:09 ]<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 23-11-2004 14:13 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
info
Messaggi: 903
Iscritto il: 01 gen 1970, 01:00

Messaggio da info »

Aspettate...ho provato il 2...scrivo lo stesso per prenderci la mano
<BR>Hp: g<sup>phi(n)</sup>=1 mod n
<BR>Th: g<sup>k*phi(n)</sup>=1 mod n
<BR>e phi(n) è il minimo numero per entrambe le proprietà. k minore di n
<BR>
<BR>Se per assurdo la tesi fosse falsa, esistono t ed m naturali tali che tm=phi(n) e:
<BR>g<sup>k*phi(n)/m</sup>=1 mod (n)
<BR>ora se gcd(phi(n),k)=1 anche gcd(m,k)=1 e quindi m nn divide k. Inoltre phi(n) nn divide k e quindi in definitiva phi(n) nn divide k*phi(n)/m...
<BR>questo però è un assurdo, infatti, se g è un generatore e
<BR>g<sup>s</sup>=1 mod n
<BR>dividendo s per phi(n) con la divisione euclidea
<BR>g<sup>m*phi(n)+e</sup>=1
<BR>con e minore di phi(n), ma così si capisce che deve essere e=0, altrimenti phi(n) nn sarebbe l\'ordine moltiplicativo di g rispetto ad n...
<BR>Questa condizione nn viene però rispettata dal numero trovato sopra e quindi assurdo... <BR><BR>[ Questo Messaggio è stato Modificato da: info il 22-11-2004 21:40 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-22 20:07, Boll wrote:
<BR>Gli interi dell\'insieme citato formano <!-- BBCode Start --><B>tutte</B><!-- BBCode End --> le possibili congruenze modulo n, dimostriamo dunque che fra tutte le possibli congruenze modulo n, se n ammette un generatore, allora ne ammette phi(phi(n)).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Non esattamente, visto che ci manca lo zero!!! Piuttosto, è {0, 1, ..., n-1} a formare un insieme completo di residui modulo n. Ti trovi? <IMG SRC="images/forum/icons/icon_eek.gif">
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-22 20:07, Boll added:
<BR>Prendiamo questa famigerata g, che è radice primitiva e consideriamo i numeri della forma g<sup><!-- BBCode Start --><B><font color=green>k</font></B><!-- BBCode End --></sup> con 0 < <!-- BBCode Start --><B><font color=green>k</font></B><!-- BBCode End --> <= phi(n), questi formano phi(n) congruenze diverse (come dimostrato nel problema 1) e, in particolare, tutte le possibili congruenze coprime a n (<!-- BBCode Start --><I>se un numero è congruo a qualcosa non coprimo a n, tale numero non può essere radice primitiva, poichè ogni sua potenza perfetta sarà congruo a <!-- BBCode Start --><B><font color=green>k</font></B><!-- BBCode End -->+<!-- BBCode Start --><B><font color=blue>w</font></B><!-- BBCode End -->, dove <!-- BBCode Start --><B><font color=green>k</font></B><!-- BBCode End --> è il divisore comune e <!-- BBCode Start --><B><font color=blue>q</font></B><!-- BBCode End --> un intero non negativo</I><!-- BBCode End -->).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ora, a parte le tue discutibili e confuse notazioni, dico io... in nome di Hilbert e Dedekind, costerebbe poi così tanto essere un po\' più chiari nell\'uso-abuso della lingua italiana? Ok, sarò pure un po\' bacchettone e poco flessibile nel mio modo di scrivere, d\'accordo... ma almeno mi sforzo di <!-- BBCode Start --><I>esprimermi compiutamente</I><!-- BBCode End -->!!! In ogni caso, se ho ben inteso il senso di quel che affermi (e credimi, al di là dell\'esito, ci ho messo grande impegno), allora il testo \"quotato\" in corsivo si dovrebbe poter interpretare, più o meno, come di seguito:
<BR>
<BR>\"se g<sup>k</sup> fosse congruo ad un qualche t<sub>k</sub> nell\'insieme {0, 1, 2, ..., n-1} tale che: gcd(n, t<sub>k</sub>) > 1, per k fissato fra gli interi 1, 2, ..., phi(n), allora si avrebbe:
<BR>g<sup>mk</sup> = t<sub>k</sub> + q<sub>m</sub> mod n, per ogni m € N, ove q<sub>m</sub> è un intero non-negativo; onde dedurne, in particolare, che: g<sup>k · phi(n)</sup> = t<sub>k</sub> + q<sub>phi(n)</sub> mod n.\"
<BR>
<BR>Bene, premesso che non ho alcuna intenzione di prendermi la briga di verificare un simile asserto, ed anzi invito TE a esibirne un <!-- BBCode Start --><I>proof</I><!-- BBCode End -->, se davvero sei convinto della sua validità (...), vi è poi da aggiungere che - pure ammettendone (per un attimo) la consistenza - non mi è del tutto esplicita la conclusione cui vorresti pervenire. In altre parole... dove sta la contraddizione?!? Se ho ben compreso, tu vorresti dedurre che, supponendo per assurdo gcd(n, t<sub>k</sub>) > 1, si avrebbe a concludere che: g<sup>k · phi(n)</sup> = t<sub>k</sub> + q<sub>phi(n)</sub> =\\= 1 mod n. Ci ho preso? Se è così, beh... non ti dispiace, vero, se ti chiedo di dimostrarmelo, uh? Ok, grazie... In alternativa, là dove non ci dovessi riuscire, ti faccio presente che la tesi che affannosamente hai <!-- BBCode Start --><I>tentato</I><!-- BBCode End --> di dimostrare, con tutti i tuoi spropositati arzigogoli, in vero è parte integrante del problema n° 1, che in effetti solo <!-- BBCode Start --><I>parzialmente</I><!-- BBCode End --> - e prima non me n\'ero reso conto - <!-- BBCode Start --><B>tu stesso</B><!-- BBCode End --> avresti risolto giusto qualche dozzina di righe sopra!!! Cosa dire? Boooooooooh... <IMG SRC="images/forum/icons/icon_eek.gif">
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-22 20:07, Boll continued:
<BR>Ora, fra queste congruenze, se k e phi(n) sono coprimi avremo che g<sup>k</sup> è generatore modulo n, poichè perchè l\'ordine divida la phi, essendo k coprimo, dobbiamo moltiplicarlo per phi stesso. Se invece phi e k hanno un divisore comune, g<sup>k</sup> ammette ordine (phi(n))/k. Quindi vi sono phi(phi(n)) generatori fra tutte le congruenze possibili modulo n. q.e.d.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Sì, ok! Nota tuttavia che, alla luce della soluzione al problema n° 2 già postata da Sisifo, avresti potuto benissimo risparmiarti questa (inutile?!?) ulteriore fatica. Ciò detto, saluti...
<BR>
<BR>
<BR>\"\"Il mestiere della parola somiglia per un verso a quello della guerra: c\'è più rischio che in altri, ma la fortuna vi è più rapida.\" - Jean de La Bruyère<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 25-11-2004 13:29 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

M\'è d\'obbligo un appunto circa un passaggio della soluzione di Boll al problema n° 1, cui prima (evidentemente) non avevo prestato la dovuta attenzione.
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-21 10:30, Boll wrote:
<BR>Poichè g è una radice primitiva modulo n avremo che il primo intero k tale che g<sup>k</sup> sia congruo a 1 mod n è phi(n). Quindi tutti i numeri g<sup>k</sup> con k < phi(n) hanno tutte congruenze diverse modulo n (e il numero di queste congruenze è, ovviamente, phi(n) poichè contiamo lo 0) poichè se esitessero due numeri distinti di tale forma con la stessa congruenza modulo n, prendiamo g<sup>j</sup> e g<sup>i</sup> allora tutti i numeri della forma g<sup>j+w</sup> g<sup>i+w</sup>, con w variabile negli interi non negativi, avrebbero la stessa congruenza moduolo n e, quando il maggiore di essi arriverà ad essere g<sup>phi(n)</sup> il minore diventerebbe un ordine modulo n minore di phi(n), ciò è evidentemente assurdo poichè g è radice primitiva modulo n. Quindi si hanno phi(n) congruenze distinte e la tesi è dimostrata.<font color=white>
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Di fatto, il nostro piccolo amico ha dimostrato <!-- BBCode Start --><I>soltanto</I><!-- BBCode End --> che, per ogni coppia di interi j, k = 0, 1, ..., phi(n) - 1: g<sup>j</sup> = g<sup>k</sup> mod n sse j = k, onde dedurne che l\'insieme G := {x € Z: x = g<sup>k</sup> mod n, per k = 0, 1, ..., phi(n) - 1} ha cardinalità appunto pari a phi(n), possiede cioè tanti elementi quanti sono i totativi di n.
<BR>
<BR>In altre parole, Boll ha mostrato che G è in corrispondenza biunivoca con l\'insieme T := {k € S: gcd(n, k) = 1}. Tuttavia, resta ancora da provare che, effettivamente: G = T. Posto t<sub>k</sub> = g<sup>k</sup> mod n, per ogni k = 0, 1, ..., phi(n) - 1, ammettiamo per assurdo che t<sub>k</sub> non sia un totativo di n. E allora: gcd(t<sub>k</sub>, n) > 1. Sia dunque q > 1 un divisore primo comune<sup>(1)</sup> ad n e t<sub>k</sub>. Per costruzione:
<BR>
<BR>g<sup>k</sup> = t<sub>k</sub> mod n; q | n & q | t<sub>k</sub> ==> g<sup>k</sup> = t<sub>k</sub> mod q ==> g<sup>k</sup> = 0 mod q
<BR>
<BR>sicché: g = 0 mod q, e quindi: gcd(g, n) >= q > 1. Del resto, fissati a, m € Z, con m > 1, esiste un x € N<sub>0</sub> tale che: a<sup>x</sup> = 1 mod m sse: gcd(a, m) = 1. Dunque, in particolare, poiché g è radice primitiva mod n: g<sup>phi(n)</sup> = 1 mod n; e tuttavia: phi(n) > 0, per ogni n € N<sub>0</sub>. Dunque: gcd(n, g) = 1. Di qui l\'assurdo, e conseguentemente la tesi.
<BR>
<BR><sup>(1)</sup>: sia d<sub>k</sub> := gcd(t<sub>k</sub>, n). Poiché si ammette d<sub>k</sub> > 1, per il th. fondamentale dell\'Aritmetica, è sempre possibile rappresentare d<sub>k</sub> in forma della produttoria prod<sub>i=1...r</sub> (q<sub>i</sub>)^(a<sub>i</sub>), ove r € N<sub>0</sub>; q<sub>1</sub>, q<sub>2</sub>, ..., q<sub>r</sub> sono primi naturali distinti ed a<sub>i</sub> è un intero positivo, per ogni i = 1, 2, ..., r. E allora è sufficiente assumere q = q<sub>i</sub>, per qualche i = 1, 2, ..., r.
<BR>
<BR>
<BR>\"Questo per isperienza è provato, che chi non si fida mai sarà ingannato.\" - Leonardo da Vinci<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 23-11-2004 15:47 ]
Avatar utente
Boll
Messaggi: 1076
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza

Messaggio da Boll »

Ah, no, ok, eguaglia, avevo letto male, credevo bisognasse dimostrare che erano equipotenti, la tua puntualizzazione è dunque doverosa. Controlla il problema 3, l\'ho riscritto.<BR><BR>[ Questo Messaggio è stato Modificato da: Boll il 23-11-2004 15:38 ]
"Ma devo prendere una n-upla qualsiasi o una n-upla arbitraria?" (Lui)
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-23 14:39, Boll wrote:
<BR>Hitleuler, ma non bastava la corrispondenza biunivoca per dimostrare l\'equipotenza fra i due insiemi e, quindi, l\'uguaglianza della loro cardinalità phi(n)??? La tuo dimostrazione è solo un plus-ultra, quindi? Quindi il Problema 1 mi sembra ultimato...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>No, \"<!-- BBCode Start --><I>non bastava</I><!-- BBCode End -->\" affatto!!! Leggi bene...
<BR>
<BR><!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-19 21:44, HiTLeuLeR wrote:
<BR><font color=blue><!-- BBCode Start --><B>Problema 1</B><!-- BBCode End --></font>: si dimostri che, se g € Z è una radice primitiva mod n, essendo n un intero > 1, l\'insieme G := {x € Z: x = g<sup>k</sup> mod n, per k = 0, 1, ..., phi(n) - 1} <!-- BBCode Start --><B>eguaglia</B><!-- BBCode End --> l\'insieme T dei totativi<sup>(1)</sup> di n, ove a mod b denota il resto della divisione intera di a per b, per ogni a, b € Z tali che b sia diverso da 0.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Non ho chiesto di dimostrare che G e T sono equipotenti, bensì piuttosto che sono uguali, nel senso che possiedono gli stessi elementi. Ok?!?
<BR>
<BR>
<BR>\"Fa più rumore una albero che cade, piuttosto che una foresta che cresce.
<BR>- Lao Tze<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 23-11-2004 15:44 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

@Info: ho appena finito di leggere la tua soluzione al problema n° 2. Nulla da dire... a parte ch\'è ben fatta! <IMG SRC="images/forum/icons/icon_wink.gif">
<BR>
<BR>Bene, adesso che i problemi della prima serie sono stati tutti risolti, possiamo pure procedere con il <!-- BBCode Start --><I>proof</I><!-- BBCode End --> di alcune proprietà dell\'ordine moltiplicativo che torneranno utili nella dimostrazione finale dell\'esistenza delle radici primitive per le particolari classi di interi n > 1 di cui già si è discusso, e diffusamente, in un altro <!-- BBCode Start --><I>thread</I><!-- BBCode End --> (<a href=\"http://olimpiadi.ing.unipi.it/modules.p ... =0\"><font color=green>qui</font></a>, per l\'esattezza).
<BR>
<BR>
<BR>\"Chi vive senza follia non è cosi saggio come crede.\" - Francois de La Rochefoucald
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

PREMESSE: siano a, n € Z tali che: n > 1 e gcd(a, n) = 1. E allora, per il th. di Euler-Fermat: a<sup>phi(n)</sup> = 1 mod n, ove phi(·) denota, al solito, la totiente di Eulero. <!-- BBCode Start --><I>Ergo</I><!-- BBCode End -->, l\'insieme X := {x € N<sub>0</sub>: a<sup>x</sup> = 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).
<BR>
<BR>Posto x<sub>0</sub> := min(X), si dice che x<sub>0</sub> rappresenta l\'ordine moltiplicativo di n alla base a, e si scrive ord<sub>a</sub>(n), o equivalentemente il gaussiano di n alla base a, e si indica con gss(n,a).
<BR>
<BR>-------
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 5:</B><!-- BBCode End --></font> se p è un numero primo naturale > 2, a un intero primo con p e
<BR>p<sup>r</sup> la massima potenza che divide a^ord<sub>a</sub>(p) - 1, allora - essendo s € N<sub>0</sub>:
<BR>ord<sub>a</sub>(p<sup>s</sup>) = ord<sub>a</sub>(p), se s <= r; ord<sub>a</sub>(p<sup>s</sup>) = p<sup>s-r</sup> · ord<sub>a</sub>(p), se s > r.
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 6:</B><!-- BBCode End --></font> se a è un intero della forma 4k+1, e 2<sup>r</sup> è la massima potenza di 2 che divide a-1, allora - essendo s € N<sub>0</sub>: ord<sub>a</sub>(2<sup>s</sup>) = 1, se s <= r; ord<sub>a</sub>(2<sup>s</sup>) = 2<sup>s-r</sup>, se s > r.
<BR>
<BR><font color=blue><!-- BBCode Start --><B>Problema 7:</B><!-- BBCode End --></font> se a è un intero della forma 4k+3, e 2<sup>r</sup> è la massima potenza di 2 che divide a+1, allora - essendo s € N<sub>0</sub>: ord<sub>a</sub>(2) = 1; ord<sub>a</sub>(2<sup>s</sup>) = 2,
<BR>se 1 < s <= r; ord<sub>a</sub>(2<sup>s</sup>) = 2<sup>s-r</sup>, se s > r.
<BR>
<BR>
<BR>\"Forse non siamo capaci di amare proprio perché desideriamo <!-- BBCode Start --><I>essere</I><!-- BBCode End --> amati, vale a dire vogliamo qualcosa dall\'altro invece di avvicinarci a lui senza pretese e colmarci soltanto della sua presenza.\" - Milan Kundera<font color=white><BR><BR>[ Questo Messaggio è stato Modificato da: HiTLeuLeR il 23-11-2004 16:12 ]
Avatar utente
HiTLeuLeR
Messaggi: 1874
Iscritto il: 01 gen 1970, 01:00
Località: Reggio di Calabria

Messaggio da HiTLeuLeR »

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-11-23 14:39, Boll wrote:
<BR>Controlla il problema 3, l\'ho riscritto.
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>Ok, adesso <!-- BBCode Start --><I>funge</I><!-- BBCode End -->...
<BR>
<BR>
<BR>\"Il mestiere della parola somiglia per un verso a quello della guerra: c\'è più rischio che in altri, ma la fortuna vi è più rapida.\" - Jean de La Bruyère
Bloccato