모듈러 연산 직관적으로 이해하기 (시계 산수와 나머지가 모든 것을 결정하는 이유)

지금은 아홉 시이고 비행기는 다섯 시간 뒤에 떠납니다. "열네 시"라고 답하는 사람은 없습니다. 여러분은 두 시라고 말하고, 생각할 틈도 없이 그렇게 합니다. 시계 문자판에는 열넷이라는 자리가 없기 때문입니다. 시각은 열둘에서 한 바퀴를 돌아 다시 시작합니다. 시계를 읽을 수 있게 된 날부터 여러분은 모듈러 연산을 해 왔습니다. 기호를 만나 본 적이 없을 뿐입니다.

이 주제는 그것이 전부입니다. 한 바퀴를 돌 기준 수를 정하고, 다 돈 바퀴는 모두 잊고, 어디에 멈췄는지만 남깁니다. 한 편의 글이 될 만한 이유는 나머지만 남기는 이 습관 하나가 정면으로는 불가능해 보이는 문제들을 풀어 주기 때문입니다. 일흔 자리 수의 마지막 자리, 거대한 수가 9로 나누어떨어지는지 여부, 신용카드 번호가 유효한지 아닌지, 그리고 의도한 사람만 되돌릴 수 있도록 메시지를 뒤섞는 방법까지.

이 글은 그 그림입니다. 나머지가 정말 무엇인지, 계산하기 전에 먼저 줄여도 되는 이유, 음수와 거듭제곱에서는 무슨 일이 벌어지는지, 그리고 이 주제의 유일한 정직한 난관인 나눗셈이 어디에서 오는지를 다룹니다.

나머지는 남은 것이 아니라 멈춘 자리다

표준적인 정의는 $a \bmod n$이 $a$를 $n$으로 나눈 나머지라고 말합니다. 맞는 말이고, 동시에 이 주제가 잡일처럼 느껴지는 이유이기도 합니다. "나머지"라는 말은 나눗셈이 끝난 뒤 남은 찌꺼기, 곧 뒷생각처럼 들리기 때문입니다.

더 나은 그림: 눈금이 $n$개 있고 $0$부터 $n-1$까지 번호가 붙은 원형 트랙. $a \bmod n$을 찾으려면 $0$에서 출발해 트랙을 $a$걸음 걸어갑니다. 멈춘 자리가 답입니다. 눈금이 5개인 트랙을 17걸음 걸으면 세 바퀴(15걸음)를 다 돌고 2걸음을 더 가므로 눈금 2에 멈춥니다. 그래서 $17 \bmod 5 = 2$입니다. 다 돈 바퀴가 몫이고, 멈춘 자리가 나머지입니다.

이 그림은 정의가 하지 못하는 두 가지를 합니다. 눈금이 그것뿐이므로 나머지가 언제나 $0$과 $n-1$ 사이에 떨어지게 만듭니다. 그리고 한참 달라 보이는 두 수가 어째서 $n$을 기준으로 "같은" 수가 될 수 있는지 설명해 줍니다. $2$, $17$, $102$, $5{,}000{,}002$는 눈금 5개짜리 트랙에서 모두 눈금 2에 멈춥니다. 이 수들은 바퀴 수만큼 다르고, 트랙은 바퀴를 기억하지 않습니다.

수학자들은 그 생각을 합동식으로 적습니다:

$$17 \equiv 2 \pmod{5}$$

"17은 5-트랙에서 2가 멈추는 자리에 멈춘다"로 읽으십시오. 삼중 막대는 등호가 아닙니다. 17과 2는 같지 않으니까요. 이 기호는 트랙 위의 위치만 따지는 질문이라면 둘을 바꿔 써도 된다고 말합니다. 정확한 형태로 쓰면, $a \equiv b \pmod{n}$은 $n$이 $a - b$를 나눈다는 뜻이고, 이는 두 수가 바퀴의 정수 개만큼 다르다는 말일 뿐입니다.

