별과 정리 · 제93장 · 1부 · 누구나 손댈 수 있는 것

시계 산수

Modular Arithmetic

9시에서 5시간 뒤는 2시 — 12로 나눈 나머지의 세계

10시에 5시간을 더하면

시계 바늘이 오전 10시를 가리키고 있습니다. 여기서 5시간이 지나면 몇 시가 될까요?

이지만 시계에는 15시가 없고 오후 3시가 됩니다. 숫자가 12를 넘어가는 순간 다시 0으로 돌아오는 마법 같은 산수의 규칙은 무엇일까요?

이야기

1801년, 스물넷의 가우스가 『산술 연구』를 펴냅니다. 그 책 첫 쪽에서 그는 새 기호를 하나 내놓습니다. ≡. 「나머지가 같다」를 나타내는 이 기호 하나로 수론이 통째로 정리됩니다.

그런데 정작 이 「시계 산수」가 오늘 가장 크게 쓰이는 곳은 시계가 아닙니다. 인터넷에서 카드 번호를 감출 때, 은행 앱이 본인을 확인할 때 — 그 안에서 도는 계산이 전부 나머지 셈입니다. 아주 큰 수로 나눈 나머지만 주고받으면, 원래 수를 되찾기가 어렵기 때문입니다.

왜 나머지만 봐도 될까요. 시계에서 12를 지나면 다시 1로 돌아오듯, 한 바퀴는 없는 셈 치기 때문입니다. 12시간이 지나면 시계는 제자리이고, 그러니 12의 배수는 아무 일도 하지 않습니다.

요일도 같습니다. 오늘이 화요일이면 100일 뒤는 무슨 요일일까요. 100을 7로 나누면 나머지가 2이므로, 7의 배수만큼은 통째로 무시하고 이틀만 세면 됩니다. 목요일입니다.

오늘 이것이 하는 일

모든 암호가 시계 산수 위에 서 있습니다. 「나머지만 보는 셈」이 곧 모듈러 연산입니다.

주민번호와 카드번호의 검증 숫자, 해시 함수, 난수 생성기가 모두 이 산수를 씁니다.

계단 넷 — 같은 사실을 네 깊이로

초4 · 초5 — 손으로 해 본다

시계를 돌려 본다

1부터 12까지 적힌 둥근 시계판을 손가락으로 짚으며 돌아보세요. 12 다음은 13이 아니라 다시 1입니다.

달력도 마찬가지입니다. 오늘이 화요일이면 7일 뒤, 14일 뒤, 70일 뒤도 언제나 화요일입니다. 숫자가 끝없이 커지지 않고 일정한 크기마다 제자리로 뱅글뱅글 맴도는 시계 산수를 경험해 보세요.

시곗바늘을 돌려 보세요

지금 시각과 지날 시간을 밀어 보세요.

몇 시 —한 바퀴 돈 횟수 —합 —

지금 — 9 시

몇 시간 뒤 — 8 시간

9 + 8 = 17 인데 시계는 5 시를 가리킵니다.
12 를 넘으면 다시 처음으로 — 이것이 나머지 셈입니다.

중1 · 중2 — 까닭을 찾는다

나머지로 계산하기

어떤 정수를 12로 나눈 나머지만 생각하는 계산법을 합동식(Modular arithmetic)이라 부릅니다.

가우스는 두 수 를 12로 나눈 나머지가 같을 때 로 표기하자고 약속했습니다. 처럼 합동식에서는 더하기, 빼기, 곱하기를 할 때 미리 나머지를 구해서 계산해도 결과가 같습니다.

나머지로 세어 보세요

수와 나눌 수를 밀어 보세요.

a mod m —몫 —a —

수 a — 137

나눌 수 m — 12

a = m×몫 + 나머지.
시계는 m = 12, 요일은 m = 7, 초는 m = 60 입니다.

고1 · 고2 — 넓혀 본다

합동식과 성질

합동식 체계 에서 나눗셈은 모듈러 곱셈 역원(Modular multiplicative inverse)을 곱하는 것으로 정의됩니다.

이 되는 는 (서로소)일 때만 유클리드 호제법으로 유일하게 존재합니다. 이 원리가 페르마의 소정리와 오일러 피 함수로 확장됩니다.

