Định lý nhỏ Fermat trong C++

Định lý nhỏ Fermat: Với số nguyên tố p, a^p - a là bội của p.

Dạng modulo: a^p ≡ a (mod p).

Nếu a không chia hết cho p: a^(p-1) ≡ 1 (mod p).

Bài toán: Cho a, p. Kiểm tra định lý có đúng không.

Ví dụ:

Đầu vào: a = 3, p = 7

Đầu ra: True

Giải thích: 3^6 = 729. 729-1=728. 728/7=104.

Chương trình minh họa

Ví dụ

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

int fermatLittle(int a, int p) {
    int powVal;
    if (a % p == 0) {
        powVal = pow(a, p);
        if ((powVal - p) % 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;
}

Kết quả

Fermat's little theorem holds true!