원시근

\(\operatorname{ord}_n a\) \(=\) \(\phi(n)\)인 경우에, \(a\)를 \(n\)의 원시근(primitive root)이라고 한다. \(n\)의 원시근은 \(n\)을 법으로 하여 구분한다. 예를 들어, 3은 7의 원시근인데, 7을 법으로 하여 3과 합동인 -4, 10, 17 등의 정수도 7의 원시근이 되며, 이들은 모두 3으로 취급한다.

성질 및 정리

• 자연수 \(n\)이 원시근을 가진다면, 정확하게 \(\phi(\phi(n))\)개의 합동이 아닌 원시근을 갖는다.
• \(r\)이 \(n\)의 원시근이라면, \(r^u\)이 원시근이라는 것은 \((u,ϕ(n))\) \(=1\)이라는 것과 동치이다.

같이 보기

• 위수
• 오일러 피 함수
• 합동