İlkel kök modulo asal gücü

Question

Bulursam $a$ PR mod p ise, bir teorem ya da $a$ kendisi veya $a+p$ PR modudur $p^2$. Üslerini kontrol etmek için hızlı bir yaklaşım var mı?$a$her unsurdan geçmek yerine $\{1,...,\phi(p^2)\}$? Üssü hatırlıyorum$a$ ($ord_{p^2}(a)$) tüm bölenleri kümede değer alır $\phi(p^2)$ama doğru hatırladığımdan emin değilim.

Modulo'dan beri daha fazlası $p^2$ modulodan uzanır $p$, Merak ediyorum eğer $\phi(p)$ üs ile ilgili olacak $e$ nın-nin $a^e \equiv 1$ mod $p^2$? Şimdiden teşekkürler!

---

Somut bir örnek: 2 ilkel bir kök modulo 13 olarak bulundu, nasıl gösterebilirim 2 de bir kök mod $13^2$? 2'nin üssü için, tüm bölenleri kontrol edecek miyim?$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$ve 156'nın kendisi en az $e$ öyle ki $2^e\equiv 1$ mod $13^2$?

---

Alakalı ve daha genel bir sonuç:

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

Answer 1

Farz et ki $a$ ilkel bir köktür (mod $p$). Daha kesin bir sonuç şudur:

• $a$ ilkel bir köktür (mod $p^2$) ancak ve ancak $a^{p-1}\not\equiv1$ (mod $p^2$);
• of $p$ sayılar $a$, $a+p$, ..., $a+(p-1)p$tam olarak bunlardan biri tatmin ediyor $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

Böylece basitçe hesaplayabilirsiniz $a^{p-1}$ modulo $p^2$ cevabı belirlemek için.