배경
프로젝트 오일러를 풀다 보면 이런 조건이 자주 붙는다.
답을 1,000,000,007로 나눈 나머지를 구하시오.
처음엔 그냥 "크니까 나누는 거겠지" 하고 넘겼다.
근데 Window into a Matrix (743번) 문제를 풀다가,
수식을 유도했더니 큰 수 / 큰 수 꼴이 나왔다.
이걸 modular 연산하려면 단순히 나눠서는 안 된다는 걸 알고 있었다.
모듈러 곱셈 역원을 써야 한다는 것도 알았다.
근데 왜 되는지를 몰랐다.
원리를 모르는 채로 쓰는 게 이상하게 느껴져서, ChatGPT랑 티키타카하면서 제대로 파고들었다.
왜 결과값을 작게 유지해야 하나
modular 연산 조건이 붙는 이유는 단순하다.
수식을 그대로 계산하면 결과값이 천문학적으로 커진다.
프로그래밍에서 숫자가 커질수록 연산 속도는 기하급수적으로 느려지고,
BigInteger 같은 자료구조로 실제 값을 계산하다간 시간 초과가 난다.
그래서 중간 중간 modular 연산을 해서 값을 항상 작게 유지하는 것이 핵심이다.
더하기, 빼기, 곱셈은 왜 중간에 mod 해도 괜찮나
더하기부터 보자.
(a + b) mod m = ((a mod m) + (b mod m)) mod m증명은 간단하다.
a = q_a·m + r_a, b = q_b·m + r_b 라 쓰면:
a + b = (q_a + q_b)·m + (r_a + r_b)m으로 나누면 나머지는 (r_a + r_b) mod m 이고,
r_a = a mod m, r_b = b mod m 이므로 성립한다.
곱셈도 동일한 원리다.
(a × b) mod m = ((a mod m) × (b mod m)) mod ma = q_a·m + r_a 를 대입하면:
a × b = (q_a·m + r_a) × b = q_a·m·b + r_a·bm으로 나누면 나머지는 r_a·b mod m = (a mod m)(b mod m) mod m.
빼기는 조심해야 한다. 중간에 음수가 나올 수 있어서다.
(a - b) mod m이걸 그냥 계산하면 음수가 될 수 있고, 언어마다 음수 mod 결과가 다르다.
그래서 이렇게 바꿔준다:
(a - b) mod m = (a + (m - b)) mod mm - b를 더해주는 방식으로 빼기를 더하기로 변환하는 트릭이다.
m - b는 항상 양수이므로 안전하다.
그럼 나눗셈은?
나눗셈은 위 방식이 통하지 않는다.
(a / b) mod m ≠ (a mod m) / (b mod m)반례: a=10, b=2, m=6
- 좌변: (10/2) mod 6 = 5 mod 6 = 5
- 우변: (10 mod 6) / (2 mod 6) = 4/2 = 2
- 5 ≠ 2
그래서 나눗셈을 곱셈으로 바꾸는 방법이 필요하다.
모듈러 곱셈 역원
일반적인 수에서는 나눗셈을 이렇게 표현한다:
a / b = a × (1/b)modular 세계에서도 똑같은 아이디어를 쓴다.
역원(inverse) 이란, 어떤 수와 곱했을 때 1이 되는 수다.
b × x ≡ 1 (mod m)이 x를 b의 모듈러 곱셈 역원이라 부른다.
이걸 구하면 나눗셈을 곱셈으로 바꿀 수 있다:
a / b ≡ a × x (mod m)예시로 확인해보자
m = 7, b = 2, a = 10이라 하자.
먼저 정답을 확인한다:
10 / 2 = 5 → 5 mod 7 = 5이제 2의 역원을 구한다.
2 × x ≡ 1 (mod 7)x = 4를 대입하면: 2 × 4 = 8 = 7 + 1 ≡ 1 (mod 7) ✓
역원 적용:
10 × 4 = 40 = 35 + 5 ≡ 5 (mod 7) ✓정확히 같은 결과가 나온다.
주의할 점 - 역원이 존재하는 조건
b와 m이 서로소(gcd(b, m) = 1) 여야 역원이 존재한다.
gcd(b, m) ≠ 1이면 b × x ≡ 1 (mod m)을 만족하는 정수 x가 없다.
프로젝트 오일러 문제들이 modular 값으로 1,000,000,007 (소수) 를 쓰는 이유가 여기 있다.
소수 p에 대해 1 이상 p 미만의 모든 정수는 p와 서로소이므로, 역원이 항상 존재한다.
배운 것
사실 모듈러 역원이라는 개념 자체는 알고리즘 문제를 풀면서 이미 쓰고 있었다.
근데 왜 되는지를 모른 채로 쓰는 게 어느 순간부터 불편해졌다.
피타고라스 삼중수 정리를 직접 증명해봤을 때랑 똑같은 느낌이었다.
공식을 외우는 것과 공식이 왜 성립하는지 이해하는 것은 완전히 다른 경험이다.
수학이 재밌어진 건 문제를 푸는 것보다 원리를 이해할 때 오는 그 감각 때문인 것 같다.
꿀잼!
