定义
设 m>0, gcd(m,a)=1, l 是使 al≡1(modm) 成立的最小正整数. 则 l 叫做 a 对模数 m 的次数(也叫阶). 记作 ordm(a)=l.
注:当 gcd(m,a)=1 时,ak≡1(modm) 永远不成立,此时次数无定义。
性质 1
设 ordm(a)=l,则
ak≡1(modm)⟺l∣k
证明:(⇐) 若 l∣k,设 k=ql,则 ak=(al)q≡1q=1(modm).
(⇒) 若 ak≡1(modm),由带余除法 k=ql+r, 0≤r<l,则
1≡ak=aql+r=(al)q⋅ar≡ar(modm)
而 l 是使同余式成立的最小正整数,故 r=0,即 l∣k. □
性质 2
ordm(a)∣φ(m)
证明:由欧拉定理,aφ(m)≡1(modm),再由性质 1 即得. □
性质 3
设 ordm(a)=l,则
ai≡aj(modm)⟺i≡j(modl)
证明:不妨设 i≥j,则 ai≡aj(modm)⟺ai−j≡1(modm)(因为 gcd(a,m)=1,aj 可约去),由性质 1 即得. □
性质 4
设 ordm(a)=l,则对任意正整数 k,
ordm(ak)=gcd(l,k)l
证明:令 d=gcd(l,k), l=l1d, k=k1d,其中 gcd(l1,k1)=1.
设 ordm(ak)=t. 由 (ak)l1=(al)k1≡1(modm),知 t∣l1.
又 (ak)t=akt≡1(modm),由性质 1 有 l∣kt,即 l1d∣k1dt,故 l1∣k1t.
而 gcd(l1,k1)=1,所以 l1∣t.
综上 t=l1=gcd(l,k)l. □
推论:ak 的次数等于 l 当且仅当 gcd(l,k)=1.
性质 5
设 ordm(a)=l1, ordm(b)=l2,且 gcd(l1,l2)=1,则
ordm(ab)=l1l2
证明:设 ordm(ab)=t.
一方面,(ab)l1l2=(al1)l2⋅(bl2)l1≡1(modm),故 t∣l1l2.
另一方面,由 (ab)t≡1(modm),有
1≡(ab)tl2=atl2⋅btl2≡atl2(modm)
故 l1∣tl2,又 gcd(l1,l2)=1,故 l1∣t. 同理 l2∣t.
由 gcd(l1,l2)=1,得 l1l2∣t.
综上 t=l1l2. □
性质 6
设 p 是一个素数,若存在 a 满足 ordp(a)=l,则恰有 φ(l) 个对模数 p 两两不同余的整数,它们对模数 p 的次数都是 l.
证明:考虑 l 个数
a0, a1, a2, …, al−1
它们两两不同余(由性质 3,ai≡aj⟺l∣i−j,而 0<∣i−j∣<l),且对每个 k 有 (ak)l=(al)k≡1(modp),即它们都是同余式
xl≡1(modp)
的解.
而 (1) 是模素数 p 的 l 次同余式,由多项式同余理论,它最多有 l 个解. 故这 l 个数就是 (1) 的全部解.
由性质 4,ordp(ak)=gcd(l,k)l,故 ak 的次数等于 l 当且仅当 gcd(l,k)=1.
而在 0,1,…,l−1 中与 l 互素的 k 恰有 φ(l) 个. □
性质 7
设 l∣p−1,则次数为 l 的模 p 互不同余的整数个数为 φ(l) 个.
证明:由性质 2,对任意 gcd(a,p)=1 有 ordp(a)∣p−1.
我们在第五章后面将证明模素数必有原根(即存在 g 使 ordp(g)=p−1). 取原根 g,则
a=glp−1
的次数为 ordp(a)=gcd(lp−1, p−1)p−1=lp−1p−1=l.
因此对任意 l∣p−1,次数为 l 的元素必然存在. 再由性质 6,其个数恰为 φ(l). □
注:当 l=p−1 时,φ(p−1) 就是模 p 原根的个数.