[原创]一类特殊的原根数量可先知φ(m)=m-1=2^k时m的原根数量为2^(k-1)

白新岭

[watermark]如果在欧拉函数中，变量为素数，且P-1=2^k,则m的原根数量为2^(k-1),例如φ（3）=2^1,所以3有2^0个原根；φ（5）=2^2,5有2^1个原根；φ（17）=2^4,3有2^3个原根；φ（257）=2^8,257有2^7个原根；φ（65537）=2^16,65537有2^15个原根。当然其他周期出现的数目也可以确定，规定a^k≡1(modm),(a,m)=1,k从1取到φ（m),式子a^k≡1(modm)出现的次数为a^k相对模m循环周期，则不同周期t对应的a的数量可以确定：
周期值    a的数目
  1       2^(k-1)
  2       2^(k-2)
  4       2^(k-3)
  ................
.................
2^(k-2)     2
2^(k-1)     1
2^k         1
不同周期出现a的数目和为2^k.[/watermark]

白新岭

[这个贴子最后由白新岭在 2009/12/15 03:39pm 第 1 次编辑]

白新岭

上贴转自维基百科，有链接，有些同余符号，幂数等字母表示已丢，所以还是打开连接看比较好。
除了定义了原根a以外，还定义了Ordm(a)，它表示最小周期值（即余数1出现的最小指数d），当(a,m)=1,且a^d≡1(modm),满足前面两个条件的最小值d就是Ordm(a)表示的值。从转入的内容中知，Ordm(a)一定是 φ(m)的因子，即循环周期d【当a^d≡1(modm)】一定能整除φ(m)，所以上面说对于3的（相对于模7）Ordm(a)只考虑1，2，3，6的次数即可，不必考虑次数4，5，因为φ(7)=6，没有因子4，5；另外，既然是这样如果在φ(m)=m-1=2^k时，只要在前2^（k-1）+1以内不出现同余数1，就说明这个a就是m的一个原根。
另外从转入的内容中，好像是说，如果一个m有原根，则原根数目为φ（φ（m)).这样的话，我的主贴等于什么也没说，不过有些内容还是没有谈到的，是自己经过研究分析得到的，如m的互质数分布问题（以不同的循环周期为划分标准，即a^k≡1(modm)中，当k从1取到φ（m)时，出现同余1的次数（不同k值出现的次数，此时的k能使a^k≡1(modm)成立。

白新岭

下面是维基百科的单位根介绍，公式，符号等不能复制过来，有兴趣的可以打开连接自己看，其中最后部分，单位根和有点遗漏，应该是单位根的n次方，才能等于0，好像拉掉了，大家觉的呢？ 单位根 维基百科，自由的百科全书 跳转到： 导航, 搜索 复平面上的三次单位根数学上，单位的 次根是次幂为 的复数。它们位于复平面的单位圆上，构成正n边形的顶点，其中一个顶点是 。 目录 [隐藏] 1 定义 2 本原根 3 例子 4 和式 [编辑] 定义 这方程的复数根 为单位的 次根。 单位的 次根有 个： 。 [编辑] 本原根 单位的 次根以乘法构成n阶循环群。它的生成元是单位的 次本原根。单位的 次本原根是，其中和互质。单位的次本原根数目为欧拉函数。 [编辑] 例子 单位的一次根有一个。 单位的二次根有两个：和，只有是本原根。 单位的三次根是 其中是虚数单位；除外都是本原根。 单位的四次根是 其中和是本原根。 [编辑] 和式 当不小于，单位的次根总和为。这一结果可以用不同的方法证明。一个基本方法是等比级数： 。 第二个证法是它们在复平面上构成正多边形的顶点，而从对称性知这多边形的重心在原点。 还有一个证法利用关于方程根与系数的韦达定理，由分圆方程的项系数为零得出。 取自