Congruence

자연수 세계 - 서론과 이야기거리 로 돌아가기

합동성(Congruence)

새로운 '논리적 관계'인 모듈 합동(congruence)에 대하여 살펴본다. 가우스가 도입한 후 '합동성(congruence)'의 개념은 나뉨 관계의 성질을 보는 데 있어 많은 도움을 준다는 것을 알게 될 것이다.

합동성의 정의

자연수의 분류에서 보았듯이 우리는 자연수 집합을 여러 방식으로 쪼개 볼 수 있게 되었다. 그 중, 예를들어, 3으로 나누어 나머지에 따라 나누어 보면

$\{3,6,9,12,\cdots \}=\{x\ |\ x:=3\cdot m,\ m\in \mathbb {N} \}$

$\{1,4,7,10,\cdots \}=\{x\ |\ x:=3\cdot m+1,\ m\in \mathbb {N} \}$

$\{2,5,8,11,\cdots \}=\{x\ |\ x:=3\cdot m+2,\ m\in \mathbb {N} \}$

으로 쪼개 볼 수 있다. 마찬가지로 5로 나눈 나머지든 7로 나눈 나머지든 자연수 집합을 쪼개 볼 수 있다.

• 3으로 나누었을 때 ( $\mathbb {N} _{0}$에서)
  • 나머지가 0인 자연수들 : $0,\ 3,\ 6,\ 9,\ \cdots$
  • 나머지가 1인 자연수들 : $1,\ 4,\ 7,\ 10,\ \cdots$
  • 나머지가 2인 자연수들 : $2,\ 5,\ 8,\ 11,\ \cdots$
• 5로 나누었을 때
  • 나머지가 0인 자연수들 : $0,\ 5,\ 10,\ 15,\ \cdots$
  • 나머지가 1인 자연수들 : $1,\ 6,\ 11,\ 16,\ \cdots$
  • 나머지가 2인 자연수들 : $2,\ 7,\ 12,\ 17,\ \cdots$
  • 나머지가 3인 자연수들 : $3,\ 8,\ 13,\ 18,\ \cdots$
  • 나머지가 4인 자연수들 : $4,\ 9,\ 14,\ 19,\ \cdots$

이런 식으로 어떤 자연수 m에 대해서도 $0,1,2,\cdots ,m-1$로 나머지가 같은 것끼리 자연수 전체를 m 조각으로 쪼개볼 수 있는 것이다. 이와 같이

정의 : 어떤 자연수 a, b, m에 대하여 a와 b가 m으로 나눈 나머지가 같다면 이를 a와 b는 모듈 m에 대하여 '합동'(또는 합동적 관계)이라고 하자.

이것을 기호로는 다음과 같이 쓰기로 한다.

$a\equiv b{\pmod {m}}$

또는

$a\equiv _{m}b$

으로 쓴다.

모듈이 3일 때, 예를 들어, 4와 5처럼, 합동적이지 않을 경우 그런 두 수 a와 b는

$a\not \equiv b{\pmod {m}}$

라고 쓰기로 하자. 그리고 m으로 나눈 나머지들은 $0,1,2,\cdots ,m-1$인 것은 명확하다. 이 수들을 '나머지'(residue)들이라고 부르자.

이제 '나뉨 관계'를 포괄하는 새로운 비교 관계가 등장한 것이다. 이것의 기초 성질을 보면 모듈합동($\equiv _{m}$ 이나 ${\pmod {m}}$ )의 기호를 '같음' 관계( = )와 비슷하게 하는 것이 우연이 아니라는 것을 알게 된다.

성질

우리는 그동안 '같다'와 '보다 크다' 관계, 더 나아가 나뉜다와 같이 두 자연수를 비교하는 관계들를 보았다. 여기서 우리는 새로운 비교 가 등장하였다. 이 관계는 자연수에서 '같음'과 마찬가지로 매우 '안정적인' 성질을 가지고 있다. 덕분에 앞으로 이 관계를 쓸 때 기초적인 연산에 대해서는 마음 편하게 쓸 수 있다. 자연수들을 그 묶음 단위로 탐구하면서 계산 복잡한 연산인 나눗셈과 연관된 성질을 깊이 알아보기 위한 강력한 수단을 가지게 된 셈이다.

