阶

定义

设m > 1 且 (a, m) = 1, 则使得at≡1(modm)
成立的最小的正整数t称为a对模m的阶, 记为δm(a)。

定理

定理1 若m>1且(a, m) = 1, 且an≡1(modm), n > 0, 则δm(a)|n。
定理2 由定理1易知δm(a)|ϕ(m)。

推论

推论1 若p和q为奇素数，且q|(ap−1), 则或有q|(a−1),或有q=2kp+1, 其中k为某整数。
推论2 2p−1的任何因子必取2kp+1的形式。

原根

定义

如果a的阶(mod m)为ϕ(m), 则称a为m的一个原根。
即若δm(a)=ϕ(m), 则称a为m的一个原根。

定理

定理1 若g是m的一个原根，则g,g2,⋯,gϕ(m)各数对模m的最小剩余，恰是小于m且与m互素的ϕ(m)个正整数的一个排列。
定理2* 每一个素数p都有ϕ(p−1)个原根。事实上, 每一个数m都有ϕ(ϕ(m))个原根(如果有的话)。
定理3 一个数m有原根的充要条件是m=1,2,4,pe,2pe, 其中p为奇素数， e为正整数。

推论

推论1 若d|(p−1),则xd≡1(modp)恰有d个解
推论2 若p为素数,d|(p−1),则阶为d的最小剩余(mod p)的个数为ϕ(d)。

原根的求法

求一个数m的原根，先求ϕ(m)的素幂分解式，即ϕ(m)=pe11pe22⋯pekk
然后枚举g，若g满足恒有gϕ(m)pi≠1(modm),i=1,2,⋯,k
则g为m的一个原根。
//数据不大的时候枚举所有ϕ(m)的因子(除本身)也可。

Primitive Roots POJ - 1284
原根 51Nod - 1135