기약잉여계

 


1. 정의
2. 추상적인 버전
3. 관련 문서

旣約剩餘界 / reduced residue system

1. 정의

$$\left\{a_1,a_2,\cdots,a_m\right\}$$을 법 $$m$$에 대한 완전잉여계라고 할 때, 이들 중 $$m$$과 서로소인 원소만 모은 집합 $$\left\{{a}'_1,{a}'_2,\cdots,{a}'_{\varphi\left(m\right)}\right\}$$[1]을 법 $$m$$에 의한 '''기약잉여계'''라 한다.
4를 예시로 들어보면, $$\left\{0,1,2,3\right\}$$은 완전잉여계, 그리고 4와 서로소가 아닌 0[2], 2를 제외한 $$\left\{1,3\right\}$$는 기약잉여계가 된다.
기약잉여계가 중요한 이유는, 이들에게는 곱셈 역원이 있다는 점때문이다. 예컨대, $$6$$에 대한 완전잉여계 $$\left\{0,1,2,3,4,5\right\}$$와 그것의 기약잉여계 $$\left\{1,5\right\}$$를 생각하자. $$\left\{1,5\right\}$$의 원소는 모두 곱셈 역원을 갖는다. 그러나, 다른 완전잉여계의 원소는 그렇지 않다. 이는, $$m$$과 $$a$$가 서로소일 때, 정수 $$x,\,y$$가 존재하여 $$ax+my=1$$ 즉, $$ax\equiv 1\left(m\right)$$이기 때문이다.

2. 추상적인 버전

정수환의 몫환의 단위원의 모임인 $$\left(Z/mZ\right)^{\times}$$이 $$m$$을 법으로 한 기약잉여계와 같다. 동치류들의 모임인 $$\left(Z/mZ\right)^{\times}$$의 동치류에서 대표원을 하나씩 선택하여 구성한 것이 기약잉여계라는 것을 쉽게 알 수 있다.

3. 관련 문서


[1] 오일러의 정리에 따라 $$\varphi\left(m\right)$$개의 서로소인 정수가 있다. [2] 의외라고 생각할 수 있는데, 최대공약수의 성질 중, $$\gcd\left(a,0\right)=\left|a\right|$$ 때문에 서로소가 아니다.

분류