C++でフェルマーの小定理を検証する方法

フェルマーの小定理とは

フェルマーの小定理とは、p を素数としたとき、任意の整数 a に対して「a^p − a が p の倍数になる」という定理です。

これを剰余演算（mod）で表現すると、次のようになります。

a^p ≡ a (mod p)

さらに、a が p で割り切れない場合（a と p が互いに素である場合）は、両辺を a で割ることで次の形に変形できます。

a^p−1 ≡ 1 (mod p)

この記事で扱う問題

ここでは、2つの整数 a と p が与えられ、これらの値に対してフェルマーの小定理が実際に成り立つかどうかを検証します。具体的には、次のいずれかの式が成立するかを確認します。

• a^p ≡ a (mod p)
• a^p−1 ≡ 1 (mod p)　※a が p で割り切れない場合

具体例で理解しよう

入力： a = 3, p = 11

出力： True（定理は成立）

解説：

a^p−1 ≡ 1 (mod p) が成り立つかを順に確認していきます。

• 3¹⁰ = 59049
• 59049 − 1 = 59048
• 59048 ÷ 11 = 5368 → 割り切れるため、定理は成立

C++による実装例

以下は、与えられた a と p に対してフェルマーの小定理が成立するかを判定するプログラムです。

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

int fermatLittle(int a, int p) {
    int powVal;
    if(a % p == 0){
        // a が p で割り切れる場合は a^p ≡ a (mod p) を確認
        powVal = pow(a, p);
        if((powVal - a) % p == 0){
            cout<<"フェルマーの小定理は成立します！";
        }
        else{
            cout<<"フェルマーの小定理は成立しません！";
        }
    }
    else {
        // a が p で割り切れない場合は a^(p-1) ≡ 1 (mod p) を確認
        powVal = pow(a, (p - 1));
        if((powVal - 1) % p == 0){
            cout<<"フェルマーの小定理は成立します！";
        }
        else{
            cout<<"フェルマーの小定理は成立しません！";
        }
    }
}

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

実行結果

フェルマーの小定理は成立します！

実装時の注意点

上記のコードでは説明のため pow() 関数を直接使用していますが、pow() は戻り値が浮動小数点型（double）であり、指数が大きくなるとオーバーフローや精度誤差が発生する可能性があります。

実際の競技プログラミングや暗号処理などでは、「繰り返し二乗法（高速べき乗）」を使って各乗算のたびに mod を取ることで、大きな数でも正確かつ効率的に計算するのが一般的です。