정수 #3.위수와 원시근

 

위수란?

2 이상의 정수 m 에 대해서 m 과 서로소인 정수 a일때, aⁿ 이 m으로 나눈 나머지가 1이 되는 가장 작은 n 을 mod m에 대한 a의 위수 라고 한다. ord_m(a)=r이다. 

 

원시근이란?

원시근에 대해서 설명하기 전에, 오일러 함수에 대해서 알아야 한다. 자연수 n에 대한 오일러 함수 Φ(n) = (n보다 작거나 같은 자연수 중, n과 서로소인 수의 개수)로서 정의 되는데, a^Φ(m) 을 m으로 나눈 나머지가 1이 되지만, Φ(m)보다 작은 n에 대해서는 aⁿ 을 m으로 나눈 나머지가 1이 되지 않도록 하는 a가 존재할 때, a를 법 m(mod m)에 대한 원시근이라고 한다.