개념

정수론은 정수의 성질, 특히 나눗셈과 나머지를 다루는 수학 분야입니다. 알고리즘 문제와 실무 코드에서 정수론이 등장하는 곳은 생각보다 많습니다. 두 주기가 다시 겹치는 시점을 구할 때, 아주 큰 경우의 수를 10^9 + 7로 나눈 나머지로 답할 때, 소수 목록이 필요할 때, 그리고 RSA 같은 공개 키 암호를 이해할 때가 대표적입니다. 이 장에서는 이후 장에서 계속 쓰는 용어와 직관을 정리합니다.

나누어떨어짐과 소수

정수 a가 b로 나누어떨어지면(나머지가 0이면) b를 a의 약수, a를 b의 배수라고 합니다. 1보다 크고 약수가 1과 자기 자신뿐인 정수를 소수(prime), 그렇지 않은 1보다 큰 정수를 합성수라고 합니다. 2, 3, 5, 7, 11은 소수이고 12 = 2 × 2 × 3은 합성수입니다.

산술의 기본 정리에 따르면 1보다 큰 모든 정수는 소수들의 곱으로 나타낼 수 있고, 곱하는 순서를 무시하면 그 방법은 한 가지뿐입니다. 이것이 소인수분해입니다. 예를 들어 360 = 2^3 × 3^2 × 5입니다. 소인수분해를 알면 약수의 개수, 최대공약수, 최소공배수를 모두 지수 비교로 구할 수 있습니다.

최대공약수와 최소공배수

최대공약수(GCD)는 두 수를 동시에 나누는 가장 큰 수이고, 최소공배수(LCM)는 두 수의 공통 배수 중 가장 작은 양수입니다. 둘 사이에는 gcd(a, b) × lcm(a, b) = a × b(a, b가 양수일 때)라는 관계가 있어서 GCD만 빠르게 구하면 LCM도 따라옵니다.

GCD를 구하는 표준 방법은 유클리드 호제법입니다. 핵심 성질은 gcd(a, b) = gcd(b, a mod b)이고, 나머지가 0이 되면 그때의 나누는 수가 답입니다. 확장 유클리드 호제법은 여기에 더해 a × x + b × y = gcd(a, b)를 만족하는 정수 x, y(베주 계수)도 함께 구합니다. 이 계수가 모듈러 역원을 구하는 열쇠가 됩니다.

import math

print(math.gcd(84, 36))   # 12
print(math.lcm(84, 36))   # 252 (Python 3.9 이상)
print(84 * 36 // math.gcd(84, 36))  # 252, 같은 값

모듈러 연산

a mod m은 a를 m으로 나눈 나머지입니다. 두 수 a, b를 m으로 나눈 나머지가 같으면 "a와 b는 법 m에 대해 합동"이라고 하고 a ≡ b (mod m)로 씁니다. 시계가 대표적인 예입니다. 10시에서 5시간 뒤는 15시가 아니라 3시이고, 이는 15 ≡ 3 (mod 12)입니다.

모듈러 연산이 유용한 이유는 덧셈, 뺄셈, 곱셈이 나머지를 유지하기 때문입니다.

• (a + b) mod m = ((a mod m) + (b mod m)) mod m
• (a - b) mod m = ((a mod m) - (b mod m) + m) mod m
• (a × b) mod m = ((a mod m) × (b mod m)) mod m

그래서 중간 결과가 아무리 커져도 매 단계마다 나머지를 취하면 숫자를 작게 유지할 수 있습니다. 단, 나눗셈은 그대로 성립하지 않습니다. a / b를 모듈러로 계산하려면 b의 모듈러 역원을 곱해야 합니다.

MOD = 10**9 + 7

a, b = 123456789, 987654321
print((a * b) % MOD)                  # 259106859
print(((a % MOD) * (b % MOD)) % MOD)  # 같은 값
print(-7 % 3)                         # 2 — Python은 결과를 항상 0 이상으로 맞춥니다

모듈러 역원과 페르마의 소정리

a × x ≡ 1 (mod m)을 만족하는 x를 a의 모듈러 역원이라고 합니다. 역원은 gcd(a, m) = 1(서로소)일 때만 존재합니다. 구하는 방법은 두 가지입니다.

• 확장 유클리드 호제법으로 a × x + m × y = 1을 풀면 x가 역원입니다. m이 소수가 아니어도 됩니다.
• m이 소수 p이면 페르마의 소정리 a^(p-1) ≡ 1 (mod p)에서 a^(p-2)가 역원입니다. 빠른 거듭제곱으로 계산합니다.

경쟁 프로그래밍에서 10^9 + 7과 998244353을 자주 쓰는 이유가 여기에 있습니다. 둘 다 소수라서 0이 아닌 모든 수에 역원이 있고, 값이 2^30 근처라서 두 수의 곱이 64비트 정수에 들어갑니다.

p = 10**9 + 7
inv3 = pow(3, p - 2, p)         # 페르마의 소정리
print(3 * inv3 % p)             # 1
print(pow(3, -1, p) == inv3)    # True — Python 3.8 이상의 내장 기능

용어 정리

언제 정수론을 떠올릴까

• 문제에 "나머지를 출력하라", "10^9 + 7로 나눈 값"이 나올 때
• 주기, 반복, 동시에 일어나는 사건이 나올 때(LCM)
• 같은 크기로 나누기, 비율 약분이 나올 때(GCD)
• 소수 판정이나 소수 개수가 범위 안에서 여러 번 필요할 때(체)
• 경우의 수가 커서 정확한 값 대신 나머지를 요구할 때(nCr mod p)

정리

정수론의 핵심 도구는 다섯 가지입니다. 유클리드 호제법(GCD · LCM), 모듈러 연산의 성질, 모듈러 역원(확장 유클리드 · 페르마), 빠른 거듭제곱, 에라토스테네스의 체입니다. 다음 장에서는 이 도구들이 작은 예제에서 실제로 어떻게 움직이는지 한 단계씩 따라가 봅니다.