फर्मेट का लिटिल थ्योरम एलिमेंट्री नंबर थ्योरी के मौलिक परिणामों में से एक है और फर्मेट प्राइमैलिटी टेस्ट का आधार है। थ्योरम का नाम पियरे डी फर्मेट के नाम पर रखा गया है, जिन्होंने इसे 1640 में बताया था। थ्योरम कहता है कि यदि p एक अभाज्य संख्या है, तो किसी भी पूर्णांक a के लिए, संख्या a^p - a, p का एक पूर्णांक गुणक है।
एल्गोरिदम
Begin
फंक्शन power() का उपयोग a को मॉड्यूलो M के तहत पावर b तक बढ़ाने के लिए किया जाता है
फंक्शन modInverse() का उपयोग मॉड्यूलो m के तहत a के मॉड्यूलर इनवर्स को ढूंढने के लिए:
मान लें m अभाज्य है
यदि a और m अपेक्षाकृत अभाज्य हैं, तो
मॉड्यूलो इनवर्स 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
