Fermat's Little Theorem

페르마의 소정리

소수와 관련된 정수론의 아주 중요한 정리 중 하나이다. 주로 소수 판별이나 거대한 수의 나머지 연산(Modular Arithmetic)에서 나눗셈을 처리할 때 핵심적인 역할을 한다.

정의는 다음과 같다.

$p$가 소수이고 $a$가 $p$의 배수가 아닌 정수일 때, 아래 식이 성립한다.

\[a^{p-1} \equiv 1 \pmod{p}\]

또한, $a$가 $p$의 배수인 경우까지 포함하여 일반화하면 아래와 같이 쓸 수 있다.

\[a^p \equiv a \pmod{p}\]

이 정리는 어떤 수가 소수일 때 반드시 만족해야 하는 성질을 제시하므로, 이를 역으로 이용하면 소수 판별 알고리즘의 근거가 된다.

알고리즘 활용 방안

1. 소수 판별 (소수판별법 :: 밀러-라빈 알고리즘)

앞서 언급된 밀러-라빈 소수판별법이 이 정리를 바탕으로 한다. 어떤 수 $n$이 소수라면 임의의 $a$에 대해 $a^{n-1} \equiv 1 \pmod{n}$이 성립해야 한다는 점을 이용하여, 이 식이 성립하지 않는 $a$를 하나라도 찾는다면 $n$은 확실히 합성수라고 단정 지을 수 있다.

2. 모듈러 역원 (Modular Multiplicative Inverse)

알고리즘 문제를 풀다 보면 아주 큰 수에 대해 $nCr \pmod{P}$ 같은 값을 구해야 할 때가 있다. 이때 나눗셈 연산은 모듈러 연산에서 직접 수행할 수 없으므로 역원을 곱해주는 방식으로 해결해야 한다.

페르마의 소정리에 따르면 $a^{p-1} \equiv 1 \pmod{p}$이다. 양변을 $a$로 나누면 다음과 같다.

\[a^{p-2} \equiv a^{-1} \pmod{p}\]

즉, $p$가 소수일 때 $a$로 나누는 연산은 $a^{p-2}$를 곱하는 연산과 동일한 결과를 가진다. 이는 분할 정복을 이용한 거듭제곱 알고리즘을 통해 $O(\log p)$ 시간 안에 계산할 수 있다.

구현 방법

페르마의 소정리를 활용하기 위해서는 거대한 지수승을 빠르게 계산하는 함수가 필수적이다.

분할 정복을 이용한 거듭제곱

지수를 절반씩 나누어 계산함으로써 $O(\log N)$의 시간 복잡도로 결과를 낼 수 있다.

typedef long long ll;

ll power(ll a, ll b, ll m) {
    ll res = 1;
    a %= m;
    while (b > 0) {
        if (b % 2 == 1) {
            res = (res * a) % m;
        }
        a = (a * a) % m;
        b /= 2;
    }
    return res;
}

nCr mod P 계산 예시

조합 공식 $nCr = \frac{n!}{r!(n-r)!}$에서 분모 부분을 페르마의 소정리로 역원 처리하여 계산하는 방식이다.

• $n! \pmod{p}$를 구한다
• $r!(n-r)! \pmod{p}$를 구한 뒤, 이 값의 $p-2$승을 구한다
• 두 값을 곱하고 다시 $p$로 나머지 연산을 한다

주의사항

• $p$는 반드시 소수여야 한다. 만약 $p$가 소수가 아니라면 페르마의 소정리 대신 오일러 정리(Euler’s Theorem)를 사용해야 한다
• $a$와 $p$는 서로소여야 한다 ($a$가 $p$의 배수가 아니어야 함)
• 지수승 계산 시 long long 범위를 초과할 수 있으므로 매 곱셈마다 모듈러 연산을 적용해야 한다