ทฤษฎีบทเล็กๆ ของแฟร์มาต์ −
ทฤษฎีบทนี้ระบุว่าสำหรับจำนวนเฉพาะ p ใดๆ
A 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
ผลลัพธ์: จริง
คำอธิบาย:
อ p-1 ≡ 1 (mod p)
=> 3 6 ≡ 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!
