ทฤษฎีบทเฟอร์ม่าเล็ก (Fermat's Little Theorem) ใน C++

ทฤษฎีบทเฟอร์ม่าเล็ก

สำหรับจำนวนเฉพาะ p และจำนวนเต็ม a:

• a^p ≡ a (mod p)
• ถ้า a ไม่หาร p ลงตัว: a^(p-1) ≡ 1 (mod p)

โจทย์

ได้รับ a และ p ตรวจสอบว่าทฤษฎีบทเป็นจริงหรือไม่

ตัวอย่าง

Input: a = 3, p = 7

Output: True

อธิบาย: 3^6 = 729, 729 - 1 = 728, 728 / 7 = 104 (ลงตัว)

โปรแกรมตัวอย่าง

#include <iostream>
#include <cmath>
using namespace std;

void fermatLittle(int a, int p) {
    long long powVal;
    if (a % p == 0) {
        powVal = pow(a, p);
        if ((powVal - a) % p == 0) cout << "Fermat's little theorem holds true!";
        else cout << "Fermat's little theorem holds false!";
    } else {
        powVal = pow(a, p - 1);
        if ((powVal - 1) % p == 0) cout << "Fermat's little theorem holds true!";
        else cout << "Fermat's little theorem holds false!";
    }
}

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

ผลลัพธ์

Fermat's little theorem holds true!