C++ में फर्मेट का लघु प्रमेय

फर्मेट का लघु प्रमेय -

यह प्रमेय बताता है कि किसी भी अभाज्य संख्या 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

आउटपुट: 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!