위수(수론)

다른 뜻에 대해서는 위수 문서를 참조하십시오.

수론에서 어떤 정수 \(a\)의 \(n\)을 법으로 한 위수(the order of \(a\) modulo \(n\)), \(\operatorname{ord}_n a\)란 \(a^k \equiv 1\; (\operatorname{mod} n)\)을 만족하는 최소의 양의 정수 \(k\)이다. 예를 들어, \(2^1\not\equiv 1\), \(2^2\not\equiv 1\), \(2^3\equiv 1\) \((\operatorname{mod} 7)\)이므로, \(\operatorname{ord}_7 2=3\)이다.

성질 및 정리

1. \(\operatorname{ord}_n a \le \phi(n)\).
   • 사실, \(\operatorname{ord}_n a\)는 \(\phi(n)\)의 약수이다.
2. 임의의 정수 \(k\)에 대하여, \(a^{k(\operatorname{ord}_n a)} \equiv 1\) (\(\operatorname{mod} n)\).
   • 역으로, \(a^x \equiv 1\) (\(\operatorname{mod} n)\)라면, 어떤 정수 \(k\)가 있어서 \(x=k(\operatorname{ord}_n a)\)이다.
3. \(a^i \equiv a^j\) (\(\operatorname{mod} n)\) \(\iff\) \(i \equiv j\) (\(\operatorname{mod} \operatorname{ord}_n a)\).

같이 보기

• 오일러 피 함수
• 원시근
• 합동