ফার্মাটের ছোট্ট উপপাদ্যটি প্রাথমিক সংখ্যা তত্ত্বের মৌলিক ফলাফলগুলির মধ্যে একটি এবং এটি ফার্মাট প্রাথমিক পরীক্ষার ভিত্তি। উপপাদ্যটির নামকরণ করা হয়েছে পিয়েরে ডি ফার্মাটের নামে, যিনি এটি 1640 সালে বলেছিলেন। উপপাদ্যটি বলে যে যদি p একটি মৌলিক সংখ্যা হয়, তবে যেকোন পূর্ণসংখ্যা a এর জন্য, a p–a সংখ্যাটি p এর একটি পূর্ণসংখ্যা গুণিতক।
অ্যালগরিদম
Begin Function power() is used to compute a raised to power b under modulo M function modInverse() to find modular inverse of a under modulo m : Let m is prime If a and m are relatively prime, then modulo inverse is a^(m - 2) mod m End
উদাহরণ কোড
#include <iostream>
using namespace std;
int pow(int a, int b, int M) {
int x = 1, y = a;
while (b > 0) {
if (b % 2 == 1) {
x = (x * y);
if (x > M)
x %= M;
}
y = (y * y);
if (y > M)
y %= M;
b /= 2;
}
return x;
}
int modInverse(int a, int m) {
return pow(a, m - 2, m);
}
int main() {
int a, m;
cout<<"Enter number to find modular multiplicative inverse: ";
cin>>a;
cout<<"Enter Modular Value: ";
cin>>m;
cout<<modInverse(a, m)<<endl;
} আউটপুট
Enter number to find modular multiplicative inverse: 26 Enter Modular Value: 7 3
