原根若干性质及最小原根的求解

重要修正:本想把原根的概念推广到所有正整数,之后就可作为解决一般性问题xk≡b(mod m)的基础(我原本就是打算写这个主题,先写本文是为了引出先导性的知识)。然而测试之后发现m为9407的时候,这个数根本没有原根!这之后就纠结了?到底是哪里出了问题?之后一直仔细排查,发现是这个定理出了问题!如果m是任意整数,那么n次多项式就可能有超过n个根!现在是,原根的概念虽然还可以推广,但是推广后,推广的原根定理却站不住脚了(不是所有数都有原根!),这就不能一般性的解决所有xk≡b(mod m)问题。下面我把该文原来错误的部分留着,但是加上删除线标记,同时修正的部分加上下划线标记!

原根本是关于素数的一个概念,但是可以推广到所有正整数中。若是不想看证明,请先确保瞟一眼原根的定义,然后直接移至最小原根的求法,如果时间稍微充裕,也可浏览一遍各定理,但是强烈建议看一遍证明!

欧拉Φ函数求和公式:设d1,...,dr是d的因数,则有Φ(d1)+...+Φ(dr)=d。

证明:令f(d)=Φ(d1)+...+Φ(dr),d1,...,dr是d的因数。于是现在即要证明f(d)=d。设有m和n且gcd(m,n)=1,mi和nj分别是m和n的任意因数。显然gcd(mi,nj)=1,因此Φ(minj)=Φ(mi)Φ(nj)。而mn的所有因数就是m的其中一个因数乘以n的其中一个因数的不同组合,因此不难得到f(mn)=f(m)f(n)!

若d为素数的幂次,显然f(d)=d。否则,把d分解成素数乘积,由于彼此互素,因此由上述结论可知f(d)=d,证毕!

多项式模m为0的解个数定理:f(x)为最高次数为n次的多项式,m为任意正整数素数,则f(x)≡0(mod m)最多有n个解。

证明:n=1时显然成立。设当n≤k时,f(x)≡0(mod m)最多有n个解。设g(x)为最高次数为k+1的多项式,若g(x)≡0(mod m)无解,则证明了n=k+1时也成立。否则,设其中一个解为a,并设g(a)=km,即a是多项式g(x)-km=0的一个解。因此可令g(x)-km=(x-a)h(x),其中h(x)是一个最高次数为k的多项式。于是有

g(x)≡g(x)-km≡(x-a)h(x)(mod m).

由于h(x)的次数≤k且m是素数(m是素数意味着m|(x-a)或m|h(x),可同时成立),因此(x-a)h(x)≡0(mod m)至多有k+1个解,也即g(x)至多有k+1个解!由数学归纳法知定理成立,证毕!

次数:对任意正整数a与m,其中gcd(a,m)=1,使得ae≡1(mod m)的最小指数e≥1叫做a模m的次数,记作em(a)。

次数整除性质:若有an≡1(mod m),则次数em(a)整除n。特别的,次数总整除Φ(m)。

证明:令g = gcd(n,em(a)),则求得x, y使得nx + em(a)y = g,于是有anx≡1≡ag(mod m),由次数的最小性可得g = em(a),即有em(a)|n。又欧拉公式告诉我们aΦ(m)≡1(mod m),结合上边推理可知次数总整除Φ(m)。证毕!

原根:使得em(g)=Φ(m)数g称为模m的原根。

原根定理:每个正整数m素数m都有恰好Φ(Φ(m))即Φ(m-1)个原根。

证明:若gcd(a,m)=1,根据次数整除性质可知em(a)|Φ(m)。因此,若a是模m的原根,则a的次数整除Φ(m)。令

Ψ(d)=#{em(a)=d}, 其中d|Φ(m), 1≤a≤m且gcd(a,m)=1.

Ψ(d)的含义是指,次数为d的不大于m的数的个数,其中d整除Φ(m)。由Ψ的定义可知Ψ(Φ(m))即为m的原根个数

设Φ(m)=kd,有xΦ(m)-1≡(xd-1)((xd)k-1+...+xn+1)(mod m)。注意到xΦ(m)-1≡0(mod m)恰好有Φ(m)个解。而由上述多项式模m为0的解个数定理可知,由于m是素数,xd-1≡0(mod m)至多有d个解,同理(xd)k-1+...+xn+1≡0(mod m)至多有d(k-1)个解。而Φ(m)=kd,因此,xd-1≡0(mod m)必有恰好d个解!这告诉我们:若d|Φ(m),则同余式xd-1≡0(mod m)恰好有d个根满足0≤x<m!另外,次数整除性质告诉我们,若ad-1≡0(mod m),则有em(a)|d。若d有r个因数,分别为:d1,...,dr,于是由Ψ的定义我们知道,xd-1≡0(mod m)的解的个数,即d等于Ψ(d1)+...+Ψ(dr)!总结一下:若d|Φ(m),d1,...,dr是d的因数(包括1和d),则有

d=Ψ(d1)+...+Ψ(dr).

这似乎就是上面的欧拉Φ函数求和公式!很容易由数学归纳法证明Φ和Ψ是相同的。当n=1时,Φ(n)=Ψ(n)=1显然成立。若对所有d<n有Φ(d)=Ψ(d),设n的因数为d1,...,dr,不妨设d1=n,因此有Ψ(n)+Ψ(d2)+...+Ψ(dr)=n=Φ(n)+Φ(d2)+...+Φ(dr)。由于Φ(di)=Ψ(di),2≤i≤r,所以有Ψ(n)=Φ(n)!因此,我们证明了Ψ(Φ(m))就为Φ(Φ(m)),即Φ(m-1),证毕!

对任意正整数m,若m有原根g,由原根定义容易得出

g,g2,...,gΦ(m)(mod m)

是所有小于m且与m互素的Φ(m)个数!用群论的观点来讲,所谓原根,就是一个群的生成元,这个群的元素是所有与m互素的数,元素间的运算是相乘并模m!因此,若是有与m互素的数a,那么必有一个指数e,使得ge≡a(mod m)。我们把这个指数e叫做以g为底的a模m的指标。假设m和g已经给定,则记指标为I(a)。

设I(a)是a的指标,I(b)是b的指标,由指标定义可知

gI(a)+I(b)≡gI(a)gI(b)≡ab≡gI(ab)(mod m),

因此gI(ab)-I(a)-I(b)≡1(mod m)。然而g是原根,所以I(ab)-I(a)-I(b)必是Φ(m)的倍数,因此有I(ab)≡I(a)+I(b)(mod Φ(m))。类似可得I(ak)≡kI(a)(mod Φ(m))。于是有下述定理:

指标法则
(1) I(ab)≡I(a)+I(b)(mod Φ(m)) [乘积法则]
(2) I(ak)≡kI(a)(mod Φ(m)) [幂法则]

根据原根的定义,要求n最小原根,只需从1遍历至n,直到发现第一个与n互素且次数为Φ(n)的数为止。那么必须要求出次数吗?不需要!我们只需判断!判断次数是否为Φ(n)!

根据次数整除性质,设p1,...,pr是Φ(n)分解成素数乘积后的r个不同的素数,根据次数整除性质,容易证明,只要存在某一pi,使得aΦ(n)/pi≡1(mod n),a必然不是原根!换句话说,若对所有pi,aΦ(n)/pi都不与1模n同余,则a就为模n的原根若遍历完所有从1至n的与n互素的元素依然没找到原根,则说明数n不存在原根!



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*