考虑对于 \(i \in 0 \sim p - 1\) 的 \(a^i \bmod p\) 的取值，其中 \(a \in [1, p), p\) 是素数。
首先 \(a^0 = a^{p - 1} \equiv 1(\bmod p)\)，那么会出现一个循环结构。对于循环节中的任意两个数，可以证明这两个数不同，理由是如果 \(a^x = a^y\) 那么 \(a^{|x-y|} = 1\)。但是 \(x \neq y\)，那么就矛盾了。
那么想象这样的事情的意义是什么。首先如果有循环节，那么这个循环节一定是 \(p - 1\) 的约数。其次在每一个循环节内，每一个数只会出现一次或零次（零次的话那么不存在 \(a^x \equiv i\) 的解）
如果这个循环节就是整个 \([0, p - 1)\) 也就是说 \(\forall i \in (0, p - 1), a^i \not \equiv 1\) 的话，那么称 \(a\) 为模 \(p\) 意义下的原根。
王元于 1959 年证明了若 \(m\) 有原根，其最小原根是不多于 \(m^{0.25}\) 级别的。此处略去证明。
因此找到一个数的原根只需要暴力从小到大去枚举就好了。