พลังไพรม์โมดูโลรากดั้งเดิม

Question

ถ้าฉันพบ $a$ คือ PR mod p จากนั้นทฤษฎีบทระบุว่าอย่างใดอย่างหนึ่ง $a$ ตัวเองหรือ $a+p$ คือ PR mod $p^2$. มีวิธีตรวจสอบเลขชี้กำลังของ$a$แทนที่จะดูทุกองค์ประกอบใน $\{1,...,\phi(p^2)\}$เหรอ? ฉันจำได้ว่าเลขชี้กำลังของ$a$ ($ord_{p^2}(a)$) รับค่าในเซตตัวหารทั้งหมดของ $\phi(p^2)$แต่ไม่แน่ใจว่าจำถูกหรือเปล่า

มากขึ้นตั้งแต่โมดูโล $p^2$ ขยายมาจากโมดูโล $p$, ฉันสงสัยว่า $\phi(p)$ จะเกี่ยวข้องกับเลขชี้กำลัง $e$ ของ $a^e \equiv 1$ mod $p^2$เหรอ? ขอบคุณล่วงหน้า!

---

ตัวอย่างที่เป็นรูปธรรม: 2 พบว่าเป็นโมดูโลรากแบบดั้งเดิม 13 ฉันจะแสดงได้อย่างไรว่า 2 เป็นม็อดรูท $13^2$เหรอ? สำหรับเลขชี้กำลังของ 2 ฉันจะตรวจสอบตัวหารทั้งหมดของ$\phi(13^2)$= 156: $\{1, 2, 3, 4, 6, 12, 13, 26, 39, 52, 78, 156\}$และแสดงว่า 156 ตัวเองน้อยที่สุด $e$ ดังนั้น $2^e\equiv 1$ mod $13^2$เหรอ?

---

ผลลัพธ์ที่เกี่ยวข้องและทั่วไปมากขึ้น:

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

Answer 1

สมมติว่า $a$ เป็นรากดั้งเดิม (mod $p$). ผลลัพธ์ที่แม่นยำยิ่งขึ้นคือ:

• $a$ เป็นรากดั้งเดิม (mod $p^2$) ถ้าและเฉพาะในกรณีที่ $a^{p-1}\not\equiv1$ (mod $p^2$);
• ของ $p$ ตัวเลข $a$, $a+p$, ... , $a+(p-1)p$หนึ่งในนั้นตรงกับความพึงพอใจ $(a+kp)^{p-1}\equiv 1$ (mod $p^2$).

คุณก็สามารถคำนวณได้ $a^{p-1}$ โมดูโล $p^2$ เพื่อกำหนดคำตอบ