모듈러 산술 — 시계 산수, mod와 합동

모듈러 산술은 법이라고 하는 고정된 양의 정수로 나눈 뒤의 나머지를 기준으로 계산하는 방법입니다. 두 수의 나머지가 같으면 그 모듈러 체계에서는 같은 방식으로 작동하므로, 흔히 시계 산수라고도 부릅니다.

$12$시간 시계에서는 $13$시는 $1$시에 해당하고, $29$시간도 $5$시간과 같은 위치에 옵니다. 이렇게 반복되는 순환이 바로 모듈러 산술의 핵심 직관입니다.

모듈러 산술에서 Mod의 뜻

정수 $a$와 양의 정수 $n$에 대해, $a \bmod n$은 $a$를 $n$으로 나누었을 때의 나머지를 뜻합니다.

예:

$$29 \bmod 12 = 5$$

왜냐하면

$$29 = 12 \cdot 2 + 5$$

이기 때문입니다.

법이 $12$이므로, $12$를 더하거나 빼도 순환에서의 위치는 바뀌지 않습니다.

법 $n$에 대한 합동의 뜻

합동은 두 정수가 법 $n$에 대해 같은 방식으로 작동한다는 것을 형식적으로 나타내는 표현입니다.

$$a \equiv b \pmod n$$

은 $a$와 $b$를 $n$으로 나누었을 때 나머지가 같다는 뜻입니다. 이에 대한 동치 조건은

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

이며, 이는 “$n$이 $a-b$를 나눈다”는 뜻입니다.

따라서

$$29 \equiv 5 \pmod{12}$$

입니다. 왜냐하면 $29 - 5 = 24$이고, $12$는 $24$를 나누기 때문입니다.

이 차이는 중요합니다.

• $29 \bmod 12 = 5$는 나머지에 대한 진술입니다.
• $29 \equiv 5 \pmod{12}$는 합동에 대한 진술입니다.

서로 관련은 있지만, 같은 뜻으로 바꿔 쓸 수는 없습니다.

예제: $8$시에서 $29$시간 후

지금이 $8$시라고 하고, $12$시간 시계에서 $29$시간 후가 몇 시인지 구해 봅시다.

먼저 $29$를 법 $12$로 줄입니다.

$$29 \bmod 12 = 5$$

따라서 $29$시간을 더하는 것은 $5$시간을 더하는 것과 같은 효과를 냅니다.

$$8 + 29 \equiv 8 + 5 \pmod{12}$$

그러면

$$8 + 29 \equiv 13 \equiv 1 \pmod{12}$$

이므로 시계는 $1$시를 가리킵니다.

핵심은 먼저 줄이는 단계입니다. 법 $12$에서는 $29$를 $5$로 바꿔도 답이 같고, 계산은 훨씬 쉬워집니다.

먼저 줄이면 왜 계산이 쉬워질까

큰 수는 더 작은 합동인 수로 바꾼 뒤 다루는 편이 훨씬 쉽습니다.

예를 들어 법 $7$에서는

$$100 \equiv 2 \pmod 7$$

입니다. 왜냐하면 $100 - 2 = 98$이 $7$로 나누어떨어지기 때문입니다. 문제에서 법 $7$만 중요하다면, $100$ 대신 $2$로 계산해도 됩니다.

자주 하는 실수

등호와 합동을 혼동하기

$29 \equiv 5 \pmod{12}$는 $29 = 5$라는 뜻이 아닙니다. 법 $12$에서 둘이 같은 나머지류에 속한다는 뜻입니다.

법이 중요하다는 점을 잊기

$17 \equiv 5 \pmod{12}$는 참이지만, $17 \equiv 5 \pmod{10}$은 거짓입니다. 합동은 항상 특정한 법에 대해 말하는 것입니다.

mod를 보통의 나눗셈처럼 다루기

$29 \bmod 12$는 나머지 $5$를 뜻합니다. 몫 $2$도 아니고, 분수 $29/12$도 아닙니다.

소프트웨어의 %가 항상 같은 수학적 관례를 따른다고 생각하기

양수에서는 프로그래밍 언어의 %가 학생들이 처음 배우는 나머지 개념과 자주 일치합니다. 하지만 음수에서는 관례가 다를 수 있어서, 많은 수학 수업에서 쓰는 최소 비음수 나머지와 결과가 다를 수 있습니다.

모듈러 산술은 어디에 쓰일까

값이 주기적으로 반복되는 곳에서는 어디서나 모듈러 산술이 등장합니다. 시계, 요일 계산, 검사 숫자 시스템, 해싱, 그리고 수론의 많은 부분이 여기에 해당합니다.

암호학에서도 등장하지만, 기본 아이디어는 같습니다. 수를 나머지에 따라 묶고, 합동인 수들을 그 체계 안에서 같은 것으로 다룹니다.

비슷한 문제를 풀어 보기

월요일로부터 $100$일 후는 무슨 요일일까요? 요일은 법 $7$로 반복되므로, 답하기 전에 먼저 $100$을 $7$로 나눈 나머지로 줄여 보세요.

비교할 다른 사례가 필요하다면, GPAI Solver에서 직접 비슷한 문제를 만들어 보고 먼저 줄이는 것이 계산을 얼마나 짧게 만드는지 확인해 보세요.