기약잉여계

• 상위 문서 : 수학 관련 정보, 정수론

기약없는 잉여

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\}$$ 을 법 $$m$$ 에 의한 기약잉여계라 한다.

4를 예시로 들어보면,

$$\left\{0,1,2,3\right\}$$ 은 완전잉여계, 그리고 4와 서로소가 아닌 0, 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 관련 문서

• 완전잉여계
• 2차 잉여
• 오일러의 정리
• 페르마의 소정리