정수론에서 합동 개념은 수학적으로 매우 중요할 뿐더러 일상 생활의 여러 문제에 대입하여 활용될 수 있습니다. 아주 큰 수의 마지막 자리수를 찾는다거나, 아주 큰 수가 적당히 작은 수로 나누어 떨어지는지 등의 문제, 또는 과거 몇 년 몇 월 며칠이 어떤 요일이었는지를 알아내는데도 사용될 수 있습니다. 이는, 결국 숫자의 비슷한 구조가 계속 '반복'된다는 점을 합동 개념을 통해 하나로 묶어 생각하는 것이기 때문입니다.
합동관계는 동치관계의 한 예시로 집합론에서 등장했던 적이 있고, 이후 추상대수학을 공부할 때 매우 매우 많이 등장합니다. 부득이하게 정수론을 제대로 학습하지 못했다고 하더라도, 대수학을 공부하기 위해서 정수론의 합동 개념은 반드시 필요한 도구입니다.
숫자가 가진 어떠한 성질이 계속 반복된다는 특징을 배운다는 생각을 하면서 아래 개념을 살펴봅시다.
1. 합동의 정의(Congruence)
정의($N.T$) 3-1) 정수론에서 합동(Congruence)
어떤 자연수 $n$이 주어졌을 때, 정수 $a,b$ 가 다음을 만족할 때 $a$ 와 $b$는 법(modulo)1 $n$에 대해 합동이다'라고 말한다.
$$a\equiv b\mod n \;\;\Longleftrightarrow \;\;n\mid (a-b)$$
정의($N.T$) 3-2)
어떤 자연수 $n$이 주어졌을 때, 정수 $a,b$ 가 $a\not\equiv b\mod n$ 이면 $a$ 와 $b$는 '법(modulo) $n$에 대해 합동이 아니다'라고 한다.
표기상의 주의할 점이라면 $a\equiv b\mod n$ 라고 적을 때, $a,b$ 의 순서를 생각해야 합니다. 즉 이 경우 $n\mid (a-b)$ 이므로 어떤 $k\in\mathbb{Z}$ 에 대하여 $kn=a-b$ 가 성립하는 것인데, 부호를 착각해서 $kn=b-a$ 가 되지 않도록 해야겠지요.2 또한 $\mod n$ 에 해당하는 부분을 적을 때는 보통 괄호 안에 넣어서 $a\equiv b\;( \text{mod} \;\;n) $ 라 적기도 합니다.
참고로 이 합동의 modulo 개념은 천재 수학자 Gauss 가 처음 사용한 것이고, 'modulo' 의 어원은 라틴어 'modulus', 'modus' 에서 유래하였습니다. 이는 무언 가를 잰다는 '측정(measure)'의 뜻을 가지고 있습니다.3
▶ 덧붙이자면 별개의 내용이지만, 컴퓨터 언어인 파이썬(python)에서 '$\% \;n\; ==\; 0$' 이라는 문법이 바로 이 합동 개념입니다. 파이썬에서는
와 같은 코드를 입력하면, 이것의 의미는 $2$ 로 나눈 나머지가 $1$ 일 때 (내가 제시한 숫자에 대하여) 이를 홀수(위의 코드에서는 'oddfunction'이라는 글자를 출력하도록 명령하였음)라고 판정할 수 있게 됩니다. 즉 위에서처럼 만일 제가 $3$ 이라는 숫자를 입력한 뒤, 'if~else~' 부분에 의하여 $2$ 로 나눈 나머지가 $0$ 이 되면 짝수로 판별하고, 그렇지 않으면(= $2$ 로 나눈 나머지가 $1$ 이면) 홀수라고 출력할 수 있게 만든 코드라는 뜻입니다.
정리($N.T$) 3.1)
합동은 동치관계이다. 즉 $\equiv$ 는 반사율, 대칭율, 추이율을 만족한다.
증명) 집합론에서 동치류를 다룰 때 증명했었다. 동치관계와 동치류 글에서 예제 3)을 참고하라. $_\blacksquare$
정리($N.T$) 3.2)
TFAE : 다음은 전부 서로 동치이다
① $a\equiv b\;( \text{mod} \;\;n)$
② $a-b$ 는 $n$의 배수이다
③ $a-b=kn$ 을 만족하는 $k\in\mathbb{Z}$ 가 존재한다
④ $a$ 와 $b$ 는 $n$ 으로 나눴을 때 나머지가 동일하다.
⑤ $0\leq b < n$ 일 때는, $a$ 를 $n$ 으로 나눈 나머지가 $b$ 이다.
이 정리는 따로 증명을 하지 않겠습니다. 사실상 $n\mid (a-b)$ 라는 기호와 합동의 정의만 제대로 알면 거의 동어 반복 수준이기 때문입니다. 그러나 제가 아주 자세하게 지금부터 설명할 것입니다. 끝까지 모두 읽고 예제 두 개까지 확인해 보셔야 합니다.
우선 합동 개념을 처음 배울 때는 표기법이나 개념이 익숙치 않을 수 있으므로 다 같이 5가지를 한 번에 떠올리는 연습을 하면서 익숙해질 필요가 있습니다. 표기상의 주의할 점이라면 $a\equiv b\mod n$ 라고 적을 때, $a,b$ 의 순서를 생각해야 합니다. 즉 이 경우 $n\mid (a-b)$ 이므로 어떤 $k\in\mathbb{Z}$ 에 대하여 $kn=a-b$ 가 성립하는 것인데, 부호를 착각해서 $kn=b-a$ 가 되지 않도록 해야겠지요.4 또한 $\mod n$ 에 해당하는 부분을 적을 때는 보통 괄호 안에 넣어서 $a\equiv b\;( \text{mod} \;\;n) $ 라 적기도 합니다.
합동의 정의를 살펴보면, 결국 두 수의 차이가 $n$ 의 배수가 된다는 것을 뜻합니다. 그렇다면 $a\equiv b\;( \text{mod} \;\;n) $ 가 의미하는 바는
$$\begin{align*}
a\equiv b\;( \text{mod} \;\;n) \;\; &\Leftrightarrow \;\; n\mid (a-b)
\\\\&\Leftrightarrow \;\; a-b=kn\;(k\in\mathbb{Z})
\\\\&\Leftrightarrow \;\; a=kn+b
\end{align*}$$
가 되는 것입니다. 이 정리의 다섯 가지 조건을 살펴보면 핵심은 다음과 같습니다.
②,③ 의 내용은 합동인 두 수는 먼저 그 차이가 $n$의 배수가 된다는 것이고, ④ 의 내용은 두 수는 $n$ 으로 나누었을 때 나머지가 동일하다는 것입니다. $n$으로 나누었을 때 나머지가 동일하면, 두 수를 빼면 나머지끼리 빼지니 $n$ 의 배수 형태만 남게 되지요.
그런데 왜 이런 관계에 대해 합동이라는 고급적인 이름을 붙여주고, 정의하게 되는 것일까요? 일상생활에서 시계를 생각해 봅시다. 밖을 볼 수 없는 밀실에 같혀 있는 채 아날로그 시계만을 볼 수 있다고 가정하겠습니다. 작은 바늘이 $3$에 있고, 큰 바늘이 $12$에 있으면 우리는 시계를 보고 현재 시각이 '세 시'라고 읽을 것임을 알 수 있습니다. 하지만, 정확히 오전 $3$시인지 오후 $3$시, 곧 $15$시인지는 알 수 없습니다. 그런데 아날로그 시계에서는 주기가 $12$시 체제이므로, 실제 현실에서 '(오전)$3$시'와 '$15$시'를 바늘만으로는 구분할 수 없습니다. 즉 실제 시각의 $3$시와 $15$시가 정의역의 두 원소라면, 이 두 원소가 모두 시계 위에서 바늘의 모든 위치라는 공역으로 넘어갈 때 공역의 $3$시라는 하나의 원소로 대응됩니다.5 하지만 $3$시와 $15$시는 분명 연관성이 있습니다. 바로 '$12$'만큼 차이나기 때문이죠! 왜냐하면 우리의 시각 체계는 $12$시간이 반복되면 시계에서 똑같은 위치로 바늘이 돌아온다는 개념을 토대로 세워져 있기 때문입니다. 따라서, 시계에서 $3$시와 $15$시가 가지는 공통적 개념은 합동의 개념으로 보았을 때 $12$로 나눈 나머지가 동일하다는 것이며, 다시 말해 $15-3$ 이 $12$의 배수라는 것입니다. 여기서 $3$과 $15$는 숫자적으로 $3=15$ 인 것은 아니지만, $12$로 나눈 나머지가 같기 때문에 큰 연관성이 있다는 점에서 합동이라는 고급스러운 이름을 붙여준 것이며, 이것이 $3\equiv 15\mod 12$ 의 의미입니다. 게다가 합동을 이런 방식으로 정의하게 되면 이후에 다룰 몇가지 산술적인 연산들과 호환성을 가집니다. 나아가, 대수학에서 지겹게 등장할 $\mathbb{Z}_n$를 구성하는 모든 원소들을 이 합동의 개념을 통해 동치류들의 집합이라고 생각하게 된다면 많은 숫자들을 압축적으로 하나의 원소로 표현하는 것이 가능해집니다.
예제 1) $10\equiv 7\;( \text{mod} \;\;3)$ 이다. 그 까닭은 $10-7$ 은 $3$ 의 배수이고, $10$ 이나 $7$ 모두 $3$ 으로 나눈 나머지가 $1$ 로 동일하기 때문이다. 반면 ⑤ 를 적용해보자. $10$ 을 $3$ 으로 나눈 나머지는 $1$ 이기 때문에 $7$ 이 아니다.
예제 2) $10\equiv 3\;( \text{mod} \;\;7)$ 이다. $10-3$ 은 $7$ 의 배수이고, $10$과 $3$ 모두 $7$ 로 나누었을 때 나머지가 $3$ 으로 동일하다. 또한 이때는 $0\leq 3 < 7$ 이므로 ⑤ 를 적용할 수 있다. 즉 $a=10$ 을 $b=7$ 로 나눈 나머지가 정확히 $n=3$ 에 해당한다.
정리($N.T$) 3.3)
정해진 $n$ 에 대해 정수 $a$ 가 주어졌다고 하자. $a\equiv 0\;( \text{mod} \;\;n)$ 일 필요충분조건은 $n\mid a$ 인 것이다.
따름정리($N.T$) 3.3.1)
임의의 $a\in\mathbb{Z}$ 에 대하여, $a\equiv 0\;( \text{mod} \;\;1)$ 이 성립한다.
증명) 합동의 정의로부터 자연수럽게 도출된다.
$$\begin{align*}
a\equiv 0\;( \text{mod} \;\;n) \;&\Leftrightarrow \;a-0=a=nk\;(k\in\mathbb{Z})
\\\\& \Leftrightarrow n\mid a
\end{align*}$$
즉 $a$ 는 $n$ 의 배수이고, $n$ 은 $a$ 의 약수이다. $_\blacksquare$
따름정리의 증명) 임의의 어떤 정수도 1로 나누면 그냥 자기 자신이다. 그러면 나머지는 항상 영이 된다. 위의 정리($N.T$) 3.2)의 ⑤ 를 생각해보면 된다. $_\blacksquare$
2. 완전잉여계(Complete residue system)
합동(모듈러)을 정의하게 되면 원소의 개수가 아주 많은 집합을 아주 간단히 동치류의 개념으로 표현할 수가 있게 됩니다. 그 방법을 활용하기 위해 완전잉여계에 대해 알아보겠습니다.
그리고 주의할 것이 있습니다. 완전잉여계는 앞서 말했듯이 합동에 관한 동치류 개념입니다. 이것의 정확한 정의는 바로 다음 글에서 다룹니다. 그런데 다음 글에서 말하는 동치류는 조금 더 일반적인 정의이고 여기서의 완전잉여계는 그러한 동치류 중에서 깔끔한 것들로 집합을 만드는, 조금 더 특수한 방법에 관한 개념입니다. 따라서 이 순서로 학습해도 무관하고, 오히려 제가 여기서 구체적으로 설명을 한 뒤 더 일반적인 표현을 바로 다음 글에서 소개하는 것이라고 생각해 주시면 됩니다.
정의($N.T$) 3-3) 완전잉여계
임의의 정수 $a$ 가 집합 $A=\{r_1,r_2,\cdots , r_{n-1},r_n \}$ 의 단 하나의 원소 $r_k\;(1\leq k \leq n\,,\,k\in\mathbb{N})$ 에 대해 $a\equiv r_k\;( \text{mod} \;\;n)$ 이면, 이 집합을 '법(modulo) $n$ 에 대한 완전잉여계(Complete residue system)'이라 정의한다.
집합 $A$ 가 완전잉여계이면, $r_1,r_2,\cdots, r_{n-1}, r_n \in A$ 에 대하여 $i\neq j\;(1\leq i,j\leq n\,,\, i,j\in\mathbb{N})$ 이면 $r_i \not\equiv r_j\;( \text{mod} \;\;n)$ 가 성립한다.
일반적으로 주어진 법 $n$ 에 대해, 완전잉여계 집합의 종류는 무수히 많고, 보통 음이 아닌 최소의 잉여(least non-negative residues)로 구성된 완전잉여계를 사용하는 편이다.
동치관계는 본질이고, 동치류는 대표원소라는 저의 철학을 이해하셨다면 이 개념도 쉽게 받아들일 수 있습니다. 예를 들어 정수 집합의 모든 원소를 원소나열법으로 적으면 $\mathbb{Z}=\left\{ \cdots, -1,0,1,2,\cdots \right\}$ 이라 표현할 수 있습니다. 그런데 이 원소들을 $8$ 에 대한 합동 관계가 주어졌을 때 새로 표현하는 방법을 찾고자 합니다.
합동의 정의를 다시 살펴보면
$$a\equiv b\;( \text{mod} \;\;n)
\;\;\Longleftrightarrow \;\;a=nq+r\;(0\leq r < n )$$
의 관계가 성립합니다. 즉, 합동식은 나눗셈 정리 식의 꼴로 표현할 수 있지요. 그러면, 여기서 $r$ 의 값은 $0\leq r < n$ 을 만족하는 정수가 되므로 결국 $r$ 은 $0,1,2,\cdots , n-1$ 중 하나의 값을 가지게 됩니다. 따라서 $n$ 이 주어졌을 때, 임의의 정수 $a$ 는 $0,1,2,\cdots , n-1$ 중 하나와 반드시 법 $n$ 에 대한 합동이어야 합니다.
이때 위 [그림 1]의 9시 방향을 보면 $\cdots , -8,0,8,16, \cdots$ 을 제가 하나의 묶음으로 처리했는데, 이들은 모두 $n=8$ 이라 주어졌을 때 $n=8$ 로 나눈 나머지가 $0$인 것들의 묶음입니다. 반시계 방향으로 한 칸 건너가면, $\cdots, -7,1,9,17,\cdots $ 이 또 하나로 묶여 있고 이들은 $8$ 로 나눈 나머지가 $1$ 인 것들의 묶음이지요? 또 한 칸 반시계로 건너가면 $8$ 로 나눈 나머지가 $2$인 것들의 묶음, 이 짓을 반복해서 11시 방향에 도착하면 나머지가 $7$ 인 것들의 묶음으로 분류가 됩니다.
따라서 임의의 정수 $a$ 는 반드시 제가 그린 팔각형의 8가지 집합 중 하나에 속해 있을 수 밖에 없게 됩니다. 이것이, 임의의 정수 $a$ 가 $0,1,2,\cdots , n-1=7$ 과 반드시 법 $n=8$ 에 대해 합동이어야 함을 의미하는 것입니다. 그러면 이때 집합 $\left\{ 0,1,2,\cdots ,7\right\}$ 는 법 $8$ 에 대한 완전잉여계라고 할 수 있습니다.
그런데 이 $\left\{ 0,1,2,\cdots ,7\right\}$ 은 법 $8$ 에 대한 완전잉여계 중 하나입니다. 왜냐하면, 사실 $\left\{ 0,1,2,\cdots ,7\right\}$ 집합 대신 $\left\{ 8,9,10,\cdots ,15\right\}$ 를 고려해 보아도, 임의의 정수 $a$ 는 반드시 $\left\{ 8,9,10,\cdots ,15\right\}$ 의 어느 한 원소와 법 $8$ 에 대해 합동인 것이기 때문입니다. 따라서, 완전잉여계는 일반적으로 무한히 많으며 단 하나로 유일하게 결정되지 않습니다. 하지만, 보통은 예컨대 모듈 $8$ 에 대한 완전잉여계는 $\left\{ 0,1,2,\cdots ,7\right\}$ 를 선택하는 것이 편리하겠지요. 그래서 일반적으로 '완전잉여계'라 함은 그 원소들이 '음이 아닌 최소의 잉여(Least non-negative residue)'로 이루어져 있음을 전제하는 편입니다.
예제 3) $x$ 가 법 $n$ 에 대한 음이 아닌 최소잉여(least non-negative residue)라 하자. 주어진 $n$ 들의 값에 따른 $a=34$, $b=100$, $c=-27$ 에 대하여 $x$ 의 값을 찾아라.
1) $34\equiv x\;( \text{mod} \;\;10) $
2) $100\equiv x\;( \text{mod} \;\;9) $
3) $-27\equiv x\;( \text{mod} \;\;7) $
제가 이 문제를 풀 때 1)에서는 직관적인 개념 위주로, 2)에서는 나눗셈 알고리즘을 통해 보다 정석적인 방법을 통해 풀 것이니 비교해 보시기 바랍니다. 그리고 3)에서는 정공법을 고수하되 음수가 등장했을 때 처리에 있어 주의해야 할 점에 주목하면 됩니다.
sol) 1) $10\mid (34-x)$ 이므로 $34-x=10k$ 를 만족하는 $k\in\mathbb{Z}$ 가 무수히 많이 존재한다. 그런데 $x$가 (음이 아니라는 조건 말고) 최소잉여라는 조건만을 일단 따지면, $x$ 의 절댓값을 최대한 작게 만든다는 뜻, 정확히는 $10$ 보다 절댓값이 작게 택해야 하기 때문에 $34-x=30$ 또는 $34-x=40$ 가 성립하면 된다. 각각 $x=4\,,\,-6$ 을 얻는데 $x$ 는 음이 아닌 최소잉여이기 때문에 $x=-6$ 을 버리고 $x=4$ 를 택한다.
2) $9\mid (100-x)$ 이므로 $100-x=9k$ 인 $k\in\mathbb{Z}$ 가 무수히 많이 존재한다. 이제 한방에 음이 아닌 최소잉여를 찾아보자. $100-x=99$ 에서 $x=1$ 을 얻는다.
하지만 이러한 암산을 자신이 잘 못한다고 생각하고 정공법을 생각해보자. $9\mid (100-x)$ 에서 $x$ 가 음이 아닌 최소잉여이면, $x$ 는 나눗셈 알고리즘을 만족해야 한다. 다시 말해 정리($N.T$) 3.2) 에서 ⑤를 생각해보자. 그러면
$$100=9q+x$$
이고 여기서 $0\leq x < 9$ 가 되어야 한다는 것을 의미한다. 그러면 $100$ 을 $9$ 로 나눈 나머지이기 때문에 $x=1$ 을 바로 찾을 수 있다.
3) $7\mid (-27-x)$ 이므로 $-27-x=7k$ 인 $k\in\mathbb{Z}$ 가 무수히 많이 존재하는 상황이다. 2)에서와 같이 나눗셈 알고리즘을 생각해보자. 그러면
$$-27=7q+x$$
인 상황이고 당연히 $0\leq x < 7$ 이어야 한다. 그런데 좌변이 음수이고 $x\geq 0$ 이려면 당연히 $q<0$ 여야 한다. $q=-3,-4,-5$ 를 모두 고려해보자
i) $q=-3$ 이면 $x=6$ 이므로 $0\leq x < 7$ 를 만족한다.
ii) $q=-4$ 이면 $x=1$ 이므로 $0\leq x < 7$ 를 만족한다.
iii) $q=-5$ 이면 $x=8$ 이므로 $0\leq x < 7$ 를 만족하지 않는다.
따라서 iii) 은 탈락이고, i),ii) 중에서는 최소 잉여를 택하는 것이기 때문에 ii), 곧 $x=1$ 이 정답이다. $_\blacksquare$
이렇게 3)의 경우 음수를 조사할 때는 약간 번거롭더라도 $q$ 의 값을 몇 개 찾아봐야 할 수도 있습니다.
정리($N.T$) 3.4)
주어진 정수 $n$ 에 대하여 임의의 두 정수 $a,b$ 가 $a\equiv b\;\;(\text{mod }n)$ 인 것은 $a,b$ 를 $n$ 으로 나누었을 때 음이 아닌 나머지가 같은 것과 필요충분조건이다.
증명) $\Rightarrow $ : $a\equiv b\;\;(\text{mod }n)$ 이라 가정하자. 정의에 의하여 $a-b=kn$ 이 되는 $k\in\mathbb{Z}$ 가 존재한다. 나눗셈 알고리즘을 사용하면,
$$\left\{ \begin{array}{cl}
a=q_1n+r_1 & \ (0\leq r_1 < n) \\
b=q_2n+r_2 & \ (0\leq r_2 < n)
\end{array} \right.$$
그러면 $a-b=n(q_1-q_2)+(r_1-r_2)=kn$ 이 되고, 따라서 $r_1-r_2=0$ 이 된다.6 고로 $a,b$ 를 $n$ 으로 나누었을 때 음이 아닌 나머지들 $r_1,r_2$ 는 그 값이 같다.
$\Leftarrow$ : 두 정수 $a,b$ 가 음이 아닌 동일한 나머지를 가진다고 가정하고, $n$ 으로 나누었을 때 그 나머지를 $r$ 이라 하자. 나눗셈 알고리즘에 의하여
$$\left\{ \begin{array}{cl}
a=q_1n+r & \ (0\leq r < n) \\
b=q_2n+r & \ (0\leq r < n)
\end{array} \right.$$
가 성립한다. 여기서 $a-b=n(q_1-q_2)$ 가 되므로, 두 수의 차는 $n$ 의 배수이다. 즉 $a\equiv b\;\;(\text{mod }n)$ 이다. $_\blacksquare$
[참고문헌]
Introduction to Number Theory - William W. Adams, Larry Joel Goldstein
- 복수형은 moduli [본문으로]
- $n$ 의 값이 자연수여야 하기 때문에, $b-a$ 인 것인지 $a-b$ 인 것인지 제대로 적는 것이 좋습니다. 물론 $k$ 의 부호를 설정해서 $a-b$ 또는 $b-a$ 와 맞혀 줄 수 있기는 하겠지만 정의 상으로는 $a,b$ 의 순서가 중요합니다. [본문으로]
- 추상대수학에서 벡터공간과 같은 '가군(module)' 또한 어원이 이것과 같습니다. [본문으로]
- $n$ 의 값이 자연수여야 하기 때문에, $b-a$ 인 것인지 $a-b$ 인 것인지 제대로 적는 것이 좋습니다. 물론 $k$ 의 부호를 설정해서 $a-b$ 또는 $b-a$ 와 맞혀 줄 수 있기는 하겠지만 정의 상으로는 $a,b$ 의 순서가 중요합니다. [본문으로]
- 그러니까 일대일 함수가 아니라는 것이죠 [본문으로]
- 이렇게 결론을 내릴 수 있는 까닭은 $r_1-r_2$ 가 $n$ 의 배수가 될 수 없기 때문이다. 두 수 모두 $n$ 보다 작은 양수이므로 두 수의 차는 $n$ 을 넘어설 수가 없기 때문. [본문으로]
'정수론(Number Theory) > 합동 이론' 카테고리의 다른 글
| 정수론의 합동에서 동치류들의 연산 (0) | 2024.06.29 |
|---|---|
| 합동방정식(congruence equation) (0) | 2024.06.27 |
| 합동의 연산성질(Operations on congruence in the Number Theory) (1) | 2024.06.24 |
| 정수론에서의 법 $n$ 에 대한 잉여류(residue class in the Number theory) (1) | 2024.01.29 |
댓글