C++의 페르마의 작은 정리

페르마의 작은 정리 -

이 정리는 임의의 소수 p에 대해,

아 ^p - 피 p의 배수입니다.

모듈식 산술 의 이 명령문 는

a ^p ≡ a (mod p)

p로 나누어 떨어지지 않으면

a ^{p - 1} ≡ 1(모드 p)

이 문제에서는 두 개의 숫자와 p가 주어집니다. 우리의 임무는 페르마의 작은 정리 를 확인하는 것입니다. 이러한 가치에 대해.

a ^p 인지 확인해야 합니다. ≡ a (mod p) 또는 a ^{p - 1} ≡ 1(모드 p)

및 p의 주어진 값에 대해 참입니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력: a =3, p =7

출력: 참

설명:

A ^p-1 ≡ 1(모드 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!