高校问答pptv打不开:韩信点兵的除几余几的问题
来源：百度文库 编辑：高校问答 时间：2024/04/19 08:59:30
五树梅花开一枝，
七子团圆正月半，
除百零五便得知。”
是说一个数能背5和7整除且除3余一是70
背3和7整除，除5余一的是21......
那是怎么得出来的啊，
有什么具体的算法吗？
发我的邮箱aisi_911@163.com
这就是中国剩余定理。严格的证明可见：
http://www.math.pku.edu.cn:8000/misc/course/algebra/download/215.doc
§2 同余式
8.2.1 有理整数环中的同余的定义
定义8.5 设 是一个正整数，若 ，且 ，亦即 ，则称 与 模 同余，记作 。不难得到， 与 模 同余就是它们用 做带余除法所得的余数相同。整数模 同余为一等价关系，验证如下：
1） 反身性： ；
2） 对称性：若 ，则 ；
3） 转递性：若 ， ，则
。
关于这个等价关系划分为等价类，给定整数 ，所有与 模 同余的整数属于一个类，称为以 为代表的同余类。
8.2.2 Euler -函数
定义8.6(与 互素的剩余类的定义) 设 是一正整数。如果 ，则 称为与 互素的剩余类。在全部模 剩余类中，与 互素的剩余类的数目记作 ，称作Euler函数。
引理 设
是全部互不相同的与 互素的剩余类，有设 ，则
也是全部互不相同的与 互素的剩余类。
简证 因为 ，故 ，即 为与 互素的剩余类；由若 ，则 ，于是 ，从而 ，矛盾。
定理（Euler定理）设 是与正整数 互素的整数，则
证明 设全部互不相同的与 互素的剩余类为
，
则由引理
与上述 个剩余类仅是排列次序不同而已，所以把它们连乘起来应该相等，即
于是
因 ，故 。于是
，
注意 ，故命题成立。
作为Euler定理的推论，我们有
定理（Fermat小定理）设 为素数，若 不整除整数 ，则 。
事实上，模 的 个剩余类，除 外，均为与 互素的剩余类，即 。
8.2.3 中国剩余定理
定理（中国剩余定理） 设 是 个两两互素的正整数。任给 个整数 ，必存在整数 ，使
证明 首先，对一固定的 。当 时， ，则有 ，使 。令
另一方面有
现在利用上面得到的 构造整数
当 时， ，即 ，而 ，带入上式得
定理得证。