[溫故知新,數論] Prmitive Root modulo n

(以下定義/定理或者未夠嚴僅... 數學人請見諒...)

記錄一下每年 "瞬耳即忘" 的數論知識...
雖然網上有很多 material
不過還是親手記下才更深刻
亦好讓日後能循著相似的思路重溫

先來的是在往年的 Training Record 就有提過...
而且(包括算法競賽)應用極廣的：

Theorem 1 (Euler's Totient Theorem)

若 (a, n) = 1
則 a^Φ(n) ≡ 1 (mod n)

---

Definition 1 (Multiplicative Order)

a 的 (multiplicative) order modulo n 是最小的 h
使得 a^h ≡ 1 (mod n)

以下為 (hopefully) 較直觀的解說：

a 的 order 就是 {x_i} 的最小循環節
其中 x₁ := 1 (mod m), x_k :=  x_k-1 × a (mod n)

---

Definition 2 (Primitive Root)