数論における位数
定義 1
定理
$a^{n} \equiv 1 \pmod{p}$ とすると、$\text{ord}_{p} (a) \mid n$ である。
説明
例えば、$p=7$ を考える。 $$ \begin{align*} 1^{1} \equiv & 1 \pmod{ 7 } \\ 2^{3} \equiv & 1 \pmod{ 7 } \\ 3^{6} \equiv & 1 \pmod{ 7 } \\ 4^{3} \equiv & 1 \pmod{ 7 } \\ 5^{6} \equiv & 1 \pmod{ 7 } \\ 6^{2} \equiv & 1 \pmod{ 7 } \end{align*} $$ ここで、$6$ の位数は $2$ であり、$2, 4$ の位数は $3$ で、$3,5$ の位数は $6$ である。
上の定理では、とくに $n=p-1$ とすると、$2,3,6$ が $p-1= 6$ を割ることを容易に確認できる。また、フェルマーの小定理によれば、素数 $p$ に対して常に $a^{p-1} \equiv 1 \pmod{p}$ が成り立つので、$\text{ord}_{p} (a) \mid (p-1)$ であることがわかる。
証明
$G := \gcd ( \text{ord}_{p} (a) , n )$ とすると、$G = \text{ord}_{p}(a) \cdot s + n \cdot t$ を満たす $s,t$ が存在する。
位数の定義と仮定により、 $$ a^{G} = a^{ \text{ord}_{p}(a) \cdot s + n \cdot t} = \left( a^{ \text{ord}_{p}(a) } \right)^s \cdot \left( a^{n} \right)^{t} \equiv 1 \cdot 1 \pmod{p} $$ $\text{ord}_{p}(a)$ は $a^{e} \equiv 1 \pmod{p}$ を満たす最小の自然数 $e$ として定義されたので、$G = \text{ord}_{p}(a)$ であり、$\text{ord}_{p}(a) \mid p$ である。
■
コード
以下は、R言語で位数を計算するためのコードである。素因数分解のコードが使われた。
prime = read.table("../attachment
/cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
factorize<-function(p)
{
q=p
factors<-numeric(0)
i=1; j=1
while(q!=1)
{
if(q%%prime[i]) {i=i+1}
else
{
q<-q/prime[i]
factors[j]<-prime[i]
i=1
j=j+1
}
}
return(factors)
}
order<-function(g,p,h=1) #Calculate a order of g in modulo p
{
qe<-table(factorize(p-1))
qe<-rbind(as.numeric(names(qe)),qe)
divisor<-qe[1,1]^(0:qe[2,1])
if((length(qe)/2)==1) {return(qe[1,1]^qe[2,1])}
for(i in 2:(length(qe)/2)) {divisor=c(divisor%*%t(qe[1,i]^(0:qe[2,i])))}
for(i in divisor) {if((FPM(g,i,p))%%p==1) break;}
return(i)
}
order(1,7)
order(2,7)
order(3,7)
order(4,7)
order(5,7)
order(6,7)
以下は上記のコードを実行した結果である。