정수론 2강. 모듈러 산술: 시계의 수학
시계는 12를 넘는 순간 0으로 돌아갑니다. 나머지만 남기는 이 단순한 규칙이 정수론 전체의 문법이 됐습니다.
풀고 시작
나머지만 남기는 세계
시계를 봅시다. 11시에서 3시간이 지나면 14시가 아니라 2시입니다. 12에 도달하는 순간 처음으로 되돌아가기 때문이죠. 요일도 같습니다. 오늘이 무슨 요일이든 7일 뒤는 같은 요일입니다. 이런 계산의 공통 구조를 합동(congruence)이라 부릅니다. 두 정수 a와 b를 m으로 나눈 나머지가 같을 때 "a와 b는 m을 법으로 합동이다"라고 말하고 a ≡ b (mod m)으로 씁니다. 14 ≡ 2 (mod 12)이고, 100 ≡ 2 (mod 7)이죠.
발상의 전환은 이것입니다. 나머지가 같은 수들을 아예 같은 수로 취급해 버립니다. mod 12의 세계에는 사실상 0부터 11까지 열두 개의 수만 존재합니다. 무한한 정수 전체가 유한한 세계로 접히는 것이죠.
합동식은 계산을 견딘다
이 접기가 강력한 이유는 합동이 덧셈과 곱셈을 그대로 통과시키기 때문입니다. a ≡ b (mod m)이고 c ≡ d (mod m)이면, a + c ≡ b + d (mod m)이고 a × c ≡ b × d (mod m)입니다. 즉 큰 수로 계산한 뒤 나머지를 구하나, 먼저 나머지로 바꾼 뒤 계산하나 결과가 같습니다.
익숙한 판정법들이 전부 이 성질의 응용입니다. 어떤 수가 짝수인지, 5의 배수인지는 끝자리만 보면 아는데, 10이 2와 5의 배수여서 끝자리를 제외한 부분이 통째로 0으로 접히기 때문이죠.
위력은 거듭제곱에서 드러납니다. 7¹⁰⁰을 4로 나눈 나머지를 구한다고 해 봅시다. 7¹⁰⁰을 실제로 계산하면 84자리 수가 되지만, 7 ≡ 3 (mod 4)이고 3² = 9 ≡ 1 (mod 4)이므로 7¹⁰⁰ ≡ 3¹⁰⁰ = (3²)⁵⁰ ≡ 1⁵⁰ = 1 (mod 4)입니다. 거대한 계산이 세 줄로 끝나죠. 익숙한 예도 있습니다. 어떤 수의 각 자리 숫자의 합이 3의 배수면 그 수가 3의 배수라는 판정법은, 10 ≡ 1 (mod 3)이어서 10의 거듭제곱이 전부 1로 접히기 때문에 성립합니다.
다만 나눗셈은 다릅니다. 6 ≡ 2 (mod 4)라고 해서 양변을 2로 나눈 3 ≡ 1 (mod 4)이 성립하지는 않습니다. 나누는 수와 법 m이 서로소일 때만 나눗셈이 허용되죠. 이 제약이 3강에서 소수가 특별해지는 이유와 직결됩니다.
검증 숫자: 일상 속의 mod
모듈러 산술은 우리 지갑 안에서 매일 작동합니다. 상품 바코드, 도서의 ISBN, 주민등록번호의 마지막 자리는 모두 체크 숫자(check digit)입니다. 앞자리들에 정해진 가중치를 곱해 더한 값의 나머지가 약속된 값이 되도록 마지막 자리를 정해 둡니다. ISBN-13은 각 자리에 1과 3을 번갈아 곱해 더한 총합이 10의 배수가 되도록 설계되어 있고, 주민등록번호는 앞 12자리에 가중치를 곱한 합을 11로 나눈 나머지로 마지막 자리를 만듭니다.
한 자리를 잘못 입력하면 어떻게 될까요? 가중합이 달라져 나머지가 약속을 벗어나고, 시스템은 즉시 오류를 잡아냅니다. 오타의 대부분을 통신도 조회도 없이 산수 한 줄로 걸러내는 것이죠. 나머지 연산이 곧 오류 검출 장치입니다.
가우스, 정수론에 문법을 주다
합동 기호 ≡와 이 이론의 체계는 가우스(Carl Friedrich Gauss, 1777~1855)의 작품입니다. 그는 스물네 살이던 1801년 『산술 연구』(Disquisitiones Arithmeticae)를 출간하며 첫 장을 합동 이론으로 열었습니다. 그 전까지 페르마와 오일러의 정수론은 천재들의 개별 발견이 흩어진 상태였는데, 가우스는 합동이라는 표기법과 개념으로 이를 하나의 학문으로 묶었죠. 좋은 기호는 단순한 줄임말이 아니라 사고의 도구라는 것을 보여 준 사례입니다. 가우스가 정수론을 "수학의 여왕"이라 불렀다는 이야기는 널리 전해집니다.
가우스가 정리한 이 문법 위에서, 다음 강은 페르마와 오일러가 발견한 거듭제곱의 놀라운 주기성을 다룹니다. 그것이 결국 RSA 암호의 심장이 됩니다.
인출 문제
생각해볼 질문 (정답 없음)
- 무한한 정수를 유한한 나머지 세계로 접는 것은 정보를 버리는 일입니다. 그런데 왜 버림으로써 오히려 더 많은 것이 보일까요?
- 좋은 표기법이 새로운 정리를 낳는다면, 기호는 생각의 기록일까요 생각의 일부일까요?