Generatori

[simone256]

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?

[Troleito br00tal]

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.

[Tess]

Non riesco a dimostrare perché non esiste se $n=2^k$ con $k\geq 3$

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.