第5节　原根，基和指标

57

按照欧拉先生的说法，我们把属于指数p-1的数称为原根。那么，如果a是原根，方幂a，a2，a3，…，ap-1的最小剩余都各不相同。那么，容易推出在这些最小剩余中将出现1，2，3，…，p-1中的每个数，因为这两组数的所含数的个数相同。这就意味着，任意一个不被p整除的数一定同余于a的某个方幂。这个性质非同寻常，它非常有用，能简化与同余式有关的算术计算，正如对数的引入简化了普通的算术运算。我们任意选择某个原根a作为基或基数，用它表示所有不能被p整除的数。并且，如果ae≡b（mod p），就称e为b的指标。例如，如果对于模19我们取原根2作为基数，那么就有

而且，显然地，对于固定的基数，每个数有很多指标，但是它们都对于模p-1同余；所以，当遇到指标的问题，对于模p-1同余的指标可以视作是等价的，正如对于模p同余的数也被视作等价一样。