Маленькая теорема Ферма

В этой статье я представлю Маленькую теорему Ферма и простую алгоритмическую задачу, в которой эта теорема может быть применена.

Маленькая теорема Ферма утверждает, что если p — простое число, то для всех действительных целых чисел a (aᵖ-a) является целым числом, кратным п. Это представлено в следующей модульной арифметической нотации.

Если p не является простым числом, но удовлетворяет приведенному выше уравнению для всех действительных целых чисел a, то это число называется числом Кармайкла. Некоторые числа Кармайкла: 561, 1105, 1729, 2465, 2821…

Доказательство малой теоремы Ферма

Я докажу малую теорему Ферма, используя математическую индукцию.

Применение в соревновательном программировании

Это — задача, требующая использования Малой теоремы Ферма. Любой, кто успешно закончил математику в средней школе, должен понять, что ответ на задачу является результатом следующего выражения (по модулю 1e9 + 7).

Во-первых, (2ⁿ - 1) можно вычислить за O(log n) с помощью двоичного возведения в степень. Затем можно использовать малую теорему Ферма для вычисления биномиальных коэффициентов.

Поскольку 1e9+7 — простое число, модуль биномиального коэффициента равен следующему.

Тот же метод можно использовать для расчета второго биномиального коэффициента. Ниже приведен мой код решения.

#include <iostream>
#include <algorithm>
using namespace std;
#define MOD 1000000007
#define ll long long

ll fermat(int N, int R) {
    ll ret=1;
    for (int i=0; i<R; i++) {
        ret*=N-i;
        ret%=MOD;
    }
    ll R_fac=1;
    for (int i=1; i<=R; i++) {
        R_fac*=i;
        R_fac%=MOD;
    }
    // calculating R_fac^(1e9+7-2)
    ll temp=1, exponent=MOD-2; 
    while (exponent) {
        if (exponent%2) {
            temp*=R_fac;
            temp%=MOD;
        }
        R_fac*=R_fac;
        R_fac%=MOD;
        exponent/=2;
    }
    return (ret*temp)%MOD;
}

int main()
{
    ll n, a, b; cin >> n >> a >> b;
    // calculating 2^n - 1
    ll exponent=n, ans=1, temp=2; 
    while (exponent) {
        if (exponent%2) {
            ans*=temp;
            ans%=MOD;
        }
        temp*=temp;
        temp%=MOD;
        exponent/=2;
    }
    
    ans=(ans-1+MOD)%MOD;
    ans=(ans-fermat(n, a)+MOD)%MOD;
    ans=(ans-fermat(n, b)+MOD)%MOD;

    cout << (ans+MOD)%MOD;
}

Другие проблемы, связанные с Малой теоремой Ферма:

Рекомендации

Лонг, CL (1965). Элементарное введение в теорию чисел. http://ci.nii.ac.jp/ncid/BA00965634

Сингх, Н. (2022, 21 августа). Маленькая теорема Ферма. Гикс для гиков. https://www.geeksforgeeks.org/fermats-little-theorem/