C++-এ ফারম্যাটের ছোট উপপাদ্য (Fermat's Little Theorem)

ফারম্যাটের ছোট উপপাদ্য (Fermat's Little Theorem) -

এই উপপাদ্য বলে যে যেকোনো প্রাইম নম্বর p এর জন্য,

          A^p - p হলো p-এর একটি গুণিতক (multiple)।

এই স্টেটমেন্টটি মডুলার অ্যারিথমেটিক-এ নিচের तरह প্রকাশ করা হয়:

          a^p ≡ a (mod p)

যদি a p দ্বারা ভাগযোগ্য না হয়, তবে:

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

উপপাদ্য কাজ করছে কিনা তা যাচাই করার প্রোগ্রাম:

#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;
}

আউটপুট

Fermat's little theorem holds true!