페르마 소정리 (Fermat's Little Theorem)

정의

페르마 소정리 (Fermat’s Little Theorem, FLT) 는 소수 p 와 gcd(a, p) = 1 인 정수 a 에 대해 다음이 성립:

a^(p-1) ≡ 1 (mod p)

1640년 피에르 드 페르마가 발견, 1736년 오일러가 최초 증명.

동치 형태:

a^p ≡ a (mod p)      (gcd(a, p) = 1 불필요)

문제 상황과 동기

모듈러 역원 a^(-1) (mod p) 를 구하라. p = 10^9 + 7 은 소수.

• naive (a·x ≡ 1 을 x = 1..p-1 순회): O(p). p=10^9+7 이면 불가능.
• 확장 유클리드: O(log p). mod 소수 아니어도 범용.
• FLT + 분할 정복 거듭제곱: O(log p). p 가 소수일 때 가장 단순.

핵심 통찰: a·a^(p-2) ≡ a^(p-1) ≡ 1 (mod p). 따라서 inv(a) ≡ a^(p-2) (mod p).

시각화

핵심 아이디어

잉여계의 순열

Z_p = {0, 1, 2, …, p-1} 에서 0 을 제외한 집합 {1, 2, …, p-1} 에 a 를 곱하면:

{1·a, 2·a, 3·a, ..., (p-1)·a}

이는 {1, 2, …, p-1} 의 순열 (permutation). 왜? a 가 p 와 서로소이므로 a·x ≡ a·y → x ≡ y (mod p) (소거 가능).

정리 증명

1·2·3·...·(p-1) ≡ (1·a)·(2·a)·...·((p-1)·a) (mod p)
(p-1)! ≡ (p-1)! · a^(p-1) (mod p)

(p-1)! 은 p 와 서로소이므로 양변 소거:

1 ≡ a^(p-1) (mod p)

모듈러 역원

a·a^(p-2) ≡ a^(p-1) ≡ 1 (mod p)
∴ inv(a) = a^(p-2) mod p

알고리즘

// 분할 정복 거듭제곱 O(log p)
mod_pow(base, exp, mod):
    result = 1
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

// FLT 로 모듈러 역원
mod_inverse(a, p):    // p 는 소수
    return mod_pow(a, p - 2, p)

구현

// Fermat 소정리 + 분할 정복 거듭제곱
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
ll mod_pow(ll base, ll exp, ll mod) {
  ll result = 1;
  while (exp > 0) {
      if (exp & 1) result = (result * base) % mod;
      base = (base * base) % mod;
      exp >>= 1;
  }
  return result;
}
​
ll mod_inv(ll a, ll p) {
  return mod_pow(a, p - 2, p);  // FLT
}
​
int main() {
  ll a, p; cin >> a >> p;
  cout << a << "^(" << p << "-2) mod " << p << " = " << mod_inv(a, p) << "\n";
  cout << "verify: " << a << " * " << mod_inv(a, p) << " mod " << p << " = "
       << (a * mod_inv(a, p)) % p << "\n";
  return 0;
}

# pow(base, exp, mod) 내장 함수로 O(log exp)
import sys
input = sys.stdin.readline
​
def mod_inv(a: int, p: int) -> int:
  return pow(a, p - 2, p)   # FLT, p 는 소수
​
a, p = map(int, input().split())
inv = mod_inv(a, p)
print(f"inv({a}) mod {p} = {inv}")
print(f"verify: {a} * {inv} mod {p} = {a * inv % p}")

// 분할 정복 거듭제곱 + FLT
import java.util.*;
import java.io.*;
public class Main {
  static long modPow(long base, long exp, long mod) {
      long result = 1;
      while (exp > 0) {
          if ((exp & 1) == 1)
              result = (result * base) % mod;
          base = (base * base) % mod;
          exp >>= 1;
      }
      return result;
  }
  static long modInv(long a, long p) {
      return modPow(a, p - 2, p);  // FLT
  }
  public static void main(String[] args) throws IOException {
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(br.readLine());
      long a = Long.parseLong(st.nextToken());
      long p = Long.parseLong(st.nextToken());
      long inv = modInv(a, p);
      System.out.println("inv(" + a + ") mod " + p + " = " + inv);
      System.out.println("verify: " + a + " * " + inv + " mod " + p + " = " + (a * inv % p));
  }
}

3 1000000007

inv(3) mod 1000000007 = 333333336
verify: 3 * 333333336 mod 1000000007 = 1

복잡도

변형 / 활용

함정

1. p 가 소수가 아닌 경우

FLT 가 성립하지 않음. 예: 2^(10-1) = 512 ≡ 2 (mod 10) ≠ 1. 오일러 정리 a^(φ(n)) ≡ 1 사용.

2. a 가 p 의 배수인 경우

a mod p = 0 이면 a^(p-1) ≡ 0 (mod p). 동치 형태 a^p ≡ a (mod p) 는 항상 성립 (0^p = 0).

3. p = 2

a^(1) ≡ 1 (mod 2) 는 홀수 a 에서 성립. 짝수면 a^(1) ≡ 0. 동치 형 a^2 ≡ a 는 항상 참.

4. 조합 inverse 전처리

nCr 을 많이 구할 때: factorial[n], inv_factorial[n] = factorial[n]^(p-2) 로 전처리. O(N + log p).

BOJ 연습 문제

참고

• 오일러 피 함수
• 모듈러 역원
• 확장 유클리드
• 중국인의 나머지 정리
• 소수 판정