费马小定理在C ++中
费马小定理-
该定理指出,对于任何质数p,
甲p-P 是p的倍数。
模块化算术中的 该语句表示为:
一个p ≡一个(modp)的
如果a不能被p整除,
ap- 1≡1(modp)
在这个问题上,我们给了两个数字a和p。我们的任务是验证这些值上的费马小定理 。
我们需要检查,如果一个p ≡一个(模p)或p-1 ≡1(模p)
对于a和p的给定值成立。
让我们举个例子来了解这个问题,
输入: a=3,p=7
输出: 真
解释:
Ap- 1≡1(modp)
=>36 ≡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!