Dubbio residuo

[ElPaso98]

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?

[Gerald Lambeau]

$\displaystyle \frac{p-1}{MCD(k, p-1)}+1$.

[ElPaso98]

Grazie mille, ero abbastanza sicuro di averla letta tempo fa da qualche parte ma non riuscivo a ricordarla/ritrovarla.

[parisgermain98]

$\displaystyle \frac{p-1}{MCD(k, p-1)}+1$.

Potresti spiegare da dove si ottiene?

[Gerald Lambeau]

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$.