ফার্মাটের ছোট্ট উপপাদ্য -
এই উপপাদ্যটি বলে যে কোনো মৌলিক সংখ্যা p,
এর জন্যA p - p p.
এর একটি গুণিতকএই বিবৃতিটি মডুলার পাটিগণিত -এ হিসাবে চিহ্নিত করা হয়,
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
আউটপুট: সত্য
ব্যাখ্যা:
A p-1 ≡ 1 (mod p)
=> 3 6 ≡ 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!
