同余与剩余系

设有整数 \(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} \]

逐层推上去即可,这样不仅证明了该定理,还求出了一组解。

有了特解后,其通解为小学奥数内容,这里不再赘述。

原文地址:http://www.cnblogs.com/Lewis-Li/p/NOIP_NT.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性