'모듈 m 에 대한 합동성'은 다음의 성질을 가지고 있다. : 어떤 m 에 대하여서도 다음의 문장들은 모두 참이다. 아래에서 m은 자연수 중 아무것이나 가능하고 p는 소수만을 나타낸다고 하자.

1. $a\equiv _{m}a$
2. $(a\equiv _{m}b)\ \Rightarrow \ b\equiv _{m}a$
3. $(a\equiv _{m}b\And b\equiv _{m}c)\ \Rightarrow a\equiv _{m}c$
4. $(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a+b\equiv _{m}a'+b'$
5. $(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a-b\equiv _{m}a'-b'$
6. $(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a\cdot b\equiv _{m}a'\cdot b'$
7. $(a\cdot b\equiv _{p}0)\Leftrightarrow (a\equiv _{p}0\ \vee \ b\equiv _{p}0)$
8. $(a\cdot b\equiv _{p}a\cdot c\And a\not \equiv _{p}0)\Rightarrow b\equiv _{p}c$

기본 성질 7)과 8)은 모듈이 소수일때만 가능하다. (왜 그런가?)

처음 세 성질은 보통의 같음 관계와 마찬가지로 reflexive, symmetry, transitive 성질을 모두 만족한다는 것을 말해주고 있다.

위의 기본 성질을 나타내는 문장들이 참인지 거짓인지 증명하기 위해서는 '모듈 m 에 대한 합동'의 정의로 돌아가면 된다. 다시말해

$a\equiv _{m}b$ 은 $a=b+q\cdot m$ 인 자연수 q가 있다는 것을 뜻한다.

따라서, 예를들어 6)의 경우,

$a\equiv _{m}a'$ 이므로, 정의에 따라 $a=a'+s\cdot m$ 이고

$b\equiv _{m}b'$ 이므로, 정의에 따라 $b=b'+t\cdot m$ 이다.

따라서

$a\cdot b=a'\cdot b'+(a'\cdot t+b'\cdot s+t\cdot s)\cdot m$

이고 자연수들은 곱셈과 덧셈 연산을 해도 자연수만 나오므로, 자연수 $a\cdot b=a'\cdot b'+q\cdot m$인 자연수 q가 있다. 따라서 6)은 참이다. 나머지 위의 문장들을 모두 검토해보라.

(모듈 합동관계를 쓰는 예)

345 라는 수가 있다고 하자. 그렇다면

$345=3\cdot 10^{2}+4\cdot 10^{1}+5$

이므로 11 모듈로 하면 $10\equiv _{11}-1$이므로, 성질 6)에 따라

$10\cdot 10\equiv _{11}(-1)\cdot (-1)$

이고 따라서 다시 성질 6)에 따라

$3\cdot 100\equiv _{11}3\cdot 1$

이다. 마찬가지로 다른 항에 대해서도 적용하고, 이어서 기본 성질 4)에 따라 다음과 같이 11 모듈 합동이다.

$345=3\cdot 10^{2}+4\cdot 10^{1}+5\ \equiv _{11}\ 3\cdot 1+(-1)\cdot 4+5\ \equiv _{11}4$

실제로 345 = 31 * 11 + 4 다.

모듈 m에 대한 합동성을 이해하기 위한 모델

'시간'이 직선형으로 흐른다고 상상해 볼 수 있다. 그런 세계관을 바탕으로 하면 우리는 시간의 흐름을 거대한 한 방향으로 뻗어나가는 반직선을 생각할 수 있는데 그것을 우리 사람들이 시(時)로 대응시켜 나타내는 방법이 0시, 1시, 2시, ... 와 같은 방법을 쓰곤한다. (물론 아주 오랜 옛날에는 민족마다 다른 풍습을 지녔다.) 그리고 이 시간은 24시간을 돌고 나면 다시 0시부터 시작하게 된다. 원형으로 돌고 돈다. 이 글 이 지점을 읽는 시점은 어제의 지금 이 시간과 분명 다른 시간이지만, 우리는 그것을 같은 시-분-초로 나타낸다. (물론 '날짜'라는 개념을 도입하여 혼돈을 막는다. '날짜'는 다시 '달'에 의해, '달'은 '년'에 의해 혼돈을 막는다.) 이는 어제 그 때와 오늘 이 때가 비슷한 성질을 가졌기 때문이다.