거듭제곱의 나머지

밑·지수·나눌 수를 밀어 보세요.

aᵉ mod m —m−1 —e mod (m−1) —

밑 a — 7

지수 e — 13

나눌 수 m — 11

페르마의 작은 정리 : m 이 소수면 a^(m−1) ≡ 1.
지수를 m−1 로 나눈 나머지만 보면 됩니다 — 큰 거듭제곱이 순식간에 풀립니다.

대학 — 어디까지 가나

순환군

시계 산수는 현대 대수학에서 순환군(Cyclic group) 및 잉여류환(Quotient ring)의 구조를 이룹니다.

소수 에 대해 는 완벽한 유한체(Finite field, Galois field)를 형성하며, 현대 인터넷 보안을 책임지는 RSA 공개키 암호와 타원곡선 디피-헬만(ECDH) 키 교환의 핵심 수학적 기반이 됩니다.

RSA 를 만져 보세요

두 소수와 공개 열쇠를 밀어 보세요.

N = pq —φ = (p−1)(q−1) —비밀 열쇠 d —

소수 p — 11

소수 q — 3

공개 열쇠 e — 7

N 은 공개해도 됩니다. 하지만 N 에서 p·q 를 되찾기가 어렵습니다.
그 어려움 하나에 오늘의 모든 은행이 걸려 있습니다.

풀어 보기

중학교 · 고등학교 수준 · 답은 검산을 마쳤습니다

합동식의 계산과 요일 산수. 다음 물음에 답하시오.

(1) 오늘이 목요일일 때, 오늘부터 일 뒤는 무슨 요일인지 합동식 을 이용하여 구하시오.
(2) 을 7로 나눈 나머지를 구하시오.
(3) 합동방정식 을 만족하는 가장 작은 양의 정수 를 구하시오.

(2) 는 임을 이용해 지수를 줄여 보세요.

답과 풀이 보기

(1) 토요일입니다.

목요일에서 2 일 뒤이므로 금 → 토요일.
⭐ 98 일은 꼭 14 주라 요일이 그대로입니다. 남는 것은 2 일뿐입니다.

(2) 나머지는 4 입니다.

이므로

⭐ 100 제곱을 직접 셈하지 않았습니다. 하나를 찾아내자 지수가 통째로 접혔습니다.

(3) 입니다.
— 맞습니다.
이 를 의 역원이라 합니다. 7 로 나눈 세계에서는 이 5 라는 뜻입니다.

시계는 12 를 지나면 1 로 돌아옵니다. 요일은 7 을 지나면 처음으로 돌아옵니다.
이렇게 되돌아오는 세계에서는 처럼 어마어마한 수도 0 부터 6 까지 일곱 칸 안에서 다 끝납니다. 카드 결제의 암호가 바로 이 세계에서 돌아갑니다.

여기 「풀어 보기」는 기본 한 벌입니다. 더 풀어 보고 싶으면 행복수학의 그 단원으로 건너가세요.

중1-2 01 기본 도형

만지는 수학으로 손에 쥐어 보기

이 장과 이어지는 「만지는 수학」 칼럼입니다. 손끝으로 직접 끌고 눌러 보며 같은 생각을 몸으로 겪을 수 있습니다.

시각과시간초2 몇시초1

더 멀리

모듈러 연산은 디지털 세상의 기본 셈법입니다.

암호 — RSA는 큰 수의 나머지 계산으로 돌아갑니다
검증번호 — 주민번호·바코드·계좌번호의 마지막 자리가 나머지로 만들어집니다
해시 — 자료를 상자에 나눠 담을 때 나머지를 씁니다

이어지는 장

시계를 돌리듯 나머지만 남기는 이 산수는 비밀 메시지를 암호화하는 현대 공개키 암호의 뼈대가 되고, 요일을 순식간에 알아맞히는 마법이 됩니다 — 제4장 과 제74장 에서 시계 산수의 강력한 힘을 볼 수 있습니다.

영감을 받은 곳

카를 프리드리히 가우스(Carl Friedrich Gauss)가 1801년 『산술 연구(Disquisitiones Arithmeticae)』 제1장에서 합동식 기호(≡)와 모듈러 산술 체계를 엄밀하게 정립한 연구에서 왔습니다.