Kekuatan utama modulo akar primitif

Question

Jika saya temukan $a$ adalah PR mod p, maka sebuah teorema menyatakan bahwa baik $a$ sendiri atau $a+p$ adalah mod PR $p^2$. Apakah ada pendekatan cepat untuk memeriksa eksponen$a$, alih-alih menelusuri setiap elemen di $\{1,...,\phi(p^2)\}$? Saya ingat eksponen dari$a$ ($ord_{p^2}(a)$) mengambil nilai dalam himpunan semua pembagi $\phi(p^2)$, tetapi saya tidak yakin apakah saya mengingatnya dengan benar.

Lebih dari itu sejak modulo $p^2$ meluas dari modulo $p$, Aku ingin tahu apakah $\phi(p)$ akan terlibat dalam eksponen $e$ dari $a^e \equiv 1$ mod $p^2$? Terima kasih sebelumnya!

---

Contoh konkret: 2 ditemukan sebagai root modulo 13 primitif, bagaimana saya bisa menunjukkan 2 juga merupakan mod root $13^2$? Untuk eksponen 2, saya akan memeriksa semua pembagi dari$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$, dan menunjukkan 156 itu sendiri adalah yang terkecil $e$ seperti yang $2^e\equiv 1$ mod $13^2$?

---

Hasil yang relevan dan lebih umum:

(https://en.wikipedia.org/wiki/Primitive_root_modulo_n)

Answer 1

Seandainya $a$ adalah root primitif (mod $p$). Hasil yang lebih tepat adalah:

• $a$ adalah root primitif (mod $p^2$) jika dan hanya jika $a^{p-1}\not\equiv1$ (mod $p^2$);
• dari $p$ angka $a$, $a+p$, ..., $a+(p-1)p$, tepatnya salah satunya memuaskan $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

Jadi, Anda cukup menghitung $a^{p-1}$ modulo $p^2$ untuk menentukan jawabannya.