Io ho pensato: sia g un generatore (mod p). Scrivo dunque $ a \equiv g^k \pmod{p} $. Devo contare insomma i k tali che ord(g^k) = n.
Scrivo $ ord_p g^k = \dfrac{ord_p g}{\gcd(k, ord_p g)} = n $ da cui, essendo ord(g) = p-1 perché è un generatore, $ \gcd(k, p-1) = \dfrac{p-1}{n} $. Sono praticamente tutti i numeri k < p-1 tali che $ \gcd(k, p-1) = \dfrac{p-1}{n} $, e questi sono ovviamente $ \phi(n) $.
La soluzione del problema però dice che sono $ \phi((p-1)/n) $, e non riesco a capire perché
.
.
