primitive root（原根）：数论中的概念。对正整数 \(n\)，若存在整数 \(g\) 使得 \(g\) 与 \(n\) 互素，并且 \(g\) 的幂 \(g^1, g^2, \dots\) 在模 \(n\) 意义下能生成所有与 \(n\) 互素的剩余类（即形成模 \(n\) 的乘法群的生成元），则称 \(g\) 是 模 \(n\) 的一个原根。
常见情形：当 \(n\) 为奇素数 \(p\) 时，原根一定存在。
/ˈprɪmɪtɪv ruːt/
A primitive root modulo 7 is 3.
模 7 的一个原根是 3。
If \(g\) is a primitive root modulo \(p\), then every nonzero residue modulo \(p\) can be written as \(g^k \bmod p\) for some integer \(k\).
如果 \(g\) 是模素数 \(p\) 的原根，那么模 \(p\) 的每个非零剩余都可以表示为某个 \(g^k \bmod p\)。
primitive 源自拉丁语 primitivus，含义是“最初的、原始的”；root 本义为“根”。在数学里，“root（根）”常用来指“基础来源/生成因素”。因此 primitive root 可理解为“最基本、能生成全部元素的‘根’（生成元）”。
Select Language