C++でのフェルマーの小定理

フェルマーの小定理-

この定理は、任意の素数pについて、

A ^p --p pの倍数です。

モジュラー演算のこのステートメント

a ^p ≡a（mod p）

aがpで割り切れない場合は、

a ^p-1 ≡1（mod p）

この問題では、2つの数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 ⁶ ≡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!