정수론 (Number Theory)

정의

정수론 (Number Theory) 은 정수의 성질과 관계를 연구하는 분야. PS 에서는 약수/배수, 소수 (prime), 모듈러 연산, 유클리드 호제법, 확장 유클리드, 페르마/오일러 정리, 중국인의 나머지 정리 등이 핵심. 수천 년 역사, 그리스 시대 유클리드부터 근대 암호학까지.

문제 상황과 동기

정수의 구조적 성질 (나누어떨어짐, 소인수분해, 모듈러 역원) 을 빠르게 계산해야 한다.

• naive: 모든 약수 나열 O(N), 소수 판정 O(√N) 시행착오.
• 정수론 도구: GCD O(log N), 모듈러 역원 O(log MOD), 소수 판정 Miller-Rabin O(k log^3 N).

핵심 통찰: “곱셈과 나눗셈은 모듈러 세계에서 닫혀 있고, 역원이 존재하면 나눗셈 = 곱셈”. 암호학 (RSA, Diffie-Hellman), 해시 함수, 조합론 (nCr mod p), DP 등에 필수.

시각화

핵심 아이디어

1. GCD (최대공약수)

유클리드 호제법: gcd(a, b) = gcd(b, a mod b), base gcd(a, 0) = a. O(log min(a, b)).

gcd(48, 18) → gcd(18, 12) → gcd(12, 6) → gcd(6, 0) → 6

2. 확장 유클리드

ax + by = gcd(a, b) 의 정수해 (x, y) 를 구함. 모듈러 역원 계산에 핵심.

gcd(35, 15) = 5
35 · 1 + 15 · (-2) = 5

3. 모듈러 역원

a · a^(-1) ≡ 1 (mod M) 인 a^(-1). gcd(a, M) = 1 일 때만 존재.

• 확장 유클리드: O(log M)
• 페르마 소정리 (M 소수): a^(-1) ≡ a^(M-2) (mod M), 거듭제곱 O(log M)

4. 중국인의 나머지 정리 (CRT)

x ≡ a_1 (mod m_1), x ≡ a_2 (mod m_2) 를 만족하는 x. m_i 서로소 시 유일해 존재 (mod M = Π m_i).

5. 오일러 φ 함수

φ(n) = n 이하 n 과 서로소인 수의 개수. φ(p^k) = p^k - p^(k-1). 오일러 정리: a^φ(n) ≡ 1 (mod n) (gcd(a,n)=1).

알고리즘

gcd(a, b):
    while b ≠ 0:
        a, b = b, a mod b
    return a

