📂整数論

数論における位数

定義¹

$\gcd (a, p) = 1$とする。$a^{e} \equiv 1 \pmod{p}$を満たす最小の自然数$e$を$\text{ord}_{p} (a)$と書き、法$p$における$a$の位数^orderと定義する。

定理

$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 \ge \text{ord}_{p}(a)$、したがって$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)

以下は上のコードを実行した結果である。