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}$ $\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 조각으로 쪼개볼 수 있는 것이다.^[1] 이와 같이

정의 : 어떤 자연수 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}}$ )의 기호를 '같음' 관계( = )와 비슷하게 하는 것이 우연이 아니라는 것을 알게 된다.

성질

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

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

$a\equiv _{m}a$
$(a\equiv _{m}b)\ \Rightarrow \ b\equiv _{m}a$
$(a\equiv _{m}b\And b\equiv _{m}c)\ \Rightarrow a\equiv _{m}c$
$(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a+b\equiv _{m}a'+b'$
$(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a-b\equiv _{m}a'-b'$
$(a\equiv _{m}a'\And b\equiv _{m}b')\ \Rightarrow a\cdot b\equiv _{m}a'\cdot b'$
$(a\cdot b\equiv _{p}0)\Leftrightarrow (a\equiv _{p}0\ \vee \ b\equiv _{p}0)$
$(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개 일 것이다.^[4]

따라서 모듈 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

^[5]

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

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

Note

↑ 어떤 자연수 a,b 에 대해서도, a가 b보다 크다고 했을 때 $a=q\cdot b+r$ 인 정수 q와 0보다 크거나 같고 q보다 작은 r이 있기 때문이다. 이때 r 을 나머지라 부르고, q를 '나누는 수'라고 부르기로 하자. 이에 대하여 최대공약수 참고.
↑ 어떤 나라에서는 m에 대한 합동성을 '합동' 개념으로 하지 않고 더 분명하게 '모듈별 비교' 라고 부르기도 한다.
↑
여기서 기호
- $A\ \And B$ 는 'A 문장이 참 이고 B 문장도 참'을 뜻하는 문장이고,
- $A\ \vee B$ 는 'A 문장이 참 이거나 B 문장도 참'을 뜻하는 문장이고
- $A\ \Rightarrow B$ 는 'A 문장이 참 이면 B 문장도 참'을 뜻하는 문장이고
- $A\ \Leftrightarrow B$ 는 'A 문장이 참이면 B 문장도 참'이고, 동시에 B 문장이 참이면 A 문장도 참이다'라는 문장이라고 이해하자. 이는 문장 A와 문장 B가 논리적으로 동치라는 것을 말하다.
↑ 이런 산술 체계를 일반적인 산술체계인
$<\mathbb {N} \ ,=,\circ >$
에 빗대어 모듈 산술 이라고 하고
$<\mathbb {N} \ ,\equiv _{m},\circ >$
기도 한다. 여기서 $\circ$ 는 기본 연산들을 나타낸다.
↑ 물론 이는 모듈 합동 관계의 언어로 말하지 않고 일반적인 산술언어로도 충분히 설명할 수 있다. 예들들어 3594 의 경우 $3592=3\cdot 10^{3}+5\cdot 10^{2}+9\cdot 10+2=3\cdot (999+1)+5\cdot (99+1)+9(9+1)+2=3\cdot (...)+3+5+9+2$ 다. 하지만 이는 그 결과를 알고 그것을 보이는 것이고, 11이나 아래의 7과 같이 다른 수들에 대해서도 폭넓게 보기에는 오히려 불편하다. 그에 비해 모듈 산술의 언어를 쓰면 그런 일반법칙을 유추하는데 편리하다.

[1] 어떤 자연수 a,b 에 대해서도, a가 b보다 크다고 했을 때 $a=q\cdot b+r$ 인 정수 q와 0보다 크거나 같고 q보다 작은 r이 있기 때문이다. 이때 r 을 나머지라 부르고, q를 '나누는 수'라고 부르기로 하자. 이에 대하여 최대공약수 참고.

[2] 어떤 나라에서는 m에 대한 합동성을 '합동' 개념으로 하지 않고 더 분명하게 '모듈별 비교' 라고 부르기도 한다.

[3] 여기서 기호
$A\ \And B$ 는 'A 문장이 참 이고 B 문장도 참'을 뜻하는 문장이고,

$A\ \vee B$ 는 'A 문장이 참 이거나 B 문장도 참'을 뜻하는 문장이고

$A\ \Rightarrow B$ 는 'A 문장이 참 이면 B 문장도 참'을 뜻하는 문장이고

$A\ \Leftrightarrow B$ 는 'A 문장이 참이면 B 문장도 참'이고, 동시에 B 문장이 참이면 A 문장도 참이다'라는 문장이라고 이해하자. 이는 문장 A와 문장 B가 논리적으로 동치라는 것을 말하다.

[4] $A\ \And B$ 는 'A 문장이 참 이고 B 문장도 참'을 뜻하는 문장이고,

[5] $A\ \vee B$ 는 'A 문장이 참 이거나 B 문장도 참'을 뜻하는 문장이고

[6] $A\ \Rightarrow B$ 는 'A 문장이 참 이면 B 문장도 참'을 뜻하는 문장이고

[7] $A\ \Leftrightarrow B$ 는 'A 문장이 참이면 B 문장도 참'이고, 동시에 B 문장이 참이면 A 문장도 참이다'라는 문장이라고 이해하자. 이는 문장 A와 문장 B가 논리적으로 동치라는 것을 말하다.

[4] 이런 산술 체계를 일반적인 산술체계인
$<\mathbb {N} \ ,=,\circ >$
에 빗대어 모듈 산술 이라고 하고
$<\mathbb {N} \ ,\equiv _{m},\circ >$
기도 한다. 여기서 $\circ$ 는 기본 연산들을 나타낸다.

[5] 물론 이는 모듈 합동 관계의 언어로 말하지 않고 일반적인 산술언어로도 충분히 설명할 수 있다. 예들들어 3594 의 경우 $3592=3\cdot 10^{3}+5\cdot 10^{2}+9\cdot 10+2=3\cdot (999+1)+5\cdot (99+1)+9(9+1)+2=3\cdot (...)+3+5+9+2$ 다. 하지만 이는 그 결과를 알고 그것을 보이는 것이고, 11이나 아래의 7과 같이 다른 수들에 대해서도 폭넓게 보기에는 오히려 불편하다. 그에 비해 모듈 산술의 언어를 쓰면 그런 일반법칙을 유추하는데 편리하다.

[1]

[2]

[3]

[4]

[5]