同余

如果整数a和整数b除以正整数m的余数相等，叫做a，b模m同余，记作a≡b(mod m)
当然有两种理解的方法
1.两个数除以m的余数相同
2.两个数的差是m的倍数
关于同余有很多的性质：
1.自反性；2.对称性；3.传递性；4.同价性；5.同乘性；6.同幂性；7.同余不满足同除性

费马小定理

如果p是质数，那么对于任意一个整数a a^p≡a(mod p)

欧拉定理

如果一个正整数a，n互质，则a^{欧拉函数（n）}≡1(mod n)

拓展欧几里得算法

bezout定理，就是说，对于一个存在两个数a，b存在一对整数x，y，满足ax+by=gcd(a,b）
这就是exgcd，拓展欧几里得算法,是用来求解线性同余方程的

gcd(a,b)=gcd(b,a%b)那么存在一对整数x，y，满足bx+a%by=gcd(b，a%b)，然后通过一系列的分解化简，就能求出来ay-b(x-a/b*y)=gcd(a,b)

给定一个方程Ax+By=k
给出A   B   k，求出x和y，使得满足方程

其实就是上面所提到的公式
ay-b(x-a/by) = 然后令x_=y，y_=x-a/by，那么 ax_+by_=gcd(a,b)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
int exgcd(int a,int b,int x,int y)
{
	if(b==0)
	{
		x=1,y=0;
		return a;
	}
	else
	{
		int x_,y_;
		int d=exgcd(b,a%b,x_,y_);
		x=y_;
		y=x_-(a/b)*y_;
		return d;
	}
}
int main()
{
	int a,b,k,x,y;
	cin>>a>>b>>k;
	int d=exgcd(a,b,x,y);
	if(k%d)
	{
		cout<<"无解"<<endl;
	 	return 0;
	}
	else
	{
		x=x*k/d;
		y=(k-a*x)/b;
	}
	return  0;
}

---

1082 同余方程（板子）

其实，同余得意思就是如果整数a和整数b除以正整数m的余数相等，叫做a，b模m同余，记作a≡b(mod m)
当然这个是官方语言，意思通过字面就能理解，就是同个得余数
因为余数相同，所以引入出来一个定律就是两个人的差是m的倍数

#include<iostream>  
#include<cstdio> 
#include<algorithm>
#include<string>
#include<cstring>
#include<cmath>
using namespace std;
int a,b,x,y,k;
void exgcd(int a,int b)
{
    if(b==0)
    {
        x=1;
        y=0;
        return;
    }
    exgcd(b,a%b);//递归 
    k=x;
    x=y;
    y=k-a/b*y;
    return ;
}
int main()
{
    cin>>a>>b; 
    exgcd(a,b);
    cout<<(x+b)%b<<endl;
    return 0;
}