Pagina 1 di 1
classi di congruenza
Inviato: 28 dic 2009, 19:43
da 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
Inviato: 30 dic 2009, 19:09
da 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?
Inviato: 30 dic 2009, 20:43
da 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 $.
Inviato: 31 dic 2009, 11:12
da danielf
ok ho capito le classi di congruenza,grazie e per quanto riguarda la frase scritta su sui generatori?
Inviato: 31 dic 2009, 12:17
da 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.
Inviato: 31 dic 2009, 12:19
da 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 $
Inviato: 31 dic 2009, 13:26
da danielf
exodd ha scritto: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!
Inviato: 31 dic 2009, 15:51
da exodd
danielf ha scritto:exodd ha scritto: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 $
Inviato: 31 dic 2009, 16:12
da 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 ;)