정수론에서의 위수
정의 1
$\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)
다음은 위의 코드를 실행시킨 결과다.
Silverman. (2012). A Friendly Introduction to Number Theory (4th Edition): p211. ↩︎