Ragazzi scusate il disturbo...
Chiedevo se qualcuno mi poteva dire/linkare/aiutare a trovare una dimostrazione su perchè esiste un generatore modulo $ n $ se e solo se $ n $ è uguale a:
$ 2 $;
$ 4 $;
$ p^k $;
$ 2p^k $.
(con $ p $ primo dispari)
Non riesco a dimostrare perchè non esiste se $ n=2^k $ con $ k \geq 3 $; il caso base che vale per ogni primo $ p $; e che vale per ogni $ n=2p^k $.
Aiutino?
Generatori
Generatori
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
and then there was light.
$ \mbox{ }\mbox{ } $Tsune ni shinen kufu seyo
- Troleito br00tal
- Messaggi: 683
- Iscritto il: 16 mag 2012, 22:25
Re: Generatori
Ti posso abbozzare una dimostrazione bruttina ma sensata che ho trovato tempo fa (se cerchi su internet probabilmente ne trovi di più rapide e interessanti).
Intanto supponi che $n$ ammetta generatori e fai il prodotto modulo $n$ di tutte le classi di resto coprime con $n$.
Se esistono generatori il prodotto deve essere $-1$. Guardacaso, se $n$ non è della forma figa, fa $1$ (provare per credere): usa gli inversi moltiplicativi.
Ora dimostriamo che $p$ primo ammette generatori.
1) Quante soluzioni ha $x^d \equiv 1 \pmod{p}$? (Sparami un Ruffini)
2) Quante di queste soluzioni hanno ordine moltiplicativo $d$?
3) $\sum_{d|n} \phi(d)=n$.
4) Fine?
La parte su $p^k$ è formale e pallosa, devi verificare che per qualche $a$ se $g$ genera in $p$ genera pure $g+ap$ in $p^k$, comunque facilotta.
La parte di $2p^k$: prendine uno dispari e sei a bolla.
Intanto supponi che $n$ ammetta generatori e fai il prodotto modulo $n$ di tutte le classi di resto coprime con $n$.
Se esistono generatori il prodotto deve essere $-1$. Guardacaso, se $n$ non è della forma figa, fa $1$ (provare per credere): usa gli inversi moltiplicativi.
Ora dimostriamo che $p$ primo ammette generatori.
1) Quante soluzioni ha $x^d \equiv 1 \pmod{p}$? (Sparami un Ruffini)
2) Quante di queste soluzioni hanno ordine moltiplicativo $d$?
3) $\sum_{d|n} \phi(d)=n$.
4) Fine?
La parte su $p^k$ è formale e pallosa, devi verificare che per qualche $a$ se $g$ genera in $p$ genera pure $g+ap$ in $p^k$, comunque facilotta.
La parte di $2p^k$: prendine uno dispari e sei a bolla.
Re: Generatori
Per mostrare questa parte, ti stai chiedendo perché non esistono elementi di ordine troppo grande, ossia, se l'equazione $a^d\equiv 1$ ha per soluzione tutte le classi di resto coprime col modulo per qualche $d< \phi(2^k)$. Allora, contare i fattori 2 di $a^d-1$ potrebbe essere un aiuto.simone256 ha scritto:Non riesco a dimostrare perché non esiste se $n=2^k$ con $k\geq 3$