Trovare un generatore

[niccoset]

L'esercizio proposto dalla mia professoressa è il seguente:

Trovare un generatore di $ (F_23)^* $ dove $ (F_23)^* $ è il gruppo degli invertibili di $ Z/(23Z) $

Ora, dal teorema di Guass so che il gruppo in questione è ciclico e che quindi avrà un certo elemento generatore, però non riesco a capire come trovarlo. Un modo potrebbe essere quello di provare ogni elemento del gruppo e vedere (uno ad uno) se sono o meno il generatore, ma questa mi sembra una soluzione alquanto orrida.

Qualcuno può aiutarmi?

Grazie

[spugna2]

Che io sappia non si conosce un algoritmo che non vada per tentativi, ma la cosa non ti deve scoraggiare perché:

1) il generatore non è unico: nel tuo caso, ad esempio, è dato un gruppo ciclico di ordine $22$, che ha $\phi(22)=10$ generatori (significa che scegliendo un numero a caso, la probabilità che sia un generatore è circa $1/2$);

2) i calcoli da fare per vedere se un certo numero è un generatore sono relativamente pochi: in un gruppo ciclico di ordine $22$, un elemento $x$ è un generatore se e solo se ha ordine $22$; se ciò non accadesse si avrebbe $x^d=1$ per qualche $d|22$, quindi basta controllare che $x^2 \ne 1$ e $x^{11} \ne 1$.