问题

称 $g$ 是模 $n$ 的原根, 如果对于任意与 $n$ 互素的 $a$, 存在 $k$ 使得

\[
g^k\equiv a\pmod n.
\]

例如, 3 是模 7 的原根.

[Definition by Ribenboim 1996]

素数 $p$ 的原根是指整数 $g$, 使得 $g\pmod p$ 具有 multiplicative order $p-1$. 即

\[
g^{p-1}\equiv 1\pmod p
\]

更一般的定义, by Burton 1989

[Def](by Burton 1989) 若 $\text{gcd}(g,n)=1$ ($g$ 和 $n$ 互素) 且 $g$ 模 $n$ 具有 multiplicative order $\varphi(n)$, 即满足

\[
g^{\varphi(n)}\equiv 1\pmod n
\]

这里 $\varphi(n)$ 是指欧拉函数(totient function), 则 $g$ 是 $n$ 的一个原根.

第一个定义是第二个定义的特殊情形, 因为对于素数 $p$, $\varphi(p)=p-1$.

设 $n$ 是具有原根的一个正整数. 若 $g$ 是模 $n$ 的一个原根, 则数 $1,g,g^2,\ldots,g^{\varphi(n)-1}$ 构成模 $n$ 的一个 reduced residue system. 在这个集合中, 有 $\varphi(\varphi(n))$ 个原根, 且这些数形如 $g^c$, 这里 $c$ 与 $\varphi(n)$ 互素.

References:

http://mathworld.wolfram.com/PrimitiveRoot.html