extended_gcd(a, b):
    if b == 0:
        return (a, 1, 0)
    (g, x1, y1) = extended_gcd(b, a mod b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

mod_inverse(a, m):
    (g, x, _) = extended_gcd(a, m)
    if g ≠ 1:
        return None   # 역원 없음
    return (x % m + m) % m

fast_power(a, b, m):
    res = 1
    a = a mod m
    while b > 0:
        if b odd:
            res = (res * a) mod m
        a = (a * a) mod m
        b = b // 2
    return res

구현

// GCD, 확장 유클리드, 모듈러 역원, 거듭제곱
#include <bits/stdc++.h>
using namespace std;
​
long long gcd(long long a, long long b) {
  while (b) { long long t = b; b = a % b; a = t; }
  return a;
}
​
tuple<long long, long long, long long> extgcd(long long a, long long b) {
  if (b == 0) return {a, 1, 0};
  auto [g, x1, y1] = extgcd(b, a % b);
  return {g, y1, x1 - (a / b) * y1};
}
​
long long modinv(long long a, long long m) {
  auto [g, x, y] = extgcd(a, m);
  if (g != 1) return -1;   // 역원 없음
  return (x % m + m) % m;
}
​
long long power(long long a, long long b, long long m) {
  long long res = 1;
  a %= m;
  while (b > 0) {
      if (b & 1) res = res * a % m;
      a = a * a % m;
      b >>= 1;
  }
  return res;
}
​
int main() {
  long long a, b, m;
  cin >> a >> b >> m;
  cout << "gcd(" << a << ", " << b << ") = " << gcd(a, b) << "\n";
  cout << a << "^" << b << " mod " << m << " = " << power(a, b, m) << "\n";
  long long inv = modinv(a, m);
  if (inv == -1) cout << a << " has no inverse mod " << m << "\n";
  else cout << a << "^(-1) mod " << m << " = " << inv << "\n";
}

# GCD, 확장 유클리드, 모듈러 역원, 거듭제곱
import math
​
def gcd(a, b):
  while b:
      a, b = b, a % b
  return a
​
def extgcd(a, b):
  if b == 0:
      return a, 1, 0
  g, x1, y1 = extgcd(b, a % b)
  return g, y1, x1 - (a // b) * y1
​
def modinv(a, m):
  g, x, _ = extgcd(a, m)
  if g != 1:
      return None
  return (x % m + m) % m
​
def power(a, b, m):
  res = 1
  a %= m
  while b > 0:
      if b & 1:
          res = res * a % m
      a = a * a % m
      b >>= 1
  return res
​
a, b, m = map(int, input().split())
print(f"gcd({a}, {b}) = {gcd(a, b)}")
print(f"{a}^{b} mod {m} = {power(a, b, m)}")
inv = modinv(a, m)
if inv is None:
  print(f"{a} has no inverse mod {m}")
else:
  print(f"{a}^(-1) mod {m} = {inv}")

// GCD, 확장 유클리드, 모듈러 역원, 거듭제곱
import java.util.*;
public class Main {
  static long gcd(long a, long b) {
      while (b != 0) { long t = b; b = a % b; a = t; }
      return a;
  }
  static long[] extgcd(long a, long b) {
      if (b == 0) return new long[]{a, 1, 0};
      long[] res = extgcd(b, a % b);
      long g = res[0], x1 = res[1], y1 = res[2];
      return new long[]{g, y1, x1 - (a / b) * y1};
  }
  static long modinv(long a, long m) {
      long[] res = extgcd(a, m);
      if (res[0] != 1) return -1;
      return (res[1] % m + m) % m;
  }
  static long power(long a, long b, long m) {
      long res = 1;
      a %= m;
      while (b > 0) {
          if ((b & 1) == 1) res = res * a % m;
          a = a * a % m;
          b >>= 1;
      }
      return res;
  }
  public static void main(String[] args) {
      Scanner sc = new Scanner(System.in);
      long a = sc.nextLong(), b = sc.nextLong(), m = sc.nextLong();
      System.out.println("gcd(" + a + ", " + b + ") = " + gcd(a, b));
      System.out.println(a + "^" + b + " mod " + m + " = " + power(a, b, m));
      long inv = modinv(a, m);
      if (inv == -1) System.out.println(a + " has no inverse mod " + m);
      else System.out.println(a + "^(-1) mod " + m + " = " + inv);
  }
}

35 15 1000000007

gcd(35, 15) = 5
35^15 mod 1000000007 = 590436101
35^(-1) mod 1000000007 = 142857145

10 3 100

gcd(10, 3) = 1
10^3 mod 100 = 0
10 has no inverse mod 100

복잡도

변형 / 활용

1. 조합론 (nCr mod p)

nCr = n! / (r! (n-r)!) 를 mod p 로. factorial 미리 계산 + 모듈러 역원 → O(N + log p).

2. 이산 로그 (Discrete Log)

a^x ≡ b (mod m) 의 x 를 구함. Baby-step Giant-step O(√m).

3. RSA 암호

공개키 (e, N), 개인키 (d, N). c ≡ m^e (mod N), m ≡ c^d (mod N). 오일러 정리 기반.

4. Pollard rho

정수 N 의 소인수를 O(N^(1/4)) 에 찾는 확률적 알고리즘.

함정

1. 모듈러 역원 존재 조건

gcd(a, M) ≠ 1 이면 역원 없음. 확인 없이 나누기 쓰면 런타임 에러.

2. 페르마 소정리 조건

M 이 소수일 때만. 합성수면 오일러 정리 (a^φ(M)) 써야.

3. overflow

a * b mod M 계산 시 a, b < M 이어도 a*b 가 long long overflow. (__int128)a * b % M 또는 modmul.

4. 음수 mod

-5 % 3 가 C++ 에서 -2. (x % M + M) % M 로 양수 보장.

BOJ 연습 문제

참고

• 에라토스테네스의 체
• 모듈러 연산
• 중국인의 나머지 정리
• 밀러-라빈 소수 판정