原根问题

常量

最近翻书，有个疑问：以2为原根的素数是否无穷多呢？如果是，占总素数的多少？

fleurly

难得遇到一个学数论的

fleurly

一个整数有原根， 那么它的一个既约剩余系对于模乘法成循环群， 原根就是生成元。
看看狐狸从代数的角度有没有办法解决这个问题。
对于质数p, { 1,2,....p-1 }对于模乘法成循环群， 那么2是生成元的充要条件或者充分条件是什么？

wanwna

我只统计一下原根所占比例，至于存在不存在极限，以及如何使用一个概率模型来说明这个我不知道：
以下是统计结果:
以内的所有情况   原根比例
100000          0.375626
200000          0.372943
300000          0.373158
400000          0.373361
500000          0.373826
600000          0.373885
700000          0.374317
800000          0.374115
900000          0.373671
1000000         0.373780
1100000         0.373638
1200000         0.374120
1300000         0.374731
1400000         0.374848
1500000         0.374622
1600000         0.375003
1700000         0.374603
1800000         0.374482
1900000         0.374318
2000000         0.374289
2100000         0.374102
2200000         0.374162
2300000         0.374235
2400000         0.374397
2500000         0.374476
2600000         0.374294
2700000         0.374141
2800000         0.374136
2900000         0.374044
3000000         0.374068
3100000         0.374183
3200000         0.374221
3300000         0.374204
3400000         0.374318
3500000         0.374247
3600000         0.374259
3700000         0.374108
3800000         0.374129
3900000         0.374215
4000000         0.374312
4100000         0.374378
4200000         0.374272
4300000         0.374333
4400000         0.374248
4500000         0.374305
4600000         0.374434
4700000         0.374467
4800000         0.374450
4900000         0.374684
5000000         0.374600

熊一兵

从数据看存在极限，我没理解原根，希望有人用《概率素数论》计算出来

常量

原根是指：当满足a^δ≡1(mod m)最小的δ为φ(m)时，a叫m的原根。
若a是m的原根，则a、a^2、……a^φ(m)是m的即约剩余系。
[br][br]-=-=-=-=- 以下内容由 常量 在 时添加 -=-=-=-=-
[br][br]-=-=-=-=- 以下内容由 常量 在 时添加 -=-=-=-=-
原根是指：当满足a^δ≡1(mod m)最小的δ为φ(m)时，a叫m的原根。
若a是m的原根，则1、a、a^2、……a^φ(m)是m的即约剩余系[br][br]-=-=-=-=- 以下内容由 常量 在 时添加 -=-=-=-=-
原根是指：当满足a^δ≡1(mod m)最小的δ为φ(m)时，a叫m的原根。
若a是m的原根，则1、a、a^2、……a^[φ(m)-1]是m的即约剩余系

申一言

   啊!
      原来与P进制单位P^n有关?
     P^n: 1,P,P^2,,,

常量

主题中将2改为3或其他素数都可成为类似的问题。
wanwna 统计出来的0.3746是以2为原根的素数占素数的比例，但这需要证明。
接着，试问以哪个自然数为原根的素数占素数的比例为最大呢?

常量

下面引用由wanwna在 2009/08/29 07:26pm 发表的内容：
我只统计一下原根所占比例，至于存在不存在极限，以及如何使用一个概率模型来说明这个我不知道：
以下是统计结果:
以内的所有情况   原根比例
100000          0.375626
...

这是wanwna算的，欣赏一下。

wanwna

[这个贴子最后由wanwna在 2009/09/03 09:10pm 第 2 次编辑] 代码如下(用C语言编写) 运行操作系统：SUSE Linux Enterprise Server 10 利用筛法筛出范围内所有质数 1~p-1在模乘下合成一Abel群，p-1是群的阶，则所有元的周期都是p-1的约数。 2的周期为p-1,称2为原根。 如果2的周期不是p-1,计为o(2) 则一定存在一个质数p2 使得p2|p-1且o(2)|(p-1)/p2 固只要把p-1因式分解，以每个不同的质数因子相除即可检验。 另外，对于2^((p-1)/p2)%p我以前介绍过幂模算法，这里求余数就是用的这种算法 代码写的很混乱，取名随意，并且没有注释，影响阅读请见谅

2. &#35;include <stdio.h>
3. &#35;include <stdlib.h>
4. &#35;include <string.h>
5. &#35;include <math.h>
6. &#35;ifndef WHICH_NUMBER
7. &#35;define WHICH_NUMBER 2
8. &#35;endif
9. int a[2000000]={2};
10. int b[14];
11. int bit_mod[32]={WHICH_NUMBER};
12. int main(int argc,char**argv)
13. {
14. char*s;
15. int c,i,j,k,m,n,x,y,p,q;
16. int c_a=0;
17. sscanf(argv[1],"%d",&c);
18. s=malloc(c);
19. for(i=3;i<=c;i++)
20. s[i]=1;
21. k=(int)(sqrt((double)c));
22. for(j=3;j<=k;j+=2) {
23. for(i=j*3;i<=c;i+=j*2)
24. s[i]=0;
25. }
26. /******All prime numbers less than c****/
27. j=1;
28. for(i=3;i<=c;i+=2)
29. if(s[i]==1) {
30. a[j++]=i;
31. }
32. free(s);
33. c=j;
34. /*printf("j=%d\n",j);
35. while(1) {
36. scanf("%d",&i);
37. printf("%d\n",a[i]);
38. }*/
40. for(i=8;i<c;i++) {
41. m=a[i];
42. x=n=m-1;
43. for(j=1;j<=31;j++)
44. bit_mod[j]=((long long)bit_mod[j-1])*((long long)bit_mod[j-1])%m;
45. for(j=0;j<7;j++)b[j]=0;
46. k=0;
47. for(j=0;;j++) {
48. if(x==1)
49. break;
50. while(1) {
51. if(x%a[j]==0) {
52. b[k]=a[j];
53. x/=a[j];
54. } else {
55. if(b[k])
56. k++;
57. break;
58. }
59. }
60. }//for(j=0;;j++)
61. for(j=0;j<k;j++) {
62. x=n/b[j];
63. //printf("x:%d\n",x);
64. y=1;
65. for(p=0;p<31;p++){
66. if((1<<p)&x)
67. y=(long long)y*(long long)(bit_mod[p])%m;
68. }
69. if(y==1) {
70. //printf("%s:%d\n",__FILE__,__LINE__);
71. break;
72. }
73. } //for(j=0;j<k;j++)
74. if(j<k) {
75. } else {
76. c_a++;
77. }
78. }//for(i=1;i<c;i++)
79. printf("%d\t%d\t%lf\n",c_a,c-1,(double)c_a/(double)(c-1));
80. return 0;
81. }

复制代码