[정수론], 원시근

원시근을 하기에 앞서 먼저 배워야 할 것은 위수(order)이다.

(a, m) = 1이 성립되고  a^r ≡ 1 (mod m)을 만족하는 정수 중에서 가장 작은 양의 정수 r(나머지)을 법 m, p에 관한 a의 위수이다.

 

예시로 들자면 법 7에 관한 2의 위수를 구하여라

 

2^r ≡ 1(mod 7)을 만족하는 가장 작은 양의 정수 r을 구할 때 2^1 ≡ 1(mod 7), 2^2 ≡ 4 (mod 7),  2^3 ≡  1(mod 7)

법 7에 관한 2의 위수는 3 ≤ ∂(7) = 6이다. 즉 ord_7 2 = 3이다. 

 

법 7에 관한 3의 위수에서 3^r ≡ 1(mod 7)일 때 3^1 ≡  3 (mod 7), 3^2 ≡  2 (mod 7), 3^3 ≡  6 (mod 7), 3^4 ≡  4 (mod 7), 3^5 ≡  5 (mod 7), 3^6 ≡  1 (mod 7)이며 법 7에 관한 3의 위수는 r = 6이다.  

위수:ord_7 3 = 6인 것이다.

 

※계산할 때 오일러 피 함수로 모듈러 m, p를 먼저 구하고 나온 값 만큼 거듭제곱을 해야한다. (1 ~ m-1 까지)

 

n | ∂(m) 은 약수배수 관계이다. 또한 ∂(m)은 원소의 개수와 같다.

 

원시근과 위수는 꽤나 비슷하다. ord_m a =  ∂(m) 동일한 값이 나오면 원시근, ord_m a 일 때 위수인 것이다.

원시근은 2, 4, p^k, 2p^k만 존재하고 그 이상에 합성수는 존재하지 않는다. 

값이 있더라도 그 값은 해가 될 수 없다.

 

존재하는 경우는 집합 Z^* p인 기약잉여계 즉 소수일 때만 존재한다.