덧셈과 곱셈은 지금 어디 있는지만 따진다

모듈러 연산을 신기한 구경거리가 아니라 도구로 만드는 사실이 여기 있습니다. 두 수를 더한 다음 나머지를 구할 생각이라면, 나머지를 먼저 구해 그것들을 더하고 다시 줄여도 됩니다. 답은 똑같습니다. 뺄셈과 곱셈에서도 마찬가지입니다.

트랙 위에서는 당연한 이야기입니다. 17을 더한다는 것은 17걸음 걷는 것이고, 그것은 세 바퀴에 2걸음입니다. 세 바퀴는 출발한 자리로 되돌려 놓을 뿐 아무것도 바꾸지 않으므로, 17을 더하는 일은 2를 더하는 일과 효과가 정확히 같습니다. 수 안에 숨어 있는 바퀴는 죽은 무게이고, 덧셈을 거쳐도 곱셈을 거쳐도 계속 죽은 무게로 남습니다. $n$의 배수에 무엇을 곱해도 여전히 $n$의 배수이기 때문입니다.

$a = qn + r$, $b = pn + s$로 놓고 적어 보면:

$$ab = (qn + r)(pn + s) = n(qpn + qs + rp) + rs$$

첫 괄호 안에 있는 것은 전부 바퀴입니다. $rs$만 살아남으므로 $ab \bmod n$은 $rs \bmod n$입니다. 나머지가 질문에 필요한 정보를 모두 지니고 있습니다.

Math Zen의 산술 주제에 있는 조언이 전체 값을 계산하지 말고 한 단계씩 줄여 나가라고 말하는 이유가 이것입니다. $123 \times 456 \bmod 7$을 구한다고 해 봅시다. 56,088까지 곱해 놓고 7로 긴 나눗셈을 할 수도 있습니다. 아니면 $123 = 119 + 4$이므로 $123 \equiv 4$이고, $456 = 455 + 1$이므로 $456 \equiv 1$이어서 답이 $4 \times 1 = 4$라는 것을 알아챌 수도 있습니다. 작은 줄이기 두 번이 네 자리 곱셈을 대신합니다. 습관은 이렇습니다. 나머지만 따질 생각이라면 어떤 수도 $n$을 넘게 키우지 마십시오.

음수는 반대 방향으로 걷는다

트랙 그림은 대부분의 사람이 걸려 넘어지는 경우도 처리해 줍니다. $-3 \bmod 5$는 무엇일까요?

눈금 5개짜리 트랙에서 0에서 뒤로 3걸음 걸어갑니다. 4를 지나고, 3을 지나고, 2에 멈춥니다. 그래서 $-3 \equiv 2 \pmod{5}$입니다. 음수는 그저 반대 방향으로 걷는 일이고, 이는 음수 직관적으로 이해하기와 같은 생각입니다. 나머지는 여전히 멈춘 자리이고, 여전히 $0$과 $n-1$ 사이에 있습니다.

빠른 방법: 수가 양수가 될 때까지 바퀴를 더하십시오. $-3 + 5 = 2$입니다. $-14 \bmod 5$라면 15(세 바퀴)를 더해 1을 얻습니다. 계산기와 프로그래밍 언어는 음수 나머지에 대해 서로 다른 규칙을 쓰고, 어떤 것은 $-14 \bmod 5$에 $-4$를 돌려주기도 합니다. 그러니 시험에서는 언제나 트랙 위의 음이 아닌 눈금으로 답을 적고, 계산기를 믿기 전에 그 규칙을 먼저 확인하십시오.

뺄셈도 같은 이야기입니다. $3 - 8 \pmod{5}$는 $-5$인데, 이는 정확히 뒤로 한 바퀴이므로 답은 0입니다. 아니면 먼저 줄여도 됩니다. $8 \equiv 3$이므로 $3 - 3 = 0$입니다.

거대한 거듭제곱의 마지막 자리

