Định lý nhỏ Fermat trong C ++

Định lý nhỏ của Fermat -

Định lý này phát biểu rằng với bất kỳ số nguyên tố p nào,

A ^p - p là bội số của p.

Tuyên bố này trong số học mô-đun được biểu thị là,

a ^p ≡ a (mod p)

Nếu a không chia hết cho p thì

a ^{p - 1} ≡ 1 (mod p)

Trong bài toán này, chúng ta được cho hai số a và p. Nhiệm vụ của chúng tôi là xác minh định lý nhỏ của fermat trên các giá trị này.

Chúng tôi cần kiểm tra xem a ^p ≡ a (mod p) hoặc a ^{p - 1} ≡ 1 (mod p)

Giữ đúng cho các giá trị đã cho của a và p.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào: a =3, p =7

Đầu ra: Đúng

Giải thích:

A ^p-1 ≡ 1 (mod p)

=> 3 ⁶ ≡ 729

=> 729 - 1 =728

=> 728/7 =104

Chương trình minh họa hoạt động của định lý,

Ví dụ

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

Đầu ra -

Fermat's little theorem holds true!