费马小定理在C ++中

费马小定理-

该定理指出，对于任何质数p，

          甲^p - P 是p的倍数。

模块化算术中的 该语句表示为：        

          一个^p   ≡一个（mod p）的

如果a不能被p整除，

 a ^p-  1≡1（mod p）

在这个问题上，我们给了两个数字a和p。我们的任务是验证这些值上的费马小定理 。

我们需要检查，如果一个^p   ≡一个（模p）或^{p - 1}  ≡1（模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!