<aside> 💡
n > 1이고 gcd(a,n) = 1일 때, 어떤 정수 a가 법 n에 대해 k의 위수를 가진다는 것은 k가 $a^k\ mod\ n \equiv 1$ 을 만족하는 최소의 자연수
</aside>
예시)
하지만 이렇게 하나하나 대입해서 찾는 방법은 매우 비효율적이다. $\phi(n)$이 n보다 작기는 하지만, n이 커지면 $\phi(n)$도 함께 커지므로 1부터 $\phi(n)$까지의 자연수를 일일이 대입하는 것은 현실적으로 불가능하다.
따라서 위수가 될 자연수의 후보를 줄일 필요가 있음.
<aside> 💡
n은 자연수이고 a는 gcd(a,n)=1을 만족하는 정수일 때, 자연수 h에 대하여 $a^h\ mod \ n \equiv 1$을 만족할 필요충분조건은 $ord_n(a) |h$이다. 그러므로 $ord_n(a)\ |\ \phi(n)$이 성립한다.
위 정리에 따라 n=13, a=3일 때 $\phi(13) = 12$, 12의 양의 약수는 1, 2, 3, 4, 6, 12이므로 3의 위수는 이 6개 중 하나이다. 실제로 법 13에 대하여 $3^1 \equiv 3 , 3^2 \equiv 9, 3^ 3 \equiv 1$이므로 $ord_{13}(3)=3$이다.
그러나 $\phi(n)$의 모든 약수가 위수가 될 수 있는 것은 아니다.
예시)
$ord_n(a) = \phi(n)$일 때, 이를 원시근이라고 한다.
예시)
n = 5일 때 $\phi(5) = 4$이고 gcd(2,5) = 1이면 다음이 성립
$$ 2^1\ mod\ 5 \equiv 2 \\ 2^2\ mod\ 5 \equiv 4 \\ 2^4\ mod\ 5 \equiv 1 $$
즉 $ord_5(2)=\phi(5)=4$
<aside> 💡
n은 자연수이고 a는 gcd(a,n)=1을 만족하는 정수일때 정수 a가 $ord_n(a)=\phi(n)$을 만족하면 a를 법 n의 원시근이라고 정의함
</aside>