同余与剩余系
设有整数 \(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