Rispondo per farmi perdonare lo strafalcione di prima.
In genere le potenze di $n \mod{p}$ ciclano secondo l'ordine di $n$ modulo $p$: infatti, dato che $n^{ord_p(n)}\equiv 1 \pmod{p}$, $n^{ord_p(n)+1}\equiv n^{ord_p(n)}\cdot n \equiv n \pmod{p}$ e cosi via. Inoltre se $n^a\equiv n^b \pmod{p}$ con $a,b<ord_p(n)$, allora segue che $a=b$ (cosa abbastanza facile da dimostrare). Dunque se per un certo $n$ $ord_p(n)=p-1$, allora tale $n$ viene chiamato
generatore o "elemento primitivo" se vuoi fare il figo. Esiste un generatore per
qualsiasi p primo.
Modulo $m$ generico: noto che non potrò
mai ottenere tutte le classi di resto modulo $m$ non primo; ho due casi:
1) $n$ non è coprimo con $m$.
2) $n$ è coprimo con $m$.
Nel primo caso sia $d$ tale che $n=d\cdot r,m=d\cdot s, d>1$ (può essere il MCD ma non per forza).
$n^a\equiv d^a\cdot r^a\equiv x \pmod{m}$. Noi vorremmo che $x$ possa assumere qualsiasi valore modulo $p$. Riscrivendo la congruenza come $d^a\cdot r^a=x+m\cdot k=x+d\cdot s\cdot k$, $d$ deve per forza dividere $x$ (siccome divide il membro di sinistra), dunque x non può assumere tutti i valori.
Il secondo è simmetrico: $n^a=x+m\cdot k$, dato che vorremo che $x$ assumesse tutti i valori, dovrebbe funzionare anche per $x$ non coprimo con $m$: prendo $x$ in modo che $\exists d$ tale che $x=d\cdot y$ e $m=d\cdot l$. Dunque
da $n^a=x+m\cdot k$ sostituendo: $n^a=d\cdot y+d\cdot l\cdot k$. Ma ciò è assurdo siccome abbiamo presupposto che $n$ è coprimo con $m$.
Dunque che si fa? Modulo $m$ generico un generatore si definisce tale se prende tutte le classi di resto coprime con $m$. Un generatore esiste sempre se $m\in {2,4,p^k, 2p^k}$ con $p$ primo dispari e $k$ intero positivo.
Queste cose sono spiegate brevemente sulle schede olimpiche e in parecchi video dei
senior basic.
Riguardo al caso particolare $n=2$, non mi pare che ci sia qualcosa di particolarmente interessante.