OliForum Matematico

Avrei bisogno di un aiuto su di un problema che ho incontrato sugli ordini moltiplicativi, che sarebbe anche un teorema abbastanza utile: sia p un primo e sia n un intero tale che $ n | p-1 $. Devo dire quanti sono gli interi a (mod p) tali che $ ord_p a = n $.
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é .

Scusa, se prendi n=p-1 hai che
$ \phi((p-1)/n)=\phi(1)=1 $
mentre i generatori modulo p sono $ \phi(\phi(p)) $.
Da dove viene l'esercizio?

L'esercizio è del Goldstein, "Introduction to number theory".
Comunque i generatori (mod p) sono $ \phi(p-1) $ .

Gauss91 ha scritto:L'esercizio è del Goldstein, "Introduction to number theory".
Comunque i generatori (mod p) sono $ \phi(p-1) $ .

beh se il modulo è primo $ \phi(p)=p-1 $ quindi è la stessa cosa

Ahah giusto che scemo!
Comunque il problema ha una soluzione sbagliata? E la mia soluzione vi sembra giusta?

Si, direi che $ \displaystyle \phi(n) $ va bene (fatto pochi giorni fa a lezione..)