Si può avere una dimostrazione di questo fatto? (ehm...forse nel glossario vero?). Cioè mi sembra di aver capito che se $ (m,p-1)=1 $ allora tutti i numeri sono residui m-esimi mod p giusto?
Grazie mille!
Residui m-esimi mod p
Se p è primo allora esiste un generatore g.
(p-1, k)=1, quindi sia i l'inverso di k modulo (p-1).
Vogliamo dimostrare che a è un residuo k-esimo.
Sia $ ~ a=g^x $, x intero. Allora $ ~ b=g^{ix} $. Avremo che $ ~ b^k = (g^{ix})^k = (g^x)^{ik} = g^x = a $, perchè $ ik \equiv 1 \pmod {p-1} $.
Quindi a è un residuo k-esimo.
(p-1, k)=1, quindi sia i l'inverso di k modulo (p-1).
Vogliamo dimostrare che a è un residuo k-esimo.
Sia $ ~ a=g^x $, x intero. Allora $ ~ b=g^{ix} $. Avremo che $ ~ b^k = (g^{ix})^k = (g^x)^{ik} = g^x = a $, perchè $ ik \equiv 1 \pmod {p-1} $.
Quindi a è un residuo k-esimo.
Oppure più stupidamente : se $ x^m\equiv y^m (\mod p) $ allora
$ (x/y)^m\equiv 1 (\mod p) $ ma allora $ \textrm{ord}_p(x/y)|m $, del resto si sa che $ \textrm{ord}_p(x/y)|p-1 $ e dunque l'ordine è 1, ma allora $ x\equiv y (\mod p) $ da cui scopriamo che l'applicazione
$ \psi:\{0,\ldots,p-1\}\to\{0,\ldots,p-1\} $ tale che $ \psi(x)\equiv x^m (\mod p) $ (esiste ed è unica...) è iniettiva, ma allora l'immagine deve essere tutto l'insieme {0,1,...,p-1}. Quindi tutti i numeri sono residui m-esimi mod p se (m,p-1)=1.
$ (x/y)^m\equiv 1 (\mod p) $ ma allora $ \textrm{ord}_p(x/y)|m $, del resto si sa che $ \textrm{ord}_p(x/y)|p-1 $ e dunque l'ordine è 1, ma allora $ x\equiv y (\mod p) $ da cui scopriamo che l'applicazione
$ \psi:\{0,\ldots,p-1\}\to\{0,\ldots,p-1\} $ tale che $ \psi(x)\equiv x^m (\mod p) $ (esiste ed è unica...) è iniettiva, ma allora l'immagine deve essere tutto l'insieme {0,1,...,p-1}. Quindi tutti i numeri sono residui m-esimi mod p se (m,p-1)=1.
Non solo... il numero di residui m-esimi mod p e'luca88 ha scritto:Si può avere una dimostrazione di questo fatto? (ehm...forse nel glossario vero?). Cioè mi sembra di aver capito che se $ (m,p-1)=1 $ allora tutti i numeri sono residui m-esimi mod p giusto?
Grazie mille!
$ \frac{p-1}{gcd(p-1, m)}+1 $
(il +1 serve solo per dire che 0 e' sempre un residuo, non ha altre strane ragioni:))
Provate a dimostrarlo... non e' diverso dalla dimostrazione di EvaG, bisogna solo fare un pochino piu' attenzione:)
-
darkcrystal
- Messaggi: 706
- Iscritto il: 14 set 2005, 11:39
- Località: Chiavari
Ci provo... allora, prima un po' di notazione.
Vi avviso: in questa dimostrazione uso tante lettere... scusatemi
Sia k l'esponente della potenza che esaminiamo, $ d=gcd(p-1,k) $, inoltre $ k=da $ e $ (p-1)=db $
Prendiamo poi un generatore g e un residuo q che vogliamo analizzare. Per un qualche m si ha allora $ g^m \equiv q \pmod p $.
Noi cerchiamo quindi un esponente l tale che $ (g^l)^k \equiv q \equiv g^m \pmod p $.
Ma allora $ kl \equiv m \pmod {p-1} $, da cui $ p-1 | kl-m \Rightarrow db | dal - m $, da cui sicuramente d|m. Ma allora gli m buoni - e corrispondentemente i q buoni - sono solo i multipli di d minori di p (e maggiori di zero, dato che p-1 e 0 sono lo stesso residuo), che sono esattamente $ \frac{p-1}{d} $. A questi ne va aggiunto uno che è lo 0, dato che non è ottenibile come $ g^m $. Per poi dimostrare che tutti questi vanno bene, si consideri che posto m=dn si ha $ db | dal - dn $ che possiamo dividere in due parti, $ d | dal-dn $ che è sempre vera e $ b| dal-dn $ che ha soluzione dato che b è coprimo sia con a che con d.
Speriamo bene,
ciao!
Vi avviso: in questa dimostrazione uso tante lettere... scusatemi
Sia k l'esponente della potenza che esaminiamo, $ d=gcd(p-1,k) $, inoltre $ k=da $ e $ (p-1)=db $
Prendiamo poi un generatore g e un residuo q che vogliamo analizzare. Per un qualche m si ha allora $ g^m \equiv q \pmod p $.
Noi cerchiamo quindi un esponente l tale che $ (g^l)^k \equiv q \equiv g^m \pmod p $.
Ma allora $ kl \equiv m \pmod {p-1} $, da cui $ p-1 | kl-m \Rightarrow db | dal - m $, da cui sicuramente d|m. Ma allora gli m buoni - e corrispondentemente i q buoni - sono solo i multipli di d minori di p (e maggiori di zero, dato che p-1 e 0 sono lo stesso residuo), che sono esattamente $ \frac{p-1}{d} $. A questi ne va aggiunto uno che è lo 0, dato che non è ottenibile come $ g^m $. Per poi dimostrare che tutti questi vanno bene, si consideri che posto m=dn si ha $ db | dal - dn $ che possiamo dividere in due parti, $ d | dal-dn $ che è sempre vera e $ b| dal-dn $ che ha soluzione dato che b è coprimo sia con a che con d.
Speriamo bene,
ciao!
"Solo due cose sono infinite: l'universo e la stupidità dell'uomo, e non sono tanto sicuro della prima" - Einstein
Membro dell'EATO
Membro dell'EATO
Per prima cosa grazie per il chiarimento! Avevo un altro dubbio e quindi posto qui visto che siamo in argomento. Ho letto su una dispensa di Tdn che i residui m-esimi mod p consistono in tutti e soli quei numeri il cui indice è multiplo di $ gcd(m,p-1) $ (da cui segue peraltro quello che ha scritto sopra leblanc sul numero dei residui e lì mi è tutto chiaro). La mia perplessità è: ma l'indice non dipende dal generatore g che si sceglie oltre che dal primo p? Gli indici non potrebbero cambiare la loro divisibilità-non divisibilità? Grazie per l'attenzione!