위수(수론)
누리위키, 온 누리의 백과사전
다른 뜻에 대해서는 위수 문서를 참조하십시오.
수론에서 어떤 정수 \(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\)이다.
성질 및 정리[편집]
- \(\operatorname{ord}_n a \le \phi(n)\).[1]
- 사실, \(\operatorname{ord}_n a\)는 \(\phi(n)\)의 약수이다.
- 임의의 정수 \(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)\)이다.
- \(a^i \equiv a^j\) (\(\operatorname{mod} n)\) \(\iff\) \(i \equiv j\) (\(\operatorname{mod} \operatorname{ord}_n a)\).