이것이 이 주제를 알아 둘 만하다고 사람들을 설득하는 문제이고, 먼저 줄이라는 규칙의 직접적인 결과입니다.

어떤 수의 마지막 자리는 그 수를 10으로 나눈 나머지입니다. 십의 자리, 백의 자리, 그 위의 모든 자리는 10의 배수이고 눈금 10개짜리 트랙에서 0으로 되돌아오기 때문입니다. 그래서 "$7^{100}$의 마지막 자리는 무엇인가"는 "$7^{100} \bmod 10$은 무엇인가"라는 질문이고, $7^{100}$을 계산할 필요는 전혀 없습니다.

대신 7의 거듭제곱이 10-트랙을 걸어가는 모습을 매번 줄여 가며 지켜보십시오:

• $7^1 = 7$
• $7^2 = 49 \equiv 9$
• $7^3 \equiv 9 \times 7 = 63 \equiv 3$
• $7^4 \equiv 3 \times 7 = 21 \equiv 1$
• $7^5 \equiv 1 \times 7 = 7$

1에 닿는 순간 주기가 다시 시작됩니다. 7, 9, 3, 1, 7, 9, 3, 1로 주기는 4입니다. $100 = 4 \times 25$이므로 백제곱은 완전한 주기의 끝, 곧 $7^4$와 같은 자리에 앉고 그 마지막 자리는 1입니다.

모든 밑은 10을 기준으로 주기를 가지며, 대부분 짧습니다. 2의 거듭제곱은 2, 4, 8, 6을 돕니다. 3의 거듭제곱은 3, 9, 7, 1을 돕니다. 5와 6의 거듭제곱은 아예 움직이지 않습니다. 방법은 언제나 같습니다. 줄여 가면서 주기의 길이를 찾고, 지수를 그 길이로 나누고, 그 나눗셈의 나머지가 주기의 어디에 있는지 알려 줍니다. 이것은 반복 곱셈이라는 지수의 생각을 직선이 아니라 원형 트랙 위에서 굴린 것입니다.

9의 배수 판정에서 자릿수 합이 통하는 이유

어떤 수의 자릿수를 모두 더해 9의 배수가 되면 그 수가 9로 나누어떨어진다는 것은 누구나 배우지만, 왜 그런지는 거의 아무도 배우지 않습니다. 모듈러 연산은 이것을 한 줄 논증으로 만듭니다.

10은 9-트랙에서 한 바퀴에 1입니다. 곧 $10 \equiv 1 \pmod{9}$입니다. 그러면 $100 = 10 \times 10 \equiv 1 \times 1 = 1$이고, 10의 모든 거듭제곱도 똑같이 1과 합동입니다. 그래서 $4{,}527 = 4 \times 1000 + 5 \times 100 + 2 \times 10 + 7$ 같은 수는 $4 + 5 + 2 + 7 = 18 \pmod{9}$과 합동이고, 18은 9-트랙에서 $0$이므로 4,527은 9로 나누어떨어집니다. 자릿수 합은 요령이 아닙니다. 9를 기준으로 바라본 그 수 자체입니다.

3의 판정법도 같은 이유로 통합니다. $10 \equiv 1 \pmod{3}$이기도 하니까요. 11의 판정법은 $10 \equiv -1 \pmod{11}$에서 오는데, 이 때문에 10의 거듭제곱이 $1$과 $-1$을 번갈아 오가며 교대하는 자릿수 합을 만들어 냅니다. 외우라고 들었던 나누어떨어짐 규칙들은 모두 "10의 거듭제곱을 줄여라"라는 하나의 사실을 서로 다른 트랙에 적용한 것입니다.

검사 숫자: 지갑 속의 모듈러 연산

모든 ISBN, 모든 신용카드 번호, 모든 바코드는 나머지가 되는 일만 하는 숫자 하나로 끝납니다.

