위수(수론)

누리위키, 온 누리의 백과사전

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


수론에서 어떤 정수 \(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)\).[1]
    • 사실, \(\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)\).

같이 보기

주석

  1. ^ \(\operatorname{ord}_n a = \phi(n)\)인 경우에, \(a\)를 \(n\)의 원시근(primitive root)이라고 한다.