phi(n)

[matteo16]

volevo sapere se è vero che $ \phi(n) $ è uguale al numero di generatori di un gruppo ciclico con n elementi.
se è così si ha che $ \phi(n) $= numero di generatori dell'insieme delle classi di resto modulo $ n $
giusto?
posso usare queste proprietà in gara(sempre se siano giuste e se abbia capito giusto)?

[salva90]

forse non ho ben capito la domanda, ma considerando che esistono troppi interi modulo i quali non c'è un generatore direi che qualcosa non torna

[SkZ]

In verita' i generatori, se ci sono, sono $ $\phi(\phi(n))$ $

[fph]

volevo sapere se è vero che $ \phi(n) $ è uguale al numero di generatori di un gruppo ciclico con n elementi.
se è così si ha che $ \phi(n) $= numero di generatori dell'insieme delle classi di resto modulo $ n $
giusto?

La prima frase è vera. La seconda no, nel senso che si dà comunemente in TdN alla parola "generatori". Di solito per "generatori" si intende "generatori del gruppo moltiplicativo formato dai resti modulo n meno lo zero (quando è un gruppo)". Se invece per generatori intendi "generatori del gruppo ciclico delle classi di resto mod n con l'operazione +", è vero -- ma è un'affermazione più banale di quello che potrebbe sembrare dalle parolone con cui è espressa.

[matteo16]

ah quindi deve essere additivo per poter affermare ciò?

[fph]

hmm... temo che questa domanda tradisca il fatto che hai un po' di confusione in testa sull'argomento. "Additivo" e "moltiplicativo" non hanno nulla a che vedere con come è fatto il gruppo, sono solo un modo di chiamare l'operazione. Esempio: il gruppo (classi di resto non nulle modulo 7 con la moltiplicazione) e il gruppo (classi di resto modulo 6 con l'addizione) sono isomorfi, cioè in pratica sono lo stesso gruppo. Quando si parla di "generatori modulo 7" in TdN si intendono i generatori di questo gruppo. Che, come il risultato generale afferma, sono $ \phi(6) $, o anche $ \phi(\phi(7)) $. Ora è più chiaro?

[matteo16]

hmm... temo che questa domanda tradisca il fatto che hai un po' di confusione in testa sull'argomento. "Additivo" e "moltiplicativo" non hanno nulla a che vedere con come è fatto il gruppo, sono solo un modo di chiamare l'operazione. Esempio: il gruppo (classi di resto non nulle modulo 7 con la moltiplicazione) e il gruppo (classi di resto modulo 6 con l'addizione) sono isomorfi, cioè in pratica sono lo stesso gruppo. Quando si parla di "generatori modulo 7" in TdN si intendono i generatori di questo gruppo. Che, come il risultato generale afferma, sono $ \phi(6) $, o anche $ \phi(\phi(7)) $. Ora è più chiaro?

sì decisamente più chiaro. effettivamente non mi ero fermato a ragionare sulle classi di resto modulo n e sulle operazioni definite. adesso che mi ci fai riflettere però riesco meglio a capire.
il fatto che vi sia un isomorfismo tra le due classi è solo verificabile o si può anche dimostrare(effettivamente mi sto allontanando dalla domanda principale)?

[fph]

il fatto che vi sia un isomorfismo tra le due classi è solo verificabile o si può anche dimostrare(effettivamente mi sto allontanando dalla domanda principale)?

Isomorfismo tra i due /gruppi/, non classi, occhio. Dimostrare che c'è quell'isomorfismo è equivalente a dimostrare che c'è un generatore: una volta che sai questo fatto, poi definisci la funzione che manda il generatore (di Z_7^*) nella classe 1 (di Z_6), e da lì in poi sono solo verifiche e formalismo.

L'esistenza di un generatore (modulo un p primo) di solito si dimostra con una dimostrazione abbastanza insolita che ti consiglio di andare a cercare se sei interessato: prima si dimostra (lemma) che $ \sum_{d|n}\phi(d)=n $, poi usando il lemma si dimostra per induzione su d|p che ci sono \phi(d) elementi di ordine d.

[matteo16]

il fatto che vi sia un isomorfismo tra le due classi è solo verificabile o si può anche dimostrare(effettivamente mi sto allontanando dalla domanda principale)?

Isomorfismo tra i due /gruppi/, non classi, occhio. Dimostrare che c'è quell'isomorfismo è equivalente a dimostrare che c'è un generatore: una volta che sai questo fatto, poi definisci la funzione che manda il generatore (di Z_7^*) nella classe 1 (di Z_6), e da lì in poi sono solo verifiche e formalismo.

L'esistenza di un generatore (modulo un p primo) di solito si dimostra con una dimostrazione abbastanza insolita che ti consiglio di andare a cercare se sei interessato: prima si dimostra (lemma) che $ \sum_{d|n}\phi(d)=n $, poi usando il lemma si dimostra per induzione su d|p che ci sono \phi(d) elementi di ordine d.

sì grupppi hai ragione.

interessante la faccenda. andrò ad approfondire
grazie ancora delle tue risposte

[salva90]

L'esistenza di un generatore (modulo un p primo) di solito si dimostra con una dimostrazione abbastanza insolita che ti consiglio di andare a cercare se sei interessato: prima si dimostra (lemma) che $ \sum_{d|n}\phi(d)=n $, poi usando il lemma si dimostra per induzione su d|p che ci sono \phi(d) elementi di ordine d.

chedo scusa se intervengo, ma dove potrei trovare questa dimostrazione?

mi pare di ricordare che quella proposta da maria allo scorso senior non usasse questo lemma...

[fph]

L'esistenza di un generatore (modulo un p primo) di solito si dimostra con una dimostrazione abbastanza insolita che ti consiglio di andare a cercare se sei interessato: prima si dimostra (lemma) che $ \sum_{d|n}\phi(d)=n $, poi usando il lemma si dimostra per induzione su d|p che ci sono \phi(d) elementi di ordine d.

chedo scusa se intervengo, ma dove potrei trovare questa dimostrazione?

mi pare di ricordare che quella proposta da maria allo scorso senior non usasse questo lemma...

hmm... io l'ho vista in università, così su due piedi non saprei su che libro andare a ripescarla. Ci dò un'occhiata e ti faccio sapere (o se preferisci ve la lascio per esercizio... se qualcuno comincia a dimostrare il lemmetto il più è fatto...)

[salva90]

uh, ok, ci proverò (tanto più che la dimostrazione del lemma la so ormai a memoria...)