やまぶんさんのマイページ

ついでにまとめてみた。
原始根の個数は φ(p-1) で求められます。
ただし、φ(n) は1以上n-1以下の数でnと互いに素なものの個数です。

p = 2 ; 1
p = 3 ; 2
p = 5 ; 2 3
p = 7 ; 3 5

p = 11 ; 2 6 7 8
p = 13 ; 2 6 7 11
p = 17 ; 3 5 6 7 10 11 12 14
p = 19 ; 2 3 10 13 14 15

p = 23 ; 5 7 10 11 14 15 17 19 20 21
p = 29 ; 2 3 8 10 11 14 15 18 19 21 26 27

p = 31 ; 3 11 12 13 17 21 22 24
p = 37 ; 2 5 13 15 17 18 19 20 22 24 32 35

p = 41 ; 6 7 11 12 13 15 17 19 22 24 26 28 29 30 34 35
p = 43 ; 3 5 12 18 19 20 26 28 29 30 33 34
p = 47 ; 5 10 11 13 15 19 20 22 23 26 29 30 31 33 35 38 39 40 41 43 44 45

p = 53 ; 2 3 5 8 12 14 18 19 20 21 22 26 27 31 32 33 34 35 39 41 45 48 50 51
p = 59 ; 2 6 8 10 11 13 14 18 23 24 30 31 32 33 34 37 38 39 40 42 43 44 47 50 52 54 55 56

p = 61 ; 2 6 7 10 17 18 26 30 31 35 43 44 51 54 55 59
p = 67 ; 2 7 11 12 13 18 20 28 31 32 34 41 44 46 48 50 51 57 61 63

p = 71 ; 7 11 13 21 22 28 31 33 35 42 44 47 52 53 55 56 59 61 62 63 65 67 68 69
p = 73 ; 5 11 13 14 15 20 26 28 29 31 33 34 39 40 42 44 45 47 53 58 59 60 62 68
p = 79 ; 3 6 7 28 29 30 34 35 37 39 43 47 48 53 54 59 60 63 66 68 70 74 75 77

p = 83 ; 2 5 6 8 13 14 15 18 19 20 22 24 32 34 35 39 42 43 45 46 47 50 52 53 54 55 56 57 58 60 62 66 67 71 72 73 74 76 79 80
p = 89 ; 3 6 7 13 14 15 19 23 24 26 27 28 29 30 31 33 35 38 41 43 46 48 51 54 56 58 59 60 61 62 63 65 66 70 74 75 76 82 83 86

p = 97 ; 5 7 10 13 14 15 17 21 23 26 29 37 38 39 40 41 56 57 58 59 60 68 71 74 76 80 82 83 84 87 90 92


付録（プログラムのソース）

#include<stdio.h>

void main(void){
int p[25]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,
71,73,79,83,89,97};
int k,n,i,ni;



for(k=0;k<=24;k++){
printf("p = %d ; ",p[k]); 

for(n=1;n<p[k];n++){
i=1;
ni=n;
while(ni != 1){ /* n^iが1になるまでnをかけていく */
ni=ni * n;
ni=ni % p[k];
i=i+1;
}

if(i==p[k]-1){ /* i=p-1 ならnは原始根 */
printf("%d ",n);
}
}
printf("n");

}

}