[정수론 입문 시리즈 11편] 합동은 왜 나머지의 언어가 될까?

앞부분의 시리즈에서는 정수를 약수, 최대공약수, 소인수분해의 관점에서 봤습니다. 이제부터는 정수를 “서로 얼마나 차이나는가”가 아니라 “같은 나머지를 가지는가”의 관점에서 보게 됩니다. 이때 중심이 되는 개념이 합동입니다.

What this post covers

• $a \equiv b \pmod n$의 의미를 설명합니다.
• 합동이 “나머지가 같다”는 말과 어떻게 같은지 이해합니다.
• 간단한 예시로 합동을 읽는 감각을 익힙니다.
• 다음 글의 모듈러 연산으로 자연스럽게 이어집니다.

이번 글에서 새로 나오는 용어

• 합동 (Congruence): 두 정수가 어떤 수 $n$으로 나누었을 때 같은 나머지를 가진다는 관계입니다.
• 나머지 (Remainder): 나눗셈에서 남는 부분입니다.
• 모듈러 연산 (Modular Arithmetic): 나머지를 기준으로 계산하는 방식입니다.
• 나누어떨어짐 (Divisibility): 어떤 정수가 다른 정수를 나머지 없이 나누는 관계입니다.

합동의 정의

정수 $a,b,n$에 대해 $n>0$라고 합시다. 이때

$$a \equiv b \pmod n$$

이라고 쓰는 것은 $a$와 $b$를 $n$으로 나누었을 때 나머지가 같다는 뜻입니다.

여기서 $n>0$라고 두는 이유는 나머지를 일정한 기준으로 말하기 위해서입니다. 합동은 항상 어떤 법 $n$을 기준으로 보는 관계라는 점이 중요합니다.

같은 말을 다른 방식으로 하면

$$n \mid (a-b)$$

라는 뜻이기도 합니다. 즉, 두 수의 차가 $n$의 배수이면 합동입니다.

왜 “나머지가 같다”와 같은 말일까?

예를 들어 $17$과 $5$를 4로 나누어 봅시다.

• $17 = 4 \times 4 + 1$
• $5 = 4 \times 1 + 1$

둘 다 나머지가 1이므로

$$17 \equiv 5 \pmod 4$$

입니다.

또 차를 보면

$$17 - 5 = 12$$

이고, 12는 4의 배수입니다. 따라서 합동의 두 정의가 같은 방향을 가리킨다는 점을 확인할 수 있습니다.

즉, 합동은

• “나머지가 같다”는 계산 관점과
• “차가 $n$의 배수다”라는 구조 관점

을 이어 주는 개념입니다.

예시 몇 가지

$14 \equiv 2 \pmod 6$

14를 6으로 나누면 나머지가 2이고, 2를 6으로 나누어도 나머지가 2입니다. 따라서 성립합니다.

또는

$$14 - 2 = 12$$

가 6의 배수이므로 성립합니다.

$20 \equiv 6 \pmod 7$

20과 6은 모두 7로 나누면 나머지가 6입니다. 따라서 성립합니다.

$11 \equiv 3 \pmod 4$

11과 3은 모두 4로 나누면 나머지가 3입니다. 따라서 성립합니다.

합동은 왜 유용할까?

합동을 쓰면 큰 수를 더 작은 나머지 대표값으로 바꾸어 생각할 수 있습니다.

예를 들어 101을 5로 나눈 나머지는 1이므로, mod 5의 세계에서는 101을 1처럼 다룰 수 있습니다. 이렇게 큰 수를 작은 대표값으로 바꾸면 계산이 훨씬 단순해집니다. 다음 글에서는 바로 이 대표값을 이용해 덧셈, 곱셈, 거듭제곱을 빠르게 계산합니다.

이 아이디어가 다음 글의 모듈러 연산으로 이어집니다.

Common mistakes

1. 합동을 등호와 완전히 같은 것으로 보는 실수

$a \equiv b \pmod n$은 $a=b$와 다릅니다. 두 수가 실제로 같은 것이 아니라, mod $n$에서 같은 나머지 부류에 있다는 뜻입니다.

2. mod를 빼먹는 실수

합동은 항상 어떤 기준 $n$에 대해 말해야 합니다. $17 \equiv 5$만 쓰면 정보가 부족합니다.

3. 나머지가 같다는 말만 외우고 차의 배수 조건을 놓치는 실수

두 관점은 서로 바꿔 쓸 수 있어야 합니다. 특히 증명에서는 $n \mid (a-b)$ 형태가 자주 쓰입니다.

Wrap-up

이번 글에서는 합동이 두 정수가 어떤 수 $n$으로 나누었을 때 같은 나머지를 가진다는 관계이며, 동시에 그 차가 $n$의 배수라는 뜻이라는 점을 정리했습니다.

다음 글에서는 이 관계 위에서 실제로 덧셈, 곱셈, 거듭제곱을 어떻게 다루는지 모듈러 연산으로 이어가겠습니다.