รากปฐมฐาน
 

1.ให้ $m \in \mathbf{N} $ และ $r$ เป็นรากปฐมฐานในมอดุโล $m$ จะได้ว่า
$ r^{\displaystyle u}$ เป็นรากปฐมฐานในมอดุโล $m$ ก็ต่อเมื่อ $(u, \phi (m))=1$

2. ให้ $n \in \mathbf{R} $ พิสูจน์ว่า $n$ จะมีรากปฐมฐาน ก็ต่อเมื่อ $n=2,4,p^{\displaystyle k},2p^{\displaystyle k}$
สำหรับจำนวนเฉพาะคี่ $p$ และ $ k \in \mathbf{N} $

นิยามของรากปฐมฐานคืออะไรหรอครับ

ตอบข้อ 1 ก่อนนะครับ

(ขาไป) ถ้า $(u,\phi(m))\neq 1$ ให้มันเท่ากับ $d$

พบว่า

$(r^u)^{\frac{\phi(m)}{d}}\equiv (r^{\frac{u}{d}})^{\phi(m)} \equiv 1 (mod m)$

แสดงว่า $ord_p(r^u)\neq \phi (m)$ ทำให้มันไม่เป็น Primitive Root ครับ :D

(ขากลับ) ให้ $ord_p(r^u)=x$ จากนิยาม จะได้ว่า

$(r^u)^x\equiv 1 (mod m)$

$r^{\phi (m)}\equiv 1 (mod m)$

$r^{(ux,\phi (m))}\equiv 1 (mod m)$

จาก $(u,\phi (m))=1$ จะได้ว่า $(ux,\phi (m))=(x,\phi (m))=x$

$r^x\equiv 1 (mod m)$

เนื่องจาก $r$ เป็น primitive root จะได้ว่า $x=\phi(m)$ :D