exgcd有关同余问题

关于同余关系的一些定理：

1. 自反性：(aequiv apmod{m})

2. 对称性：(aequiv bpmod{m}),则(bequiv apmod{m})

3. 传递性：(aequiv bpmod{m})，且(bequiv cpmod{m})，则(aequiv cpmod{m})

同余的三则运算：

若(a,b,c)为整数，(m)为正整数，且(aequiv bpmod{m})

1. ({a+c}equiv {b+c}pmod{m})

2. ({a-c}equiv {b-c}pmod{m})

3. ({a imes c}equiv {b imes c}pmod{m})

同余式的三则运算：

(a,b,c,d)为整数，(m)为正整数，且(aequiv bpmod{m})，(cequiv dpmod{m})

1. ({ax+cy}equiv {bx+dy}pmod{m})其中(x,y)为任意整数，即同余式可以相加

2. ({a imes b}equiv {c imes d}pmod{m})，即同余式可以相乘

3. ({a^n}equiv {b^n}pmod{m})，其中(n>0)

4. (f(a)equiv f(b)pmod{m})，其中(f(x))为任意整数系多项式

扩展欧几里得:

数论证明就算了吧，利用扩展欧几里得定理我们可以求解(ax+by=gcd(a,b))的问题

如果我们现在要求(ax+by=m)，我们可以先用扩展欧几里得求(ax+by=gcd(a,b))，如果(gcd(a,b))不能整除(m)则无解，否则在(modm)的意义下有(gcd(a,b))个解，所有的解可以通过对其中一个解加减(dfrac{b}{gcd(a,b)})得到

code:

void exgcd(int a,int b,int &x,int &y){
	if (!b){x = 1,y = 0;return;}
	exgcd(b,a%b,y,x);
	y -= (a/b)*x;
	return;
}