原根

与整数阶有关的一个数论概念
image
原根（Primitive Root[2]）是与整数阶有关的一个数论概念[3]。其定义为：设m>1，(a,m)=1，t是使at≡1(mod m)成立的最小正整数，则称t为a关于模m的阶数，若a关于模m的阶数是φ(m)，就称a为模m的一个原根。[7]
原根的历史可追溯至18世纪数论问题的研究。1785年，勒让德（Legendre）在给出二次互反律的同时还给出了模
的原根的构造。1801年，高斯（Carl Friedrich Gauss）在他的著作《算术研究》中，证明了一个原根的性质[12]，即正整数中只有
，
，
和
存在原根。[3]20世纪50年代开始，一些学者对原根的上下限进行了讨论，中国数论专家王元证明了模
的最小原根
的结果为
。[4]1962年，伯吉斯（Burgess）得到了和王元同样的结果，且说明了
所隐含的常数仅取决于
。[5]而对于原根的上限，1981年，格罗斯瓦尔德（Emil Grosswald）进行了猜测：如果
，则
，其结果被其他学者做出了验证和进一步探索。[6]
原根具有一些基本性质，如，如果模
有原根，则它恰有
个原根。[13]它可以用于数论中著名定理——费马小定理的证明。[11]消去法可以用于求解原根，但是计算过程较为复杂。[3]此外，原根在现实世界中应用广泛，如密码学中，它是实现Diffie-Hellman密钥交换协议的一个核心参数，直接影响协议的安全性。[9]

定义

根据欧拉定理，当
，
时，
，因此在
的正方幂
，
，
，
中，必有正整数
存在，使得
，于是给出：[7]