OliForum Matematico

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?

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.

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

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?

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...