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?
generatori
Re: generatori
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)}\}$).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.
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.
Re: generatori
Scusa, non riesco a capire e purtroppo non conosco le notazioni che hai usato 
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
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
Re: generatori
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?
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?
Re: generatori
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...
Sto vedendo i video degli stage tutti in una volta e ho un gran confusione in testa...