OliForum Matematico

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!

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.

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.

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!

Non solo... il numero di residui m-esimi mod p e'
$ \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:)

Ho spezzato il thread, visto che minacciava di comparire anche la dimostrazione dell'affermazione di leblanc sul numero di residui. Così almeno nel glossario c'è anche questa voce.

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!

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!