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

시계에서 12시에 5시간을 더하면 17시가 아니라 다시 5시라고 말합니다. Python에서도 같은 생각이 나옵니다.

17 % 12  # 5

즉, 중요한 것은 실제 숫자 17이 아니라 “12로 나누었을 때 나머지가 5”라는 정보입니다. 이 글에서는 정수를 같은 나머지를 가지는가의 관점에서 보는 합동을 배웁니다.

What this post covers

• $a \equiv b \pmod m$의 의미를 설명합니다.
• 합동이 “나머지가 같다”는 말과 어떻게 같은지 이해합니다.
• $m \mid (a-b)$라는 표현이 왜 나오는지 봅니다.
• 합동에서 덧셈과 곱셈을 어떻게 다룰 수 있는지 간단히 확인합니다.

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

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

실험: 손으로 계산하기

합동은 큰 수를 작은 나머지로 바꾸어 보는 연습에서 시작됩니다.

실험 1. 4로 나눈 나머지

수	나눗셈	나머지
5	$5=4\times1+1$	1
9	$9=4\times2+1$	1
13	$13=4\times3+1$	1
17	$17=4\times4+1$	1

따라서 이 수들은 모두 mod 4에서 같은 나머지를 가집니다.

실험 2. 차이를 확인하기

같은 나머지를 가진 두 수의 차를 계산해 봅시다.

두 수	차	4의 배수인가?
17, 5	12	예
13, 9	4	예
21, 5	16	예

나머지가 같으면 차가 4의 배수입니다.

실험 3. mod 7에서 보기

수	7로 나눈 나머지	합동 표현
20	6	$20\equiv6\pmod7$
34	6	$34\equiv6\pmod7$
-1	6	$-1\equiv6\pmod7$

음수도 같은 나머지의 관점으로 다룰 수 있습니다.

패턴 발견

실험에서 다음 두 관점이 같은 현상을 설명한다는 것을 볼 수 있습니다.

• $a$와 $b$를 $m$으로 나누었을 때 나머지가 같습니다.
• 그러면 $a-b$는 $m$의 배수입니다.
• 반대로 $a-b$가 $m$의 배수이면 두 수는 $m$으로 나누었을 때 같은 나머지를 가집니다.

핵심 통찰은 합동이 단순한 기호가 아니라, “같은 나머지”와 “차가 기준 수의 배수”를 연결하는 언어라는 점입니다.

합동의 정의

정수 $a,b$와 양의 정수 $m$에 대해, $a$와 $b$가 $m$으로 나누었을 때 같은 나머지를 가지면

$$a \equiv b \pmod m$$

이라고 씁니다. 이것을 $a$와 $b$가 mod $m$에서 합동이라고 읽습니다.

같은 말을 나누어떨어짐으로 쓰면

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

입니다. 예를 들어

$$5\mid(7-2),\qquad 6\mid(47-35)$$

이므로

$$7\equiv2\pmod5,\qquad 47\equiv35\pmod6$$

입니다.

특히 $a$를 $m$으로 나눈 나머지가 $r$이면 $a\equiv r\pmod m$입니다. 나머지 $r$은 보통 $0\le r<m$ 범위에서 고릅니다.

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

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

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

둘 다 나머지가 1이므로

$$17 \equiv 5 \pmod 4$$

입니다.

또 차를 보면

$$17 - 5 = 12$$

이고, 12는 4의 배수입니다. 그래서 “나머지가 같다”와 “차가 4의 배수다”는 같은 상황을 두 방식으로 말한 것입니다.

합동식은 어떻게 계산할까?

정해진 mod에서 합동은 덧셈과 곱셈에 대해 잘 유지됩니다. 예를 들어

$$17\equiv5\pmod4,\qquad 10\equiv2\pmod4$$

입니다. 그러면 더해도

$$17+10=27\equiv7=5+2\pmod4$$

이고, 곱해도

$$17\times10=170\equiv10=5\times2\pmod4$$

입니다.

일반적으로

$$a_1\equiv b_1\pmod m,\qquad a_2\equiv b_2\pmod m$$

이면

$$a_1+a_2\equiv b_1+b_2\pmod m$$

이고

$$a_1a_2\equiv b_1b_2\pmod m$$

입니다. 다음 글에서는 이 규칙을 이용해 큰 수 계산을 작게 줄이는 모듈러 연산을 더 자세히 다룹니다.

조심할 점: 나눗셈은 아직 다루지 않는다

합동에서 덧셈과 곱셈은 비교적 안전하지만, 나눗셈은 항상 되는 것이 아닙니다. 예를 들어

$$15\cdot2\equiv20\cdot2\pmod{10}$$

은 성립하지만

$$15\not\equiv20\pmod{10}$$

입니다.

즉, 양쪽에 같은 수가 곱해져 있다고 해서 무조건 지울 수는 없습니다. 이 주제는 이후 모듈러 역원과 선형 합동식에서 따로 다룹니다.

이론 정리

합동의 기본 의미

정수 $a,b$와 양의 정수 $m$에 대해

$$a\equiv b\pmod m$$

이라는 말은 $a$와 $b$가 $m$으로 나누었을 때 같은 나머지를 가진다는 뜻이다.

같은 말로,

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

라고 쓸 수 있다.

또한 합동은 덧셈과 곱셈에 대해 유지된다.

Python으로 확인하기

아래 코드는 두 수가 같은 나머지를 가지는지와 차가 mod의 배수인지 동시에 확인합니다.

def congruent(a, b, n):
    same_remainder = (a % n) == (b % n)
    difference_multiple = (a - b) % n == 0
    return same_remainder, difference_multiple

examples = [(7, 2, 5), (47, 35, 6), (-7, 1, 8), (20, 6, 7)]

for a, b, n in examples:
    print(a, b, n, congruent(a, b, n))

모든 예시에서 두 결과가 함께 참으로 나오는지 확인해 보세요.

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

이번 글에서는 합동을 $m\mid(a-b)$라는 나누어떨어짐의 언어로 정의하고, 이것이 같은 나머지를 가진다는 말과 같음을 정리했습니다. 또한 합동이 덧셈과 곱셈에 대해 유지된다는 점을 간단히 확인했습니다.

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