| 정수론 Number Theory | |||
| {{{#!wiki style="margin: 0 -10px -5px; min-height: calc(1.5em + 5px)" {{{#!folding [ 펼치기 · 접기 ] {{{#!wiki style="margin: -5px -1px -11px" | 공리 | ||
| 페아노 공리계 · 정렬 원리 · 수학적 귀납법 · 아르키메데스 성질 | |||
| 산술 | |||
| 나눗셈 | 약수·배수 | 배수 · 약수(소인수) · 소인수분해(목록 · 알고리즘) · 공배수 · 공약수 · 최소공배수 · 최대공약수 | |
| 약수들의 합에 따른 수의 분류 | 완전수 · 부족수 · 과잉수 · 친화수 · 사교수 · 혼약수 · 반완전수 · 불가촉 수 · 괴짜수 | ||
| 정리 | 베주 항등식 · 산술의 기본정리 · 나눗셈 정리 | ||
| 기타 | 유클리드 호제법 · 서로소 | ||
| 디오판토스 방정식 | 페르마의 마지막 정리 · 피타고라스 세 쌍 · 버치-스위너턴다이어 추측(미해결) | ||
| 모듈러 연산 | |||
| 잉여역수 · 2차 잉여 · 기약잉여계 · 완전잉여계 · 중국인의 나머지 정리 · 합동식 · 페르마의 소정리 · 오일러 정리 · 윌슨의 정리 | |||
| 소수론 | |||
| 수의 분류 | 소수 · 합성수 · 메르센 소수 · 쌍둥이 소수(사촌 소수 · 섹시 소수) · 페르마 소수 · 레퓨닛 수 | ||
| 분야 | 대수적 정수론(국소체) · 해석적 정수론 | ||
| 산술함수 | 뫼비우스 함수 · 소수 계량 함수 · 소인수 계량 함수 · 약수 함수 · 오일러 파이 함수 · 폰 망골트 함수 · 체비쇼프 함수 · 소수생성다항식 | ||
| 정리 | 그린 타오 정리 · 페르마의 두 제곱수 정리 · 디리클레 정리 · 소피 제르맹의 정리 · 리만 가설(미해결) · 골드바흐 추측(미해결)(천의 정리) · 폴리냑 추측(미해결) · 소수 정리 | ||
| 기타 | 에라토스테네스의 체 · 윌런스의 공식 | ||
完全剩餘界 / Complete Residue System
1. 개요
1보다 큰 자연수 [math(m)]에 대하여, 집합 [math(\left\{a_1,a_2,\cdots,a_m\right\})]이 임의의 정수 [math(a)]에 대하여 [math(a\equiv a_i\left(\text{mod}\,m\right))]인 [math(a_i)]가 유일하게 존재할 때, 위 집합을 법 m에 대한 완전잉여계라 한다. 이것은 [math(m)]개의 정수 [math(a_1,a_2,\cdots,a_m)]이 [math(i\neq j)]이면, [math(a_i \not\equiv a_j \left(\text{mod}\,m\right))][1]을 만족하는 것과 동치이다.
위의 내용을 간단히 풀어쓰자면, ''법 [math(m)]에 대한 완전잉여계"란 각 원소를 [math(m)]으로 나누었을 때 나머지들이 정확히 [math(\left\{0, 1, 2,\cdots,m-1\right\})]이 되는 집합이다.
법 [math(m)]에 대한 대표적인 완전잉여계는 [math(\left\{0,1,2,\cdots,m-1\right\})]이 있다. [math(m)]으로 나눈 나머지는 반드시 [math(0, 1,\cdots, m-1)]밖에 없기 때문이다.
하지만 완전잉여계가 반드시 위와 같은 꼴인 것만은 아니다. 예를 들어 법 5에 대한 대표적인 완전잉여계는 [math(A=\{0,1,2,3,4\})]인데, [math(B=\{0,1,3,4,7\})]도 각 원소를 5로 나눈 나머지의 집합을 C라 하면 [math(C=\{0,1,3,4,2\})]로 원소가 중복되지 않으므로 역시 완전잉여계이다.
2. 완전잉여계가 되는 경우
집합 A가 완전잉여계가 되려면 A의 각 원소를 법 m으로 나눈 나머지의 집합을 B라 할 때, B의 원소의 범위가 m 미만의 음이 아닌 정수이고, 원소의 개수가 m과 같아야 하면서 중복되는 원소가 생기지 않아야 하므로 [math(B=\left\{b_1,b_2,\cdots,b_k,\cdots,b_m\right\}(1\leq k\leq m))]라 하면 모든 k에 대하여 [math(b_k)]가 일대일 대응되어야 한다. 이런 경우로는 다음을 들 수 있다.- 이때, 집합 B를 만드는 방법의 수는 m!이며, 집합 A를 만드는 방법의 수는 B의 각 원소에 mk(k는 정수)를 더하거나 빼면 되므로 무수히 많다.
- 정수 k에 대하여 [math(A=\{0, k, 2k, ..., (m-1)k\})]이면서 m과 k가 서로소인 경우: 0, k, 2k, ..., (m-1)k를 m으로 나눈 나머지가 모두 서로 다르므로 완전잉여계이다. 단, 서로소가 아닌 경우는 m으로 나눈 나머지가 서로 같은 원소가 반드시 생기므로 완전잉여계가 아니다. 예를 들어 4와 10은 서로소가 아닌데, [math(A=\{0, 10, 20, 30\})]가 법 4에 대한 완전잉여계인지 알아보기 위해 각 원소를 4로 나눈 나머지를 집합 형태로 표현하면 [math(B=\{0, 2, 0, 2\})]이고, 중복되는 원소가 있으므로 완전잉여계가 아니다.
- k가 음수일 때도 물론 성립한다.
- m이 홀수일 때, [math(\displaystyle A=\{-\frac{m-1}{2}, -\frac{m-3}{2}, ..., -2, -1, 0, 1, 2, ..., \frac{m-3}{2}, \frac{m-1}{2}\})]는 법 m에 대한 완전잉여계이다. A의 모든 음수 항에 각각 m을 더해서 만든 집합을 C라 하면 [math(\displaystyle C=\{\frac{m+1}{2}, \frac{m+3}{2}, ..., m-2, m-1, 0, 1, 2, ..., \frac{m-3}{2}, \frac{m-1}{2}\})]이고, 원소를 다르게 나열하면 [math(\displaystyle C=\{0, 1, 2, ..., \frac{m-3}{2}, \frac{m-1}{2}, \frac{m+1}{2}, \frac{m+3}{2}, ..., m-2, m-1\})]이며, 이때 원소가 모두 정수이고 서로 중복되지 않으므로 완전잉여계임을 알 수 있다.
3. 완전잉여계와 기약잉여계의 관계
법 m에 대한 어떤 완전잉여계 A에 대하여 A의 부분집합인 법 m의 기약잉여계가 존재한다. 예를 들어 법 6에 대한 완전잉여계 [math(A=\{0, 1, 2, 3, 4, 5\})]에 대하여 A의 부분집합인 법 6에 대한 기약잉여계는 [math(B=\{1, 5\})]이다. m이 소수일 때는 A에서 원소 0을 제외한 나머지로 이루어진 집합이 기약잉여계이다.4. 추상적인 버전
정수환의 몫환 [math(Z/mZ)]이 [math(m)]을 법으로 한 완전잉여계와 같다. 동치류들의 모임인 [math(Z/mZ)]의 동치류에서 대표원을 하나씩 선택하여 구성한 것이 완전잉여계라는 것을 쉽게 알 수 있다.5. 관련 문서
[1] 대우를 취하자면 [math(a_i\equiv a_j \left(\text{mod}\,m\right))]이면 [math(i=j)]라는 것과도 동치이다.