原根

原根（）是一个在数论中的重要概念，特别是整除理论。

對於两个正整数，由欧拉定理可知，存在正整数， 比如说欧拉函数，即小于等于的正整数中与互質的正整数的个数，使得。

由此，在時，定義对模的指数為使成立的最小的正整数。由前知 一定小于等于 ，若，則稱是模的原根。

例子

考慮 ，则 。

设  ，由于

因此有，所以 2 不是模 7 的一个原根。

设  ，由于

因此有  ，所以 3 是模 7 的一个原根。

性质

可以证明，如果正整数和正整数 d 满足，则  整除 d。参考 http://www.infosec.sdu.edu.cn/jpkc/resource/4yuangen.pdf 因此整除。在例子中，当时，我们仅需要验证 3 的 2、3 次方模 7 的余数即可，如果其中有一个是1，则3就不是原根。
记，则模 m 两两不同余。因此当是模的原根时，构成模 m 的简化剩余系。
模有原根的充要條件是，其中是奇質數，是任意正整數。
对正整数，如果 a 是模 m 的原根，那么 a 是整数模m乘法群（即加法群 Z/mZ 的可逆元，也就是所有与 m 互素的正整数构成的等价类构成的乘法群）Zm×的一个生成元。由于Zm×有 个元素，而它的生成元的个数就是它的可逆元个数，即 个，因此当模有原根時，它有個原根。

 一些數的原根列表 
m模m的原根(有*號的數沒有原根，此時是有最大模m週期的數)週期 ()10121132243252, 3465273, 568*3, 5, 7292, 56103, 74112, 6, 7, 81012*5, 7, 112132, 6, 7, 1112143, 5615*2, 7, 8, 13416*3, 5, 11, 134173, 5, 6, 7, 10, 11, 12, 1416185, 116192, 3, 10, 13, 14, 151820*3, 7, 13, 17421*2, 5, 10, 11, 17, 196227, 13, 17, 1910235, 7, 10, 11, 14, 15, 17, 19, 20, 212224*5, 7, 11, 13, 17, 19, 232252, 3, 8, 12, 13, 17, 22, 2320267, 11, 15, 1912272, 5, 11, 14, 20, 231828*3, 5, 11, 17, 19, 236292, 3, 8, 10, 11, 14, 15, 18, 19, 21, 26, 272830*7, 13, 17, 234313, 11, 12, 13, 17, 21, 22, 243032*3, 5, 11, 13, 19, 21, 27, 29833*2, 5, 7, 8, 13, 14, 17, 19, 20, 26, 28, 2910343, 5, 7, 11, 23, 27, 29, 311635*2, 3, 12, 17, 18, 23, 32, 331236*5, 7, 11, 23, 29, 316

除了直接運算以外，至今還沒有一個辦法可以找到模特定m時的原根，但假如已知模m有一個原根，則可找出它其他的原根。

 最小原根 
模 p 的最小原根 g p 定義為在 1 到 p-1 中最小的原根。數學家已經給出最小原根的上界及下界的一些限制。

伯吉斯(1962)證明對任何 ε>0，存在一個 C>0，使得
。

Emil Grosswald (1981) 證明如果 ，則 。

参考资料及注释

 參見 

費馬小定理
同餘
離散對數

Category:同余