同余与剩余系
设有整数 \(n_1,n_2,m\) 满足 \(\exist q_1,q_2,r \in \Z,n_1=mq_1+r,n_2=mq_2+r\)，则称 \(n_1,n_2\) 模 \(m\) 同余，记作 \(n_1 \equiv n_2 \pmod m\)。
称所有模 \(m\) 同余（设为 \(r\)）的 \(n\) 组成的集合为模 \(m\) 的一个剩余类，记作 \(C_r\)。
设有 \(m\) 个整数构成的集合 \(A\) 满足 \(a_1,\dots,a_m\) 模 \(m\) 互不同余（即从每个剩余类中各取一个数），则称 \(A\) 为模 \(m\) 的一个完全剩余系。
容易证明一个满足上面条件的集合至多有 \(m\) 个数。
我们可以再化简一下，只取与 \(m\) 互质的数，这样就得到了模 \(m\) 的一个简化剩余系。简化剩余系的大小为 \(\varphi(m)\)。
欧几里得算法与裴蜀定理
欧几里得算法（辗转相除法）：\(\gcd(a,b)=\gcd(b,a\bmod b)(a,b\in\Z)\)。
证：设 \(a=qb+r,\gcd(b,r)=d\)。
由于 \(\gcd(b,a\bmod b)=\gcd(b,r)\)，则有 \(d|r,d|b\)，则可以推出 \(d|a\)，则有 \(d|\gcd(a,b)\)。
设 \(k=\gcd(a,b)\)，则 \(k|a-qb=r\)，说明 \(k|\gcd(b,r)\)
因此，\(\gcd(a,b)|\gcd(b,a\bmod b),\gcd(b,a\bmod b)|\gcd(a,b) \Rightarrow \gcd(a,b)=\gcd(b,a\bmod b)\)。
裴蜀定理：若有 \(a,b,m\in\Z\)（\(a,b\) 不全为 0），则存在一组解 \(x,y\in\Z\) 使得 \(ax+by=m\) 的充要条件是 \(\gcd(a,b)|m\)，且若有解则必有无穷多组解。
证（拓展欧几里得算法）：
必要性显然，下证充分性：
不妨假设 \(a,b \ge 0\)，因为正负号的不同可以简单地通过 \(x,y\) 的正负性来改变。
同时，只要证明 \(ax+by=\gcd(a,b)\) 即可，因为对 \(x,y\) 扩大若干倍即可得到 \(m\)。
那么两边同时除以 \(\gcd(a,b)\)，即 \(a'x+b'y=1\)。
我们在求 \(\gcd(a',b')\) 的时候是怎么做的？后几步单独拿出来看（不妨设此时的两个求公约数的数分别为 \(u,v\)）：
\[\gcd(a',b')=\gcd(u,v)=\gcd(v,1)=\gcd(1,0)=1 \]发现出现了一个 \(u=qv+1\)，移项得到 \(u-qv=1\)。那么现在就得到了一组对于 \(u,v\) 的解。
能不能从 \(u,v\) 推到 \(a',b'\) 呢？答案是可以的。
假设我们上一级求的是 \(\gcd(\lambda u+v,u)=\gcd(u,v)\)，已知 \(ux_0+vy_0=1\)，要求 \((\lambda u+v)x_1+uy_1\) 的解。
构造：取 \(x_1=y_0,y_1=x_0-\lambda y_0\)，得到
\[\begin{aligned} &(\lambda u+v)x_1+uy_1 \\ =&(\lambda u+v)y_0+u(x_0-\lambda y_0) \\ =& \lambda uy_0+vy_0+ux_0-\lambda uy_0 \\ =&ux_0+vy_0=1 \end{aligned} \]逐层推上去即可，这样不仅证明了该定理，还求出了一组解。
有了特解后，其通解为小学奥数内容，这里不再赘述。
标签：剩余,uy,gcd,数论,bmod,速查,同余,提高,lambda From： https://www.cnblogs.com/Lewis-Li/p/NOIP_NT.html