완전잉여계

완전 잉여계에서 넘어옴

역사 raw
대문 랜덤 문서 최근 토론
분류
1. 개요2. 완전잉여계가 되는 경우3. 완전잉여계와 기약잉여계의 관계4. 추상적인 버전5. 관련 문서


完全剩餘界 / Complete Residue System

1. 개요[편집]

1보다 큰 자연수 mm에 대하여, 집합 {a1,a2,⋯ ,am}\left\{a_1,a_2,\cdots,a_m\right\}이 임의의 정수 aa에 대하여 a≡ai(mod m)a\equiv a_i\left(\text{mod}\,m\right)인 aia_i가 유일하게 존재할 때, 위 집합을 법 m에 대한 완전잉여계라 한다. 이것은 mm개의 정수 a1,a2,⋯ ,ama_1,a_2,\cdots,a_m이 i≠ji\neq j이면, ai≢aj(mod m)a_i \not\equiv a_j \left(\text{mod}\,m\right)[1]을 만족하는 것과 동치이다.

위의 내용을 간단히 풀어쓰자면, ''법 mm에 대한 완전잉여계"란 각 원소를 mm으로 나누었을 때 나머지들이 정확히 {0,1,2,⋯ ,m−1}\left\{0, 1, 2,\cdots,m-1\right\}이 되는 집합이다.
법 mm에 대한 대표적인 완전잉여계는 {0,1,2,⋯ ,m−1}\left\{0,1,2,\cdots,m-1\right\}이 있다. mm으로 나눈 나머지는 반드시 0,1,⋯ ,m−10, 1,\cdots, m-1밖에 없기 때문이다.

하지만 완전잉여계가 반드시 위와 같은 꼴인 것만은 아니다. 예를 들어 법 5에 대한 대표적인 완전잉여계는 A={0,1,2,3,4}A=\{0,1,2,3,4\}인데, B={0,1,3,4,7}B=\{0,1,3,4,7\}도 각 원소를 5로 나눈 나머지의 집합을 C라 하면 C={0,1,3,4,2}C=\{0,1,3,4,2\}로 원소가 중복되지 않으므로 역시 완전잉여계이다.

2. 완전잉여계가 되는 경우[편집]

집합 A가 완전잉여계가 되려면 A의 각 원소를 법 m으로 나눈 나머지의 집합을 B라 할 때, B의 원소의 범위가 m 미만의 음이 아닌 정수이고, 원소의 개수가 m과 같아야 하면서 중복되는 원소가 생기지 않아야 하므로 B={b1,b2,⋯ ,bk,⋯ ,bm}(1≤k≤m)B=\left\{b_1,b_2,\cdots,b_k,\cdots,b_m\right\}(1\leq k\leq m)라 하면 모든 k에 대하여 bkb_k가 일대일 대응되어야 한다. 이런 경우로는 다음을 들 수 있다.
  • 이때, 집합 B를 만드는 방법의 수는 m!이며, 집합 A를 만드는 방법의 수는 B의 각 원소에 mk(k는 정수)를 더하거나 빼면 되므로 무수히 많다.
  • 정수 k에 대하여 A={0,k,2k,...,(m−1)k}A=\{0, k, 2k, ..., (m-1)k\}이면서 m과 k가 서로소인 경우: 0, k, 2k, ..., (m-1)k를 m으로 나눈 나머지가 모두 서로 다르므로 완전잉여계이다. 단, 서로소가 아닌 경우는 m으로 나눈 나머지가 서로 같은 원소가 반드시 생기므로 완전잉여계가 아니다. 예를 들어 4와 10은 서로소가 아닌데, A={0,10,20,30}A=\{0, 10, 20, 30\}가 법 4에 대한 완전잉여계인지 알아보기 위해 각 원소를 4로 나눈 나머지를 집합 형태로 표현하면 B={0,2,0,2}B=\{0, 2, 0, 2\}이고, 중복되는 원소가 있으므로 완전잉여계가 아니다.
    • k가 음수일 때도 물론 성립한다.
  • m이 홀수일 때, A={−m−12,−m−32,...,−2,−1,0,1,2,...,m−32,m−12}\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라 하면 C={m+12,m+32,...,m−2,m−1,0,1,2,...,m−32,m−12}\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}\}이고, 원소를 다르게 나열하면 C={0,1,2,...,m−32,m−12,m+12,m+32,...,m−2,m−1}\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에 대한 완전잉여계 A={0,1,2,3,4,5}A=\{0, 1, 2, 3, 4, 5\}에 대하여 A의 부분집합인 법 6에 대한 기약잉여계는 B={1,5}B=\{1, 5\}이다. m이 소수일 때는 A에서 원소 0을 제외한 나머지로 이루어진 집합이 기약잉여계이다.

4. 추상적인 버전[편집]

정수환의 몫환 Z/mZZ/mZ이 mm을 법으로 한 완전잉여계와 같다. 동치류들의 모임인 Z/mZZ/mZ의 동치류에서 대표원을 하나씩 선택하여 구성한 것이 완전잉여계라는 것을 쉽게 알 수 있다.

5. 관련 문서[편집]




[1] 대우를 취하자면 ai≡aj(mod m)a_i\equiv a_j \left(\text{mod}\,m\right)이면 i=ji=j라는 것과도 동치이다.