C++로 검증하는 페르마의 소정리(Fermat's Little Theorem)

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

페르마의 소정리는 수론의 기초를 이루는 핵심 정리로, 소수 판별이나 모듈러 역원 계산 같은 다양한 알고리즘의 이론적 기반이 됩니다. 이 정리는 다음과 같이 정의됩니다.

p가 소수일 때, 임의의 정수 a에 대하여 a^p − a 는 p의 배수이다.

이를 모듈러 산술(modular arithmetic)로 표현하면 다음과 같습니다.

a^p ≡ a (mod p)

만약 a가 p로 나누어 떨어지지 않는다면(a와 p가 서로소인 경우), 양변을 a로 나누어 아래 형태로 나타낼 수 있습니다.

a^p−1 ≡ 1 (mod p)

문제: 페르마의 소정리 검증하기

두 수 a와 p가 주어졌을 때, 주어진 값에 대해 페르마의 소정리가 실제로 성립하는지 확인하는 것이 이번 문제의 목표입니다. 즉, 다음 두 조건 중 하나가 참인지 검사하면 됩니다.

• a^p ≡ a (mod p)
• a^p−1 ≡ 1 (mod p) (단, a가 p로 나누어 떨어지지 않는 경우)

입력 예시로 이해하기

입력: a = 3, p = 7

출력: True (성립)

풀이 과정:

a^p−1 ≡ 1 (mod p) 인지 확인합니다.

=> 3⁶ = 729

=> 729 − 1 = 728

=> 728 ÷ 7 = 104 (나누어 떨어짐)

3⁶ − 1이 7로 나누어 떨어지므로, a = 3, p = 7일 때 페르마의 소정리가 성립함을 알 수 있습니다.

C++ 구현 예제

#include <iostream>
#include <math.h>
using namespace std;

void fermatLittle(int a, int p) {
    long long powVal;

    if (a % p == 0) {
        // a가 p로 나누어 떨어지는 경우: a^p ≡ a (mod p) 검증
        powVal = (long long)pow(a, p);
        if ((powVal - a) % p == 0) {
            cout << "페르마의 소정리가 성립합니다!" << endl;
        } else {
            cout << "페르마의 소정리가 성립하지 않습니다!" << endl;
        }
    } else {
        // a가 p로 나누어 떨어지지 않는 경우: a^(p-1) ≡ 1 (mod p) 검증
        powVal = (long long)pow(a, p - 1);
        if ((powVal - 1) % p == 0) {
            cout << "페르마의 소정리가 성립합니다!" << endl;
        } else {
            cout << "페르마의 소정리가 성립하지 않습니다!" << endl;
        }
    }
}

int main() {
    int a = 3, m = 11;
    fermatLittle(a, m);
    return 0;
}

실행 결과

페르마의 소정리가 성립합니다!

구현 시 주의할 점

위 코드는 개념 이해를 돕기 위한 예제입니다. pow() 함수는 부동소수점 값을 반환하기 때문에 지수가 커지면 오버플로나 정밀도 손실이 발생할 수 있습니다. 따라서 실제 코딩 테스트나 큰 수를 다룰 때는 거듭제곱을 매 단계마다 모듈러 연산하는 모듈러 거듭제곱(modular exponentiation) 기법을 사용하는 것이 안전합니다.