13자리 ISBN의 마지막 숫자는 열세 자리 전체에 1과 3을 번갈아 가중치로 붙여 더한 값이 $0 \pmod{10}$과 합동이 되도록 정해집니다. 숫자 하나를 잘못 입력하면 그 합은 10-트랙의 다른 자리에 떨어지고, 스캐너가 거부합니다. 신용카드는 룬 알고리즘(Luhn algorithm)을 쓰는데, 조금 더 영리한 가중치 방식으로 인접한 두 숫자가 뒤바뀐 경우까지 대부분 잡아내며, 이것도 역시 10을 기준으로 합을 확인합니다.

이것들은 훨씬 큰 응용의 소박한 사촌입니다. 현대 암호는 아주 큰 $n$을 기준으로 어떤 수를 거듭제곱하는 일은 쉽지만 비밀 키 없이 그 과정을 거꾸로 되돌리는 일은 쉽지 않다는 사실에 기대고 있습니다. 위에서 $7^{100}$에 대해 했던 주기 찾기가 바로 같은 연산이며, 수백 자리 수로 규모만 키운 것입니다. 그리고 그것이 계산 가능한 유일한 이유가 가면서 줄이라는 규칙입니다.

나눗셈은 트랙이 울퉁불퉁해지는 곳

덧셈, 뺄셈, 곱셈은 트랙 위에서 수직선 위에서와 똑같이 행동합니다. 나눗셈은 그렇지 않고, 이 주제가 악명을 얻는 유일한 자리가 여기입니다.

보통의 수직선에서 4로 나누는 것은 $\tfrac{1}{4}$을 곱하는 것, 곧 4를 곱하면 1이 되는 수를 곱하는 것입니다. 12-트랙에는 4를 곱하면 1에 떨어지는 눈금이 있을까요? 전부 해 봅시다. $4 \times 1 = 4$, $4 \times 2 = 8$, $4 \times 3 = 12 \equiv 0$, $4 \times 4 = 16 \equiv 4$이고, 4, 8, 0이라는 패턴이 영원히 반복됩니다. 1에는 결코 닿지 않습니다. 그러므로 12-트랙에서 4로 나누는 일은 존재하지 않습니다.

이유는 4와 12가 인수를 공유하기 때문입니다. 4의 배수에서 출발해 12 바퀴를 더하거나 빼도 여전히 4의 배수이므로, 12의 배수보다 1 앞선 자리에는 결코 멈출 수 없습니다. 대신 5로 해 봅시다. $5 \times 5 = 25 = 24 + 1 \equiv 1$이므로 5는 12-트랙에서 자기 자신이 역원이고 5로 나누는 일은 문제없습니다. 규칙은 이렇습니다. $a$는 $a$와 $n$이 1 말고는 공통 인수를 갖지 않을 때 정확히 그때만 $n$을 기준으로 역원을 갖습니다.

이 규칙에는 눈에 띄는 결과가 하나 있습니다. $n$이 소수이면 $1$부터 $n - 1$까지 어느 수도 $n$과 인수를 공유하지 않으므로, 0이 아닌 모든 눈금이 역원을 갖고 자유롭게 나눌 수 있습니다. 소수 트랙은 네 연산이 모두 통하는 트랙이고, 소수의 무한함이 그 공급을 보장하는 소수가 정수론과 암호학의 중심에 앉아 있는 이유의 큰 부분이 이것입니다.

실수는 어디에서 오는가

모듈러 연산은 움직이는 부품이 적고, 그래서 오류도 그만큼 구체적입니다.

첫째는 밑이 아니라 지수를 줄이는 것입니다. $7^{100} \bmod 10$에서 7을 10으로 줄일 수는 있고(이미 줄어 있습니다), 주기의 길이를 알아낸 뒤 그 길이를 기준으로 지수를 줄일 수도 있지만, 100을 10으로 줄여 $7^0$을 계산해서는 안 됩니다. 지수는 다른 트랙, 곧 크기가 주기의 길이인 트랙에 살고, 두 트랙을 섞는 것이 이 주제에서 단연 가장 흔한 오류입니다.