합동성도 마찬가지다. 수를 직선으로 표시하면 모든 정수들은 '같음'의 관계를 기준으로 해서 직선상에 표현할 수 있겠지만, '나눗셈'과 '나머지들'의 개념을 도입하여 비슷한 성질들로 쪼개어 묶음 단위로 생각하면서 '같음'의 관계 대신 '모듈 m에 대한 합동'관계로 보면 원형이 된다. 이 때 원에 찍히는 점의 개수는 m개 일 것이다.

따라서 모듈 3에 대하여 2나 5나 8은 원형의 모두 같은 점에 찍히고, 모듈 7에 대하여 2나 9나 11일도 모두 같은 점에 찍혀 있다. (같은 달에 있는 그 날짜들은 같은 요일이다.) 우리가 정수까지 확장해보면, 모듈 11에 대하여 10은 -1과 합동 관계다. 다시 말해 원형에 같은 점에 찍힌다.

기본 성질의 응용

어떤 정수가 주어지고 그 수가 어떤 수로 나누어지는지 알아내는 것은 아주 계산이 복잡한 과정이다. (10진법으로 아주 길고 복잡한 숫자를 여러 개 생각한 다음 그 숫자가 어떤 수로 나뉘는지 알아내는 '법칙'을 만들어낸다고 생각해보라. 사실 나눗셈이 복잡한 것은10진법 시스템이기 때문이기도 하다. 2진법은 차원이 다르다.자연수 나타내기: q-진법을 참고하라.) 그런데 합동관계의 성질을 적용하면 주어진 어떤 수가 다른 수로 나뉘는가 하는 새로운 어떤 '기준'들을 찾아낼 수 있다. 그 예를 몇가지 들어보기로 한다. 십진법에서 어떤 정수 z가 $a_{n}a_{n-1}a_{n-2}\cdots a_{0}$ 으로 표현되어 있다고 하자. 자연수를 나타내는 껍질인 '기호'만으로 자연수 속의 성질을 알 수 있다.

• 어떤 정수 z가 11로 나뉜다 $\Leftrightarrow \ a_{0}-a_{1}+a_{2}-\cdots +(-1)^{n}a_{n}$이 11로 나뉜다.

왜 그런가? 앞에서 말했듯이 모듈 11에 대하여 10은 -1과 합동 관계다. 다시 말해

$10\equiv _{11}-1$

기본 성질 6)을 이용하면

$10\cdot 10\equiv _{11}(-1)\cdot (-1)$ 이고

$10^{3}\equiv _{11}(-1)^{3}$ 이고

$10^{4}\equiv _{11}(-1)^{4}$ 이고

$\ldots$

$10^{10}\equiv _{11}(-1)^{10}$ 이고

$\ldots$

어떤 z은 10진법으로

$z=a_{0}+a_{1}\cdot 10+a_{2}\cdots 10^{2}+\cdot +a_{n}\cdot 10^{n}$

으로 풀어 쓸 수 있다. 기본 성질 4), 6)에 따라, z의 나머지가 얼마인가만 관심을 갖는다면, $10^{i}$ (여기서 i는 1부터 n까지의 자연수)대신 그것과 모듈 11에 대해 합동관계인 수들로 바꿔 써도 된다. 따라서 11로 나누었을 때 z의 나머지는 $a_{0}-a_{1}+a_{2}-\cdots +(-1)^{n}a_{n}$ 의 나머지와 같다. 같은 방법으로 다음을 알 수 있다. 직접 검토해보라.

• 어떤 정수 z가 3으로 나뉜다 $\Leftrightarrow \ a_{0}+a_{1}+a_{2}+\cdots +a_{n}$이 3로 나뉜다.
• 어떤 정수 z가 7로 나뉜다 $\Leftrightarrow \ a_{0}+3a_{1}+2a_{2}-a_{3}-3a_{4}-2a_{5}+a_{6}+3a_{7}\cdots$이 7로 나뉜다.

위의 내용을 보일 때, 다음 설명을 위해 이것은 꼭 확인하자.

$10^{2}\equiv _{3}1$

$10^{6}\equiv _{7}1$

자연수 세계 - 서론과 이야기거리 로 돌아가기

Note

Math : Math글쓰기 | Math번역 | MathBoard | Math&Culture | MathMoim
OnLineMathCenter | MathCamp | SoftMathJournal | MathBook | CyberAcademia | Academia