恩爱狗

为何为难单身狗

根据高斯分布，我们可以知道当我们执着于寻找一个完美的伴侣时，这个概率仅有不到4.2%，就好比现在我在一个劲码文章的时候，舍友在电话里面和一个女生打情骂俏一样。当舍友一个个都脱单的时候，总会有一个人默默地心疼抱住胖胖的自己，投去羡慕的目光。

因此，在你的周围，总有需要被关心的单身的孩子们，他们善良、单纯、可爱并且为人亲切，乐观地作为被剩下的单身狗而生活。

这就是著名的中国剩余定理，又叫单身狗守恒定律。

马上就是5月20号了，所以大伙要记得看到周围的单身狗，别忘了请他们（我）吃饭，或者买一杯奶茶，因为能够在这一天仍旧不懈码字的，只有他们（我）了。

以上内容纯为凑字数扯淡，如有雷同，放心，不可能的。

==========================

传言有这样一个故事。韩信带兵打仗，在出征前需要清点人数，但是人数太多且战事紧急，即便把脚趾算上也数不过来呀，那该怎么办？

这个问题没有难住韩信，他让士兵按照如下的方法排队，并统计不够一排的人数的情况：

3人一排，多出2人

5人一排，多出4人

7人一排，多出6人

于是，韩信很快就得知了人数：1049。

就是这么神奇。单单凭借着么几个个位数字就能得知整个队伍，韩信到底怎么办到的？

而这一切都是追溯到中国古老的数学文化：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

这是《孙子算经》里面记载的一道题，大意是一个数除以3余2，除以5余3，除以7余2，求这个数是几。

这和上面韩信暗点兵的情况有点类似，都是通过相除后得到余数，进而得到那个数是多少。所以当我们解决了这个问题后，也就知道韩信是怎么出大招的了。

如果用我们现在的数学思维，这道题解法有许多。

首先，我们假设这个数为x，把上面的文字用数学语言表示：

x-2=3a

x-3=5b

x-2=7c

其中a，b，c均为正整数。

我们发现，当x被3和7整除的时候，都会产生相同的余数2，于是，我们就可以推测，x-2既是3的倍数也是7的倍数，而且3与7互素，所以x-2也是21的倍数。

那我们姑且先认为x-2=21n吧。之后我们再看x-3=5b，说明这个数的尾数一定是3或8。那么我们来处理n，当假设n等于1的时候，x=23，尾数为3，正好符合我们的条件。代入验证一下，发现23刚好就是这个数！

到这里我们不得不发问：对于n来说明明是可以任取的数，x难道就只有一个吗？

其实我们都知道，只要x的取值满足我们上述讨论的条件即可。那我们假设n=6，发现也符合上述条件，x=128也是一个解。所以我们不难发现，n的取值要保证当21n+2的值的个位数为3或8，所以n的取值可以是1，11，21，31…，6，16，26…有无穷多个，我们得到的23只是最小的值。

既然是古代的数学题，那就要用古代的解法来算：

三人同行七十稀，

五树梅花廿一枝。

七子团圆正半月，

除百零五便得知。

意思是把数除以3的余数乘70，除以五的余数乘21，除以7的余数乘15，然后加起来减去105的倍数，答案也可以得到23。

于是按照上面的两种方法，都可以去解释韩信点兵的问题了。当然得到的数字有许多，但是韩信毕竟也是身经百战了，见得多了，不同的人数对应的规模他肯定心里也是有准的，所以根据这种办法，他可以精确推算不同规模的队伍到底有多少人，这就是韩信暗点兵的秘密。

但是大家有没有发现，这种方法还有一个我们没有提到的细节，就是这些用到的作为除数的数都是素数。

我们知道，任何数都能被分解为几个素数的乘积，当一个数被不同素数除以并得到不同余数的时候，即便作为除数的素数很多，我们也一定可以构造出相应的数来满足这些条件。这是数论里面一个重要结论，也叫做中国剩余定理。

这是我们祖先伟大的数学文化，也是在世界上获得公开承认的一个发现。

我们尝试用数学语言来表示：

若

则

x=amod b=a+kb，k为整数。

关于x的值，我们都可以通过上述办法构造出来。

下面我们可以通过逆推的办法来作一个简单的验证。

任取两个数满足条件：

这里为了表示方便我们取上标表示不同的数。让上式相减，有：

于是有：

这说明两数之差即为不同素数的倍数。

对任意一个式子作一个移项处理，有：

当然所有的式子都可以这么处理，于是我们得到的式子在形式上就和下式相同：

这就是在构造数时所用的条件。

是不是很神奇？虽然这不是严格的证明推导，但是我们依旧可以发现其正确性。这就是我们祖先的智慧为我们留下的宝贵财富。

那中国剩余定理除了数数方便，它还有哪些用途呢？

实际上，中国剩余定理在目前银行机构所使用的RSA公开密码体系，占有举足轻重的地位。

RSA公开密码体系是基于大数不可分解理论搭建的，大数不可分解理论大意是：对于任意一个大的数，我们很难把它分解为两个素数的乘积。在公开密码体系中，对于加密密钥是公开的，保密的是解密密钥。这样在给某人发信息的时候，就像打电话一样需要找到某人电话号码一样，我们只需要找到对方的公开密钥并加密就好。而这个加密的安全性关键，就是选取的大数。

其实通过中国剩余定理，我们可以构造出一个数，利用不同的素数整除的约束条件，在本来就很大的数上，增加其干扰条件，显然约束的条件越多，干扰的条件越大，所需要的计算成本越高。

所以只有当所利用的数越不容易分解成两个素数乘积的时候，我们的信息安全才有保障。这就是为什么我们要使用RSA公开密码体系。不过中国剩余定理更多地是作为RSA公开密码体系的理论基础，并不是单单用来去构造那个数。

但是这不代表我们的信息就绝对安全，随着科技的发展，RSA体系的最大威胁就是量子计算机。如果用量子计算机去做分解，想要破解公开密码体系，仅仅半小时不到的事情。

最后问一句，

是不是因为我知道得太多了，所以才一直单身？