둘째는 음수 나머지입니다. $-14 \bmod 5$는 1이고 $-4$가 아닙니다. 트랙 위의 같은 자리이지만 둘 중 하나만 관례적인 이름이고, 정답표는 음이 아닌 쪽을 원합니다.

셋째는 역원을 확인하지 않고 나누는 것입니다. 합동식 양변에서 공통 인수를 약분하는 일은 그 인수가 법과 아무것도 공유하지 않을 때만 허용됩니다. $4 \times 2 \equiv 4 \times 5 \pmod{12}$는 양변이 모두 8이므로 참이지만, 여기서 4를 약분해 $2 \equiv 5$라고 결론 내릴 수는 없고 그것은 거짓입니다. 약분할 때 버리는 바퀴는 원래 트랙의 바퀴여야 합니다.

넷째는 마지막에 줄이기를 잊는 것입니다. 7-트랙에서 $rs = 21$을 얻고 21이라고 적는 것이 딱히 틀린 것은 아니지만, 답도 아닙니다. 답은 트랙 위의 눈금이고, 21은 세 바퀴이므로 그 눈금은 0입니다.

Math Zen이 도움이 되는 지점

Math Zen의 산술 주제에는 모듈러 연산 전용 묶음이 있고, 진행은 기호가 아니라 먼저 줄이는 습관을 중심으로 짜여 있습니다. 초반 문제들은 작은 법으로 단순한 나머지와 합동식을 묻고, "나는 어디에 멈추는가"가 자동이 될 때까지 이어집니다. 중간 묶음들은 음수와 곱을 섞어 내는데, 요점은 곱하기 전에 모든 인수를 줄이고 음이 아닌 나머지로 답하는 것입니다. 나중 묶음들은 마지막 자리와 주기의 길이 문제로, 경시대회와 입시에 나오고 거듭제곱을 끝까지 계산하려는 사람을 벌주는 바로 그 문제들입니다.

세션이 짧고 문제들이 수학 연습을 위한 간격 반복에서 설명한 것처럼 일정한 간격을 두고 되돌아오기 때문에, 주기 찾기라는 한 수는 찾아보는 절차가 아니라 반사 신경이 됩니다. 대부분의 사람에게는 한 단원이 메워 줄 모듈러 연산의 공백이 있는 것이 아닙니다. 아무도 그려 주지 않은 그림 하나, 곧 트랙과, 한 번도 해 보지 않은 마흔 번쯤의 반복이 있을 뿐입니다.

핵심 요약

모듈러 연산은 눈금이 $n$개 있는 원형 트랙 위의 산수입니다. 나머지는 $a$걸음 걸은 뒤 멈춘 자리이고, 다 돈 바퀴는 잊히고, 두 수는 같은 눈금에 멈출 때 합동입니다. 바퀴는 합과 곱에 아무것도 기여하지 않으므로 더하거나 곱하기 전에 모든 수를 자기 나머지로 줄여도 되며, 이 한 가지 허락이 $7^{100}$의 마지막 자리처럼 불가능해 보이는 계산을 손으로 따라갈 수 있는 짧은 주기로 바꿉니다. 나누어떨어짐 판정법은 10의 거듭제곱을 9, 3, 11로 줄인 것입니다. 검사 숫자는 오타를 잡아내는 나머지입니다. 나눗셈은 그 수가 트랙과 인수를 공유하지 않을 때만 통하고, 소수 트랙이 특별한 이유가 이것입니다.

모듈러 문제가 막히면 트랙을 그리십시오. 각 조각이 어디에 멈추는지 묻고, 가면서 줄이고, 지수는 자기 트랙에 두십시오. 답은 $0$과 $n - 1$ 사이의 눈금이고, 공식보다 그림이 먼저 여러분을 거기로 데려다줄 것입니다.