기약없는 잉여
Reduced Residue System
1 개요
여타 다른 정수론 관련 내용이 그렇듯이, 일반인들은 평생 볼 일 없는 개념. 대학에서 수학을 전공하거나 아니면 중·고등학생 때 경시대회를 준비한다면 보게 될 것이다. 자세한 정의는 다음과 같다.
| [math]\left\{a_1,a_2,\cdots,a_m\right\}[/math]을 법 [math]m[/math]에 대한 완전잉여계라고 할 때, 이들 중 [math]m[/math]과 서로소인 원소만 모은 집합 [math]\left\{{a}'_1,{a}'_2,\cdots,{a}'_{\varphi\left(m\right)}\right\}[/math][1]을 법 [math]m[/math]에 의한 기약잉여계라 한다. |
4를 예시로 들어보면, [math]\left\{0,1,2,3\right\}[/math]은 완전잉여계, 그리고 4와 서로소가 아닌 0[2], 2를 제외한 [math]\left\{1,3\right\}[/math]는 기약잉여계가 된다.
기약잉여계가 중요한 이유는, 이들에게는 곱셈 역원이 있다는 점때문이다. 예컨대, [math]6[/math]에 대한 완전잉여계 [math]\left\{0,1,2,3,4,5\right\}[/math]와 그것의 기약잉여계 [math]\left\{1,5\right\}[/math]를 생각하자. [math]\left\{1,5\right\}[/math]의 원소는 모두 곱셈 역원을 갖는다. 그러나, 다른 완전잉여계의 원소는 그렇지 않다. 이는, [math]m[/math]과 [math]a[/math]가 서로소일 때, 정수 [math]x,\,y[/math]가 존재하여 [math]ax+my=1[/math] 즉, [math]ax\equiv 1\left(m\right)[/math]이기 때문이다.
2 추상적인 버전
정수환의 몫환의 단위원의 모임인 [math]\left(Z/mZ\right)^{\times}[/math]이 [math]m[/math]을 법으로 한 기약잉여계와 같다. 동치류들의 모임인 [math]\left(Z/mZ\right)^{\times}[/math]의 동치류에서 대표원을 하나씩 선택하여 구성한 것이 기약잉여계라는 것을 쉽게 알 수 있다.
3 관련 문서
- ↑ [math]\\varphi\\left(m\\right)[/math]개의 서로소인 정수가 있다.
- ↑ 의외라고 생각할 수 있는데, 최대공약수의 성질 중, [math]\gcd\left(a,0\right)=\left|a\right|[/math] 때문에 서로소가 아니다.