Se a è residuo d-esimo mod p allora a^((p-1)/d) è congruo a 1 mod p. e questo ok.
Ma se a^((p-1)/d) è congruo a 1 mod p allora è per forza vero che a è residuo d-esimo?
dubbio residui d-esimi
Re: dubbio residui d-esimi
Questo andrebbe in Glossario e teoria di base (se c'è qualche moderatore di passaggio che lo sposti, lo ringrazio..). Fatto. --FrancescoVenezianoardroc ha scritto:Ma se a^((p-1)/d) è congruo a 1 mod p allora è per forza vero che a è residuo d-esimo?
In $ \mathbb{Z}/p\mathbb{Z} $ sia $ g $ un generatore, cioè un intero positivo minore di $ p $ tale che $ \text{ord}_p(g)=p-1 $ (è un fatto noto, ma se nn lo conosci dimostra che ne esiste almeno uno e che ne sono esattamente $ \varphi(\varphi(p)) $).
Sia $ \alpha \in \mathbb{Z}\cap [1,p-1] $ tale che $ g^{\alpha}=a $ in $ \mathbb{Z}/p\mathbb{Z} $. Se allora $ a^{\frac{p-1}{d}}=g^{\alpha \frac{p-1}{d} }= g^{p-1} = 1 $ allora $ \alpha \frac{p-1}{d} \equiv p-1 \equiv 0 \pmod{p-1} \implies d\mid \alpha $.
The only goal of science is the honor of the human spirit.
Re: dubbio residui d-esimi
Grazie. però c'è un'altra cosa che non mi è chiara allora: il fatto che i residui d-esimi modulo p siano (p-1)/mcd(d,p-1).
dimmi dove sbaglio nel ragionamento.
io dico che a è residuo se a^((p-1)/d) è congruo a 1 mod p. sia g^k congruo ad a mod p. questo equivale a chiedere che g^(k(p-1)/d) sia congruo a 1 mod p. questo implica che d divide k ( come hai fatto nella precedente dimostrazione) o che mcd(d,p-1) divide k? perche se è vera la seconda allora posso effetivamente dire che i residui sono p-1/mcd(d,p-1).
grazie e scusa per il non uso del latex.
dimmi dove sbaglio nel ragionamento.
io dico che a è residuo se a^((p-1)/d) è congruo a 1 mod p. sia g^k congruo ad a mod p. questo equivale a chiedere che g^(k(p-1)/d) sia congruo a 1 mod p. questo implica che d divide k ( come hai fatto nella precedente dimostrazione) o che mcd(d,p-1) divide k? perche se è vera la seconda allora posso effetivamente dire che i residui sono p-1/mcd(d,p-1).
grazie e scusa per il non uso del latex.