推荐这篇日记的豆列
&&&&&&&&&&&&&|&&|&&|&&|&&
当前位置： >
从“模线性方程”到“中国剩余定理”
作者：chuanwang66 & 来源：转载 &
浏览次数：
摘要: &&&& 中国余数定理 即最开始《孙子算经》的“物不知数”问题，到秦九韶《数书九章》有了系统答案。而西方19世纪高斯《算术探究》才有一次同余式解法。据说还有“韩信点兵”的故事： 　　韩信在点兵的时候，为了保住军事机密，不让 敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵
&&&& 中国余数定理 即最开始《孙子算经》的“物不知数”问题，到秦九韶《数书九章》有了系统答案。而西方19世纪高斯《算术探究》才有一次同余式解法。据说还有“韩信点兵”的故事： 　　韩信在点兵的时候，为了保住军事机密，不让 敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从1至5报数，也记下最后一个士兵所报之数；最后令士兵从1至7 报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。 &&&& 西方人文献中都称“中国剩余定理”（Chinese Remainder Theorem），而且这条定理可以说是初等数论中同余理论的核心定理之一，它解释的是关于同余线性方程组可解性的问题，我们都知道方程在代数中是很要紧的一个概念，在同余理论中当然还有高次方程的理论，这个涉及跟深的勒让德符号和高斯二次反转定理，还有就是本原根等等，而这些东西在代数数论中又会得到加深。比如本原根存在定理会在域论中以一种更精彩的面貌出现。中国剩余定理也一 样，在环论中会以更加一般的方式通过理想的概念出现(数学中重要的定理都会被人试图推广，西方人推广了这个定理，可见中国剩余定理在数学中的地位了)。 呃。。。打住，还是从故事开始讲吧 &&&& 1. 首先要讲一下同余 这个概念 &&&& 首先我们要有一个非零整数m，那么对于另外两个整数a,b，如果m|a-b（m整除a-b），我们就说a,b关于m同余(就是说a除m和b除m得到的余数相同，同余这个术语是这样来的),记作a=b(mod m)（等号一般写出三条线的，不过这里不晓得怎么打╮(╯▽╰)╭） &&&& 比如对于2这个数，我们发现所有偶数都关于2同余，所有奇数也都关于2同余，这样关于2同余这个概念就跟数的奇偶性一样了，其实mod2同余在计算机中非常重要，它恰好给出了二值逻辑需要的数学结构。 &&&& 为什么要同余这个概念？呃。。。。这个问题小弟还不知道怎么用通俗的语言的回答，这样说吧，给松鼠一推果子，果子太多了松鼠高兴完了就得晕，不知道怎么去 处理这么一推果子，但是如果把果子分成几个小份，那么一堆堆分开处理就方便多了。例子举的实在勉强，但是东西多了不容易处理倒是人人都能理解，整数太多了 (里面随便抛出一个问题就够人们花费几百年了)，而且复杂，那怎么办呢？大数学家高斯就想出一种办法，把整数分类，分好类了再去研究，那就会轻松多了。这 种分类就是同余，比如上面的mod2同余就是等价于整数的奇偶性分类，讲整数分成2类，同样mod m将整数分成了m类，所有关于m同余的数分成一类。 &&&& 2. 模线性方程
&&&& 就像一般的方程ax=b一样，我们会问给定a,b,m,方程ax=b(mod m)是不是一定有解呢？我们知道对于一般实数的方程ax=b都有解x=b/a，只要a不是0。但这个问题在同余中就不对了，我们考虑方程2x=1(mod 2)，就是2|2x-1，右边总是奇数的，怎么可能有解呢？。不过放心，就像初中学过的二次方程ax^2+bx+c=0的判别式一样，我们对于一般方程 ax=b(mod m)也有判别式(a,m)（就是a,m的最大公约数），结论是这样的： &&&& 如果(a,m)|b，那么方程有解，反之则没有解。 &&&& 上面的这个例子就说明同余中的方程并不怎么好解，其实上面那个判别方法为什么成立这里就不好讲了(而且有办法把这个解算出来)，有兴趣的童鞋们自己去看初等数论的书吧^_^ &&&& 3. 现在我们就可以解释中国剩余定理 (模线性方程组 )了：
&&&& 一言蔽之，求解“模线性方程组”的方法就是：通过如下“变0法”或“套公式法”，将模线性方程组化成若干一次模线性方程，逐个求解，然后相加
&&&& 现在我们假设上面问题中的a=1，那么方程变为x=b(mod m)，不需要判别式就知道这个方程有解。可是中国古代的数学家提出了一个问题，如果方程里的b,m可以取好几组数，那么这些方程是不是有公共的解呢？具体说就是： &&&& 给定数b_1,b_2,...,b_n; m_1,m_2,...,m_n,那么方程组x=b_i(mod m_i)(i: 1~n)（这里b_1表示b有下标1）是不是有公共解呢？ &&&& 学数学最头痛的就是不知道书上在讲什么东西，估计不熟悉同余的童鞋们已经糊涂了，还是给个例子吧： &&&& 比如方程组x=3(mod5),x=2(mod3)是不是有公共解呢？顽强的童鞋们可以用无敌凑数法发现8是一个解，恭喜恭喜，不过这样可不好，除了8还有其他解吗？整数无穷多个，谁都不愿意花一辈子时间去试所有解，终于在试到个数的时候去见mks了。 &&&& 我们的问题就是这种方程组是不是也有判别式呢？中国剩余定理说，有！我们现在就来看看怎么找出这个判别式： &&&& 这里小弟我打算用上面那个具体的方程组来说，一般情况的证明估计会吓跑好多对数学尚有兴趣的小朋友，小弟我当时第一次看时就是这样 &&&& 我们现在先来解方程x=3(mod5),x=2(mod3)，解完之后看看怎么把它推广到一般的方程组情况，然后从解法中提炼出我们需要的判别式。而整个过程就是我们所说的中国剩余定理的灵魂了。 &&&& 这个方程不好解，为什么呢？我们只会解实数的方程，你突然冒出一个同余，还搞一堆方程，本来就糊涂了，怎么会好解呢？不急不急，我们慢慢来，上面我们讲过一个方程的解了，我们看看能不能转化成一个方程的情形： &&&& 现在考虑一个现象，如果x=a(mod m), y=b(mod m),那么我们可以证明x+y=a+b(mod m)， &&&& 好！我们现在看上面的方程， &&&& 可以将x=3(mod5) 对应到 x1=3(mod5)---(1) , x2=0 (mod5)---(2) ==& x1+x2=3(mod5) &&&& 可以讲x=2(mod3) 对应到 x1=0 (mod3)---(3) , x2=2(mod3)---(4) ==& x1+x2=2(mod3) &&&& 那么如果我们解出了上面方程(1)~(4)，哈哈，m+n就是一个解了 &&&& 可是新的方程比原来的好解么？因为x1=0(mod3)，这样我就可以把x1写成3t,这样方程x1=0(mod 3)就不需要了，而两个方程（ 方程(1)& 方程(3) ）就变成了一个3t=3(mod 5)，这个方程我们会，(3,5)=1|3，方程有解的。任务解决了，同样的办法可以知道n也是有解的，那么原来的方程 x=3(mod5),x=2(mod3)有解。
&&&& 现在如果能够算出一次模线性方程组的解，那么模线性方程组的解也就能算出来了。具体算法去看初等数论吧~
&&&& 同样对于n个方程的方程组，我们可以用类似变零的办法把它化成一个方程，这样得到n个方程，每个方程有一个判别式，如果每个都表示有解，那么方程组就有解。
&&&& 中国剩余定理说的是：如果m_i之间两两互素，那么方程组有解，而且所有的解关于m_i的乘积同余。 &&&& 之所以不写出具体定理的表述，是因为小弟觉得掌握了上面的方法就把握住了定理了。
&&&& 另见这个例子：《算法导论》P537——直接套公式求解模线性方程组：
方法：（这个过程中全是单纯的四则运算和模数运算）
&&&& 假设模线性方程组是 a=a1(mod n1), a=a2(mod n2), ...
&&&& 定义n=n1n2n3..., 定义mi=n/ni，定义ci=mi(mi^-1 mod ni)，有a=(a1c1+a2c2+...)(mod n)
&&&& a=2(mod5), a=3(mod13)
&&&& a1=2, a2=3
&&&& n1=5, n2=13
&&&& n=n1n2=5*13=65
&&&& m1=n/n1=65/5=13
&&&& m2=n/n2=65/13=5
&&&& c1=m1(m1^-1 mod n1)=13 (13^-1 mod 5) = 13 ( 2 mod 5) = 26, 注意到：13^-1=2(mod 5)
&&&& c2=m2(m2^-1 mod n2)=5(5^-1 mod 13) = 5 ( 8 mod 13) =40, 注意到：5^-1=8(mod 13)
&&&& ∴a=(a1c1+a2c2) mod n =(2*26 + 3*40) mod 65= 42 (mod 65)
&&&& 4. 再看韩信点兵
&&&& 现在我们可以看看楼上那个韩信点兵的问题，这个问题用同余这个语言来讲特别容易，就是找一个数x，满足x=a(mod 3), x=b(mod 5), x=c(mod7)。根据中国剩余定理，因为3,5,7两两互素，所以方程肯定有解，而且所有解关于3*5*7=21同余，所以把所有解排出来，两两间隔就是21，那么如果韩信确信士兵大概是100人，那么靠近100的那个解就应该是士兵人数了。
-----------------------------------------------------------------------------------------------------------------------------------
POJ 1006 Biorhythm ==& /ycdoit/item/640fa5914617f
版权所有 IT知识库 CopyRight (C)
, All Rights Reserved.数论在计算机科学中有哪些精彩的应用？ - 知乎235被浏览12132分享邀请回答12813 条评论分享收藏感谢收起6添加评论分享收藏感谢收起更多1 个回答被折叠（） 上传我的文档
 下载
 收藏
