Dubbio residuo

Tutto ciò che dovete sapere per arrivare preparati alle competizioni matematiche.

Dubbio residuo

Messaggioda ElPaso98 » 24/02/2017, 15:41

Dato un primo [tex]p[/tex], è possibile contare il numero di residui [tex]k-esimi[/tex] modulo [tex]p[/tex] in funzione del primo stesso?
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Dubbio residuo

Messaggioda Gerald Lambeau » 24/02/2017, 17:22

$\displaystyle \frac{p-1}{MCD(k, p-1)}+1$.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18

Re: Dubbio residuo

Messaggioda ElPaso98 » 24/02/2017, 19:26

Grazie mille, ero abbastanza sicuro di averla letta tempo fa da qualche parte ma non riuscivo a ricordarla/ritrovarla.
ElPaso98
 
Messaggi: 99
Iscritto il: 26/02/2016, 19:38

Re: Dubbio residuo

Messaggioda parisgermain98 » 24/02/2017, 19:27

Gerald Lambeau ha scritto:$\displaystyle \frac{p-1}{MCD(k, p-1)}+1$.


Potresti spiegare da dove si ottiene?
parisgermain98
 
Messaggi: 28
Iscritto il: 23/04/2016, 23:32

Re: Dubbio residuo

Messaggioda Gerald Lambeau » 24/02/2017, 20:22

Dati due resti diversi modulo $p$, se $g$ è un generatore scriviamoceli come $g^a$ e $g^b$, per opportuni $a \not=b$. L'uso dei generatori ci fa escludere lo $0$ per ora.
Vogliamo sapere quando $(g^a)^k \equiv (g^b)^k \pmod{p} \Rightarrow g^{ak} \equiv g^{bk} \pmod{p}$. Essendo $g$ un generatore modulo $p$, l'ultima uguaglianza vale se e solo se $ak \equiv bk \pmod{p-1}$.
Questo vale se e solo se $\displaystyle a \equiv b \pmod{\frac{p-1}{MCD(k, p-1)}}$. Questo ti dice che ce n'è al più $\displaystyle \frac{p-1}{MCD(k, p-1)}$ diversi, ma siccome quel numero è minore o uguale di $p-1$, allora ne abbiamo trovati proprio quel numero lì (un generatore ha esattamente $p-1$ potenze diverse, alla peggio, cioè quando $MCD(k, p-1)=1$, le dobbiamo usare tutte).
Dobbiamo però riaggiungere lo $0$, quindi $+1$.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 920
Iscritto il: 07/01/2015, 18:18


Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite