합동식(모듈러 산술)
“모듈러 산술은 '시계 산술' — 한 바퀴 돌면 처음으로 돌아온다.”
수식
a ≡ b (mod n) ⟺ n | (a − b)읽는 법: a와 b를 n으로 나눈 나머지가 같으면, 즉 a−b가 n의 배수이면 a와 b는 mod n에서 합동이다
- a ≡ b
- — a와 b가 합동(같은 나머지)이라는 표시
- mod n
- — n을 기준(법)으로 삼는다는 뜻 — 시계라면 12
- n | (a−b)
- — n이 a−b를 나눈다(배수다)는 뜻
이야기의 시작
시계에서는 9시의 5시간 뒤가 14시가 아니라 2시다. 이 '한 바퀴 돌면 처음으로' 산술이 모듈러 산술이다.
쉬운 말로
모듈러 산술은 어떤 수 n에서 한 바퀴 돌아 0으로 돌아오는 산술이다. 두 수가 n으로 나눈 나머지가 같으면 '합동'이라 하고 a ≡ b (mod n)으로 쓴다. 오직 나머지만 신경 쓴다.
직관
수직선을 길게 늘어놓는 대신, n칸짜리 원(시계판)에 감아버린다고 상상하라. n을 넘어가면 다시 0으로 돌아온다. 12시간 시계에서 17시는 5시와 같은 자리 — 17과 5는 mod 12에서 합동이다. 큰 수를 '바퀴 위 위치'로 접어버리는 것.
어떻게 만들어지나
핵심은 나머지. a를 n으로 나눈 나머지가 곧 a의 'mod n 값'이다. 덧셈·뺄셈·곱셈이 나머지끼리 그대로 성립해서, 큰 수를 다 계산할 필요 없이 나머지만 굴리면 된다 — (a+b) mod n은 각각의 나머지를 더해 다시 mod n 하면 끝.
예시
17 ≡ 5 (mod 12) 인 이유: 17 − 5 = 12 는 12의 배수. 시계로는 17시가 곧 오후 5시. 또 25 mod 7 = 4 인데, 25 = 3·7 + 4 이기 때문.
흔한 오해
나머지는 음수가 되지 않는다는 약속이 흔히 쓰인다. 예컨대 −1 mod 5 는 −1이 아니라 4다 (−1 = (−1)·5 + 4). 시계에서 뒤로 한 칸 가면 11시가 되는 것과 같다(12시계).
어디에 쓰나
RSA·타원곡선 등 현대 암호의 심장, 해시함수와 체크섬(ISBN·신용카드 검증), 요일·달력 계산, 난수 생성기, 음악의 12음계 — 순환하는 모든 계산에 모듈러 산술이 쓰인다.
어디서 왔나
가우스가 1801년 『산술 연구』에서 합동 기호 ≡를 도입하며 정수론을 체계화했다. '수학의 여왕은 정수론'이라던 그의 대표 무기였다.
선행 개념
확인 문제
25 mod 7 의 값은? (25를 7로 나눈 나머지)
- 3
- 4✓
- 5
- 11
연습
17 mod 5 를 구하라.
정답: 2
- 17 = 3·5 + 2
- 나머지는 2
핵심: mod n = n으로 나눈 나머지.
(7 + 8) mod 12 를 구하라.
정답: 3
- 7 + 8 = 15
- 15 mod 12 = 3 (한 바퀴 돌고 3)
핵심: 시계 산술 — 12를 넘으면 다시 0부터.
(4 × 6) mod 5 를 구하라.
정답: 4
- 4 × 6 = 24
- 24 = 4·5 + 4, 나머지 4
핵심: 곱셈도 나머지끼리 그대로 성립한다.
오늘이 월요일이면 100일 뒤는 무슨 요일인가? (mod 7 을 이용)
정답: 1
- 100 mod 7 = 2 (98 = 14·7 이므로 나머지 2)
- 월요일 + 2일 = 수요일
핵심: 요일 계산은 mod 7 — 7일마다 제자리.