원시근

원시근 (Primitive Root) 의 정의는 다음과 같습니다.

양의 정수 $n$에 대해, $\gcd(a, n) = 1$ (즉, $a$와 $n$이 서로소 ) 이고 $\operatorname{ord}_n a = \phi(n)$인 정수 $a$를 법 $n$에 대한 원시근이라 한다.

$\gcd(a, b)$는 최대공약수 , $\operatorname{ord}_n a$는 위수 , $\phi(n)$은 오일러 토션트 함수 입니다.
$n$의 원시근이 존재한다면, 원시근의 개수는 $\phi(\phi(n))$개라는 사실이 알려져있습니다.