因此对于每一个d都有Φ(d)=ψ(【www.8455.com】d)

当前位置:澳门新葡8455最新网站 > 【www.8455.com】 > 因此对于每一个d都有Φ(d)=ψ(【www.8455.com】d)
作者: 澳门新葡8455最新网站|来源: http://www.xiaoyaozhuan.com|栏目:【www.8455.com】

文章关键词:澳门新葡8455最新网站,原根

  什么叫原根?什么样的正整数具有原根?我来介绍一下《数学100个基本问题》中提到的这个比较有趣的概念。

  假设a和m是互素的正整数,那么对于所有a的方幂,a,a^2,a^3,…除以m后所得的余数来说,因为余数的可能性只有m种,因此总能找到2个不同的方幂不妨设i,j使得m整除a^i-a^j=a^i[a^(j-i)-1]。又因为a和m互素,所以m整除a^(j-i)-1。由此证明了对于任意a和m互素,就存在正整数k使得a^k≡1(mod m)。我们把这个最小的k称作a模m的阶,或者a关于m的指数。

  阶k应该是什么样子的?假设有另外一个正整数n使得a^n≡1(mod m)。我们可以令n=kq+r,其中q和r都是整数且0≤rk,那么有下面推导:

  根据k的最小值假定,则r=0。所以k整除n,因此k是a模m的阶当且仅当a^k≡1(mod m),且对于所有a^n≡1(mod m)总有k整除n。

  在我之前的关于欧拉函数的文章中有提到过关于欧拉对于费马小定理的推广,即当a和m为互素正整数时,总有m整除a^Φ(m)-1,其中Φ(m)为欧拉函数。有上面的推导可得,k必定整除Φ(m),那么有趣的问题来了,什么时候k=Φ(m)呢?

  如果a模m的阶恰好等于Φ(m),则称a为m的一个原根。那么什么样的正整数有原根,我们能否求得它的所有原根?为什么要谈论这个问题,因为对于具有原根a的正整数m而言,a的Φ(m)个方幂:a,a^2,…,a^Φ(m)除以m所得的余数恰好是小于m且与m互素的全部正整数(因为如果余数和m有公因子,那么a也会有这个公因子,这与a和m互素矛盾)

  并不是所有的正整数都有原根,简单的计算可知m=8时就没有原根。欧拉在1773年首先证明了对于所有的素数p都是有原根的。在介绍欧拉的证明前我们要先做点准备工作。【www.8455.com】首先介绍一个同余方程解的一个性质。如果x是同余方程f(x)≡0(mod m)的一个解,且x除以m后所得的余数为r,即x=km+r,可得f(x)≡f(km+r)≡f(r)≡0(mod m),即r也是同余方程的一个解。因此我们在讨论同余方程的解的时候只讨论小于m的情况。下面说一下2个重要结论。

  1) 拉格朗日定理:设f(x)为n次整系数多项式,则同余方程f(x)≡0(mod p)至多有n个解。

  这是拉格朗日在1770年首先证明的。我们现在用归纳法来证明这个结论,设:

  首先考虑到1,2,3,…,p-1中的每个数模p的阶都整除Φ(p)=p-1。对于p-1的每一个因子d,我们用ψ(d)表示该p-1个数中模p的阶等于d的那些数的的个数。运用上面的结论2)我们可以得到:

  现在比较Φ(d)和ψ(d)的大小。对于p-1的每一个因子d,如果ψ(d)=0则ψ(d) Φ(d)。如果ψ(d)≠0,则存在一个模p的阶为d的正整数,假设为a。因为阶为d的数都是同余方程x^d≡1(mod p)的解。而上面结论2)告诉我们方程恰有d个解。因为a,【www.8455.com】a^2,…,a^d模p都是1,且两两不同,故为上述方程全部的解,因此我们知道凡是阶为d的正整数都可以写成a的方幂。而且若a^k的阶为d,则d和k互素。从而有Φ(d)个阶为d的方幂即Φ(d)=ψ(d)。因此我们证明了Φ(d)≥ψ(d)。再由欧拉函数的性质,我们可以得到:

  因此对于每一个d都有Φ(d)=ψ(d)。特别的Φ(p-1)=ψ(p-1)≠0,这说明存在模p的阶为p-1的正整数,即p有原根。高斯在1801年证明了一个正整数有原根当且仅当它型如1,2,4,p^e,2p^e,其中p为奇素数e为正整数。【www.8455.com】

  最后关于原根有个猜想在1927年由奥地利数学家阿廷提出:对于每个不等于1,p-1以及完全平方数的正整数a都存在有无穷多个素数p以a为原根。返回搜狐,查看更多

网友评论

我的2016年度评论盘点
还没有评论,快来抢沙发吧!