Piccolo teorema di Fermat e collane

[Zorro_93]

Salve... non so se qualcuno abbia presente una delle dimostrazioni dell'Engel per il piccolo teorema di Fermat, quindi la riporto:
"We have pearls with a colors. From these we make necklaces with exactly p pearls. First, we make a string of pearls. Thereare $ a^p $ different strings. If we throw away the a one-colored strings ap — a strings will remain. We connect the ends of each string to get necklaces. We find that two strings that differ only by a cyclic permutation of its pearls result in indistinguishable necklaces. But there are p cyclic permutations of p pearls on a string. Hence the number of distinct necklaces is $ (a^p -a)/p. $ Because of its interpretation this is an integer. So $ p|a^p-a $


Non ho ben capito dove viene utilizzata l'ipotesi che p sia primo.

[Tibor Gallai]

But there are p cyclic permutations of p pearls on a string.

Qui una cosa è sottointesa. Quale?

Hence the number of distinct necklaces is $ (a^p-a)/p $.

Perché?

[Zorro_93]

scusa... ho copiato male il testo
ho editato

[Zorro_93]

Hence the number of distinct necklaces is $ (a^p-a)/p $.

Perché?

Perchè una volta che chiudo le collane ho contato p volte ogni collana ( perchè p sono le "rotazioni" possibili)

[Tibor Gallai]

Perché?
Ok, alternativamente rispondi alla domanda "perché no?" nel caso p non sia primo.

[Zorro_93]

Perché?
Ok, alternativamente rispondi alla domanda "perché no?" nel caso p non sia primo.

Forse ho capito: se p non è primo allora può esserci un colore che ricompare a intervalli regolari, tipo nella collana ABAB, questa la conto 2 volte e non 4. Se p è primo questo non può accadere.

Giusto?

[Zorro_93]

c'è da aggiungere che ciò accade con gli intervalli regolari di 1, forse è per quello che toglie le collane di un sol colore

[julio14]

c'è da aggiungere che ciò accade con gli intervalli regolari di 1, forse è per quello che toglie le collane di un sol colore

E i divisori di $ $p $ primo sono...
Prova a dimostrare formalmente perché primo va bene e composto no, e vedrai che capisci meglio.

[Tibor Gallai]

But there are p cyclic permutations of p pearls on a string.

Qui una cosa è sottointesa. Quale?

Le permutazioni cicliche di una stringa sono tutte distinte, tranne nel caso della stringa costante.

[Zorro_93]

c'è da aggiungere che ciò accade con gli intervalli regolari di 1, forse è per quello che toglie le collane di un sol colore

E i divisori di $ $p $ primo sono...
Prova a dimostrare formalmente perché primo va bene e composto no, e vedrai che capisci meglio.

Vediamo... ci provo:
In una collana si possono individuare delle "sequenze" di colori che si ripetono, e possono essere lunghe quanto i divisori di $ p $. Le permutazioni cicliche di collane con segmenti lunghi n, se n divide p, sono n.
Quindi per $ p $ primo i soli divisori sono 1 e $ p $ stesso, e $ p $ sono le permutazioni cicliche di collane con "segmenti" lunghi $ p $ ( e quindi senza ripetizioni)

[julio14]

Uh, ok.
A voler essere pignoli, non hai giustificato

possono essere lunghe quanto i divisori di $ p $.

e

Le permutazioni cicliche di collane con segmenti lunghi n, se n divide p, sono n.

ma sono veramente veloci. Btw, per il secondo c'è da specificare che i "segmenti" sono quelli di lunghezza minima che rispettino una definizione sensata di segmenti ripetuti.

[Zorro_93]

Uh, ok.
A voler essere pignoli, non hai giustificato

possono essere lunghe quanto i divisori di $ p $.

e

Le permutazioni cicliche di collane con segmenti lunghi n, se n divide p, sono n.

ma sono veramente veloci. Btw, per il secondo c'è da specificare che i "segmenti" sono quelli di lunghezza minima che rispettino una definizione sensata di segmenti ripetuti.

Ok, ora che mi è tutto più chiaro c'è da dire che questa dimostrazione è veramente bella, uno dopo aver iniziato il capitolo sulle congruenze si aspetti che passi da lì e invece puff... da tutt'altra parte

[Tibor Gallai]

Cerchiamo di dimostrare la freccia giusta.

Supponiamo che due permutazioni cicliche di una stringa di lunghezza n coincidano, e che l'una si ottenga dall'altra con una rotazione di d>0 posizioni. Supponiamo anche che d sia il minimo intero per cui ciò accade. Allora la stringa ha "periodo" d, ovvero è formata da n/d copie consecutive della stessa sottostringa lunga d. In particolare, d|n.

Dimostra questo e hai vinto.

[Zorro_93]

Cerchiamo di dimostrare la freccia giusta.

Supponiamo che due permutazioni cicliche di una stringa di lunghezza n coincidano, e che l'una si ottenga dall'altra con una rotazione di d>0 posizioni. Supponiamo anche che d sia il minimo intero per cui ciò accade. Allora la stringa ha "periodo" d, ovvero è formata da n/d copie consecutive della stessa sottostringa lunga d. In particolare, d|n.

Dimostra questo e hai vinto.

Chiamo $ (a_1,a_2,\cdots,a_d,\cdots,a_n) $ e $ (a_{d+1},\cdots,a_n,a_1,\cdots,a_d) $ la stringa permutata con rotazione d allora devo avere che $ (a_i,a_{i+1},\cdots,a_{i+k})=(a_{i+d},\cdots,a_{i+d+k}) $ per tutti le i e le d (per comodità considerati modulo n), giusto? si intende questo per coincidenza? A questo punto è fatta, l'ultima relazione è la definizioni di segmenti lunghi d.
Non ne sono molto convinto

[Tibor Gallai]

Non ho capito cos'è k. Inoltre non è chiaro dove (e se) usi la minimalità di d.