잉여류(Residue class)

예를 들어서 5를 3으로 나누면 2가 남는다.

3으로 나누어 2가 남는 수는 또 뭐가 있을까?

8, 11, 14...가 있다.

즉 이들 수는 '3처럼 5로 나누어 2가 남는 수'라고 말할 수 있으며

'3의 법 5에 대한 잉여류/합동류'라고 표현하며

a 위에 작대기를 그어 표현한다.

$\bar{a}$

완전잉여계(Complete Residue System)

잉여류는 a와 m, 두 숫자가 있으면 정해진다.

m=10이라고 하자. a가 뭐가 되었든

잉여류는 10가지 중 하나다.

0이 남는 수들, 1이 남는 수들, 2가 남는 수들... 9가 남는 수들.

이렇게 법 m에 대한 m 가지 서로 다른 잉여류에서

하나씩 수를 뽑아 만든 집합을

법 m에 대한 완전잉여계라고 한다.

m=10이라면

0이 남는 수 중에는 30,

1이 남는 수 중에는 11,

...

9가 남는 수 중에는 289를 뽑아

완전잉여계를 만들 수 있다.

제일 간단한 완전잉여계는

$\{0, 1, \dots m-1 \}$일 것이다.

기약잉여계(Reduced Residue System)

완전잉여계는 일종의 대표선수다.

다들 m으로 나눈 나머지들의 대표다.

나머지가 0인 수들의 대표, 1인 수들의 대표...

완전잉여계가 하나 나오면

이 수 중에 m과 서로소인 것만 남기자.

예를 들어 법 4에 대한 완전잉여계가

{4, 17, 10, 35}라고 하면

기약잉여계는

{17, 35}다.

(*참고로 0은 서로소가 아니다)

m이 소수라면

완전잉여계가 곧 기약잉여계다.

기약잉여계의 원소 수는

오일러 파이 함수와 같다.

(오일러 파이 함수가 'n보다 작으며 서로소인 수의 개수'니 당연할지도.)

2보다 큰 m에 대한 기약잉여계에서

원소를 모두 더한 수는 m에 맞아떨어진다.

원시근(Primitive Root)

어떤 기약잉여계가 있다.

이때 이 기약잉여계의 모든 원소를 어떤 수의 거듭제곱으로 표현할 수 있다면,

그것을 원시근이라고 한다.

예를 들어 법 7이 있다.

7에 대한 완전잉여계는 {0, 1, 2, 3, 4, 5, 6}이다.

7은 소수이므로 기약잉여계는 {1, 2, 3, 4, 5, 6}이다.

법 7에 대한 원시근은 3인데, 3의 거듭제곱으로

모든 기약잉여계 수들을 합동식으로 쓸 수 있기 때문이다.

3^6 = 729 - 7로 나누어 1이 남는다.

3^2 = 9 - 7로 나누어 2가 남는다.

3 = 3 - 7로 나누어 3이 남는다.

3^4 = 81 - 7로 나누어 4가 남는다.

3^5 = 243 - 7로 나누어 5가 남는다.

3^3 = 27 - 7로 나누어 6이 남는다.

한 법에 대해 원시근은 없을 수도 있고, 여럿일 수도 있다.

(5도 법 7에 대한 원시근이다)

원시근 찾기

원시근을 찾는 특별한 공식은 아직 없지만,

일일이 찾는 것보다는 빨리 찾는 법이 있다.

첫째, 원시근이 존재할 조건

우선 원시근은 오직 m이

2, 4, $p^k$, $2p^k$일 때만 존재한다.

(p는 홀수 소수, 즉 2를 뺀 소수)

2, 3, 4, 5, 6, 7, 9, 10, 11, 13...가 원시근이 있다.

둘째, 다른 원시근 찾기

m보다 작으며 m과 서로소인 수의 개수, $\varphi (m)$을 구한다.

$\varphi (m)$와 서로소인 수 k를 구한다.

원시근 g가 존재한다면,

$g^k$도 원시근이다.

$\varphi (m)$와 서로소인 수 k는 $ \varphi (\varphi (m))-1$개가 존재하므로

원시근은 g를 포함해 $ \varphi (\varphi (m))$개가 존재한다.

(만약 존재한다면)