classi di congruenza

[danielf]

vorrei sapere la definizione di "classe di congruenza" con magari un esempio e come si fa appunto a trovarla per un generico numero n

[danielf]

nessuno mi può rispondere?
la domanda nasce dal fatto che un generatore g implica che le potenza g^1,..,g^(p-1) sono tutte distinte quindi sono tutte le classi non nulle di p.ma che vuol dire quest'ultima frase?

[julio14]

Sai cosa sono congruenze modulo n? Se no, prendi un video dal sito di Gobbino e parti da capo. Se si, le classi di congruenza sono semplicemente insiemi che contengo numeri congruenti tra loro. Ad esempio, modulo 5, la classe di congruenza di 3 contiene 3, 8, -2, 113.. In genere si considerano i "rappresentanti privilegiati" della classe, e cioè i numeri delle classi compresi tra 0 e n-1. Ad esempio, le classi di congruenza modulo 5 sono gli insiemi $ $\{...-5, 0, 5...\}, \{...-4, 1, 6...\},...,\{...-1, 4, 9...\} $, o, più brevemente, $ $0,1,2,3,4 $.

[danielf]

ok ho capito le classi di congruenza,grazie e per quanto riguarda la frase scritta su sui generatori?

[julio14]

Non è molto chiaro cosa hai scritto sui generatori... Comunque, modulo alcuni n esistono dei generatori, cioè dei numeri tali che $ $g,g^2,g^3...g^{\phi (n)} $ sono tutte e sole le classi di congruenza coprime con n. In particolare, se n è primo, il generatore esiste, e tutte le classi di congruenza tranne 0 sono coprime con n.

[exodd]

un generatore è, per definizione, quello che hai scritto sopra

riporto testualmente dalle schede:

"si definisce generatore modulo p un intero a tale che $ ord_p(a)=p-1 $, cioè un elemento il cui ordine è il massimo possibile"

"si definisce ordine moltiplicativo di a modulo p, e si indica con $ ord_p(a) $, il più piccolo intero $ 1\le n $ tale che $ a^n=1 $ modulo p"

un esempio di generatore:
5 è generatore modulo 7
infatti
$ 5^1=5 $
$ 5^2=4 $
$ 5^3=6 $
$ 5^4=2 $
$ 5^5=3 $
$ 5^6=1 $

[danielf]

un generatore è, per definizione, quello che hai scritto sopra

riporto testualmente dalle schede:

"si definisce generatore modulo p un intero a tale che $ ord_p(a)=p-1 $, cioè un elemento il cui ordine è il massimo possibile"

"si definisce ordine moltiplicativo di a modulo p, e si indica con $ ord_p(a) $, il più piccolo intero $ 1\le n $ tale che $ a^n=1 $ modulo p"

un esempio di generatore:
5 è generatore modulo 7
infatti
$ 5^1=5 $
$ 5^2=4 $
$ 5^3=6 $
$ 5^4=2 $
$ 5^5=3 $
$ 5^6=1 $

siete stati entrambi chiari,quando nelle schede dice che
"se a è un generatore mod p,allora gli elementi della forma a^k,con (k,p-1)=1 sono tutti e soli i generatori mod p.Un esempio di questo?
E in generale a cosa servono i generatori nell'atto pratico degli esercizi?
Grazie!

[exodd]

un generatore è, per definizione, quello che hai scritto sopra

riporto testualmente dalle schede:

"si definisce generatore modulo p un intero a tale che $ ord_p(a)=p-1 $, cioè un elemento il cui ordine è il massimo possibile"

"si definisce ordine moltiplicativo di a modulo p, e si indica con $ ord_p(a) $, il più piccolo intero $ 1\le n $ tale che $ a^n=1 $ modulo p"

un esempio di generatore:
5 è generatore modulo 7
infatti
$ 5^1=5 $
$ 5^2=4 $
$ 5^3=6 $
$ 5^4=2 $
$ 5^5=3 $
$ 5^6=1 $

siete stati entrambi chiari,quando nelle schede dice che
"se a è un generatore mod p,allora gli elementi della forma a^k,con (k,p-1)=1 sono tutti e soli i generatori mod p.Un esempio di questo?
E in generale a cosa servono i generatori nell'atto pratico degli esercizi?
Grazie!

rimanendo modulo 7, già sappiamo che 5 è un generatore
prendiamo tutti i numeri k minori di 7 che siano primi con 6
gli unici sono 1, 5
quindi 5^1=5 e 5^5=3 saranno gli unici generatori modulo 7
$ 3^1=3 $
$ 3^2=2 $
$ 3^3=6 $
$ 3^4=4 $
$ 3^5=5 $
$ 3^6=1 $

se vuoi una spiegazione di ciò, basta osservare che se elevi un generatore ad un numero k non comprimo con p-1, il suo ordine moltiplicativo si ridurrà
anzi, per essere precisi, se d>1
$ (k, p-1)=d $
$ ord_p(g^k)=p-1/d $

[dario2994]

Esempio di lemma dimostrabile con i generatori:
Dato p primo per quali $ n\in\mathbb{N} $ vale
$ $p|\sum_{i=1}^pi^n $
Te lo lascio da provare...

p.s. buon anno ;)