费马小定理和费马大定理_费马小定理推论

全栈程序员-用户IM • 2022年10月25日上午6:16 • 未分类

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46，售后保障稳定

（1）费马小定理结论：结论是若存在整数 a , p 且gcd(a,p)=1,即二者互为质数，则有a^(p-1)≡ 1(mod p)。(这里的 ≡ 指的是恒等于，a^(p-1)≡ 1(mod p)是指a的p-1次幂取模与1取模恒等)，再进一步就是a^p≡a(mod p)。
继续学习：中国剩余定理、拓展欧几里得(exgcd)、求除法逆元、费马小定理

（2）费马大定理结论：又被称为“费马最后的定理”，常见的表述为当整数n>2时，关于xⁿ + yⁿ = zⁿ 的方程没有正整数解。
当n=0时，实数范围只有x=0,y=0,z=0时才是解,当n=1时，就是一个加减法，当n=2时，就类似于勾股定理。
构造勾股数的四种表现形式：
（1）2n+1、2n²+2n、2n²+2n+1（n为正整数）是一组勾股数。
（2）2(n+1)、n²+2n、n²+2n+2（n为正整数）是一组勾股数。
（3）m²-n²、2mn、m²+n²（m、n表示两个不同的正整数且m>n）是一组勾股数。
（4）如果a、b、c是一组勾股数那么na、nb、nc（n为正整数）也是一组勾股数。

应用费马小定理：

题目链接：杭电oj 6440
http://acm.hdu.edu.cn/showproblem.php?pid=6440

在这里插入图片描述
题意：
给一个质数p，重新定义 + 和 * 使得（m+n)^p= m^p + n^p;(其中 m , n 指的是小于p的非负整数），使得对于任意的n,m属于[0,p-1]，满足式子，最后，输出两个n*n的矩阵表示加法和乘法的结果，对于1到p行，你将要输出第i行与第j列的数相加的结果；对于第p+1行到2p行，你将要输出第i行与第j列相乘的结果。
题解：个人理解就是让你选一个操作让(m+n)^p=m^p+n^p(0<=m,n<p)。成立，最后输出操作之后的值。因为给定的是素数，根据费马小定理得=(m+n)^p-1≡1(mod p),因此，m^p+n^p≡m+n(mod p)。所以在模p的意义下，(m+n)^p=m^p+n^p(0<=m,n<p)恒成立，且加法运算与乘法运算封闭。
下面附AC代码：

#include<iostream>
using namespace std;
int t,p;
int main()
{ 
   
	cin>>t;
	while(t--)
	{ 
   
		cin>>p;
		for(int i=0;i<p;i++){ 
   
            for(int j=0;j<p-1;j++){ 
   
                printf("%d ",(i+j)%p);
            }
            printf("%d\n",(i+p-1)%p);
        }
        for(int i=0;i<p;i++){ 
   
            for(int j=0;j<p-1;j++){ 
   
                printf("%d ",(i*j)%p);
        	}
        	printf("%d\n",(i*(p-1))%p);
        }
    }
	return 0;
}

Jetbrains全家桶1年46，售后保障稳定

应用费马大定理：

题目链接：杭电oj 6441
https://acm.dingbacode.com/showproblem.php?pid=6441

题意：
构造aⁿ+bⁿ=cⁿ，a和n给出，求b和c，所以就成了一道构造题。
题解：
由费马大定理可得当n=0（因为题目中a>=3）或者n>2时输出-1 -1
当n=1时，构造一个加减法就可以了。当n=2时，用奇偶构造法求出勾股定理中另外两个数。
下面附AC代码：

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll n,a,t;
int main()
{ 
   
	cin>>t;
	while(t--)
	{ 
   
		cin>>n>>a;
		if(n>2||n==0)
			printf("-1 -1\n");
		else{ 
   
			if(n==1){ 
   
				printf("1 %d\n",a-1);
			}
			else{ 
   
				if(a%2==0){ 
   
					ll ans=a/2-1;
					printf("%d %d\n",ans*ans+ans*2,ans*ans+ans*2+2);
				}
				else{ 
   
					ll ans=(a-1)/2;
					printf("%d %d\n",2*(ans*ans+ans),2*(ans*ans+ans)+1);
				}
			}
		}
	}
	return 0;
}