所有未标明（原创）的资料文档、资料、PPT、议论文书均来源于网络，资料来自于互联网，版权归相关厂商所有，仅限于学习使用，不得从事商业活动，如有侵权，及时告知并做删除处理。
 下载此文档
正在努力加载中...
密码编码学与网络安全_原理与实践第5版_8教学课件
下载积分：1500
内容提示：密码编码学与网络安全_原理与实践第5版_8教学课件
文档格式：PPTX|
浏览次数：3|
上传日期： 12:13:48|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1500 积分
下载此文档
该用户还上传了这些文档
密码编码学与网络安全_原理与实践第5版_8教学课件
官方公共微信(Relax 数论1.8)POJ 1284 Primitive Roots(欧拉函数的应用: 以n为模的本原根的个数phi(n-1))
* POJ_2407.cpp
Created on: 日
Author: Administrator
const int maxn = 1000015;
bool u[maxn];
ll su[maxn];
ll gcd(ll a, ll b) {
if (b == 0) {
return gcd(b, a % b);
void prepare() {//欧拉筛法产生素数表
memset(u, true, sizeof(u));
for (i = 2; i <= 1000010; ++i) {
if (u[i]) {
su[++num] =
for (j = 1; j
1000010) {
u[i * su[j]] =
if (i % su[j] == 0) {
ll phi(ll x) {//欧拉函数,用于求[1,x)中与x互质的整数的个数
ll ans = 1;
for (i = 1; i <= ++i) {
if (x % su[i] == 0) {
while (x % su[i] == 0) {
x /= su[i];
for (k = 1; k
ans = ans * (x - 1) %
int main() {
prepare();
while (scanf("%d", &n) != EOF) {
printf("%lld\n", phi(n-1));//以n为模的本原根的个数为phi(n-1)。而,[1,n]与n互质的整数的个数为phi(n)