generatori

Cosa sono il pigeonhole e l'induzione? Cosa dice il teorema di Ceva? 1 è un numero primo?
Rispondi
ghiroz
Messaggi: 31
Iscritto il: 12 dic 2010, 18:26

generatori

Messaggio da ghiroz »

Approfondendo un po' di teoria dei numeri, mi sono imbattuto in questo:

$ g,g^{2},g^{3},...,g^{\varphi(m)} $

con g generatore mod m.
Perché quei $ \varphi(m) $ residui tutti diversi corrispondono proprio ai $ \varphi(m) $ residui coprimi con m?
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: generatori

Messaggio da ma_go »

ghiroz ha scritto:Approfondendo un po' di teoria dei numeri, mi sono imbattuto in questo:

$ g,g^{2},g^{3},...,g^{\varphi(m)} $

con g generatore mod m.
la "cosa" in cui ti sei imbattuto non ha nulla di speciale.. diciamo che il senso di quello che dici si capisce (spero che tu voglia dire che, se $(\mathbb{Z}/m\mathbb{Z})^*$ è ciclico, allora $(\mathbb{Z}/m\mathbb{Z})^* = \{g, g^2, \dots, g^{\varphi(m)}\}$).

entrambi gli insiemi che hai sono finiti, hanno lo stesso numero $\varphi(m)$ di elementi, e uno è contenuto nell'altro (il secondo nel primo, nel paragrafo precedente). quindi sono uguali.
ghiroz
Messaggi: 31
Iscritto il: 12 dic 2010, 18:26

Re: generatori

Messaggio da ghiroz »

Scusa, non riesco a capire e purtroppo non conosco le notazioni che hai usato :oops:

Potresti rispiegarmelo in modo più semplice?( se esiste xD) Quello che non capisco è perché tra gli m-1 residui possibili proprio quei numeri risultano essere quelli comprimi con m, cioè perché non è possibile che uno dei $ g^{k} $ sia non coprimo con m
ma_go
Site Admin
Messaggi: 1906
Iscritto il: 01 gen 1970, 01:00

Re: generatori

Messaggio da ma_go »

scusa, qual è la definizione di generatore?

comunque, prodotto di invertibili è invertibile: detto in altre parole, se $a,b$ sono coprimi con $m$, allora per bézout esistono $h,k$ tali che $ha\equiv kb\equiv 1 \pmod m$, e $ha\cdot kb = 1$, quindi $(hk)(ab)=1$, quindi $ab$ è invertibile (questa volte per definizione).
oppure, se preferisci, $(ab,m)\mid (a,m)\cdot (b,m)$ (qui con $(a,m)$ indico il massimo comun divisore di $a$ ed $m$), e se $a$ e $b$ sono coprimi con $n$, allora $(ab,m)\mid 1$, quindi anche $ab$ è coprimo con $m$ se $a$ e $b$ lo sono.
oppure, in alternativa, (ora nelle notazioni dei post precedenti) supponi che $p$ sia un primo che divide sia $g^k$ sia $m$ per un certo $k$, allora (per primalità), $p$ divide anche $g$, contraddicendo l'ipotesi che $g$ sia coprimo con $m$.
potrei anche barare e usare il teorema di fermat per dare un'altra dimostrazione, ma quella usa che il prodotto di invertibili è invertibile...

nel mio post precedente, davo per scontato che il prodotto di invertibili è invertibile, e indicavo con $(\mathbb{Z}/m\mathbb{Z})^*$ le classi di resto invertibili $\pmod m$. (la notazione è piuttosto standard, così come è piuttosto standard indicare tutte le classi di resto $\pmod m$ con $\mathbb{Z}/m\mathbb{Z}$). un po' meglio, ora?
ghiroz
Messaggi: 31
Iscritto il: 12 dic 2010, 18:26

Re: generatori

Messaggio da ghiroz »

Grazie! Ora ho capito. Non consideravo il fatto che prodotto d'invertibili è ancora invertibile

Sto vedendo i video degli stage tutti in una volta e ho un gran confusione in testa...
Rispondi