원시근
원시근 (Primitive Root) 의 정의는 다음과 같습니다.
양의 정수 n에 대해, gcd (즉, a와 n이 서로소 ) 이고 \operatorname{ord}_n a = \phi(n)인 정수 a를 법 n에 대한 원시근이라 한다.
\gcd(a, b)는 최대공약수 , \operatorname{ord}_n a는 위수 , \phi(n)은 오일러 토션트 함수 입니다.
n의 원시근이 존재한다면, 원시근의 개수는 \phi(\phi(n))개라는 사실이 알려져있습니다.