密码学数学基础(三)

我们接着上篇文章来聊密码学有关的数学知识，这次依然没有华丽的开场，还是直入主题吧。

前情回顾

上文，我们用到了小朋友分桃子的例子，那么，相信各位读过小学二年级的读者，也应该记得这个是有后续的，那我们知道，我们在分桃子的时候，每个小朋友恰好分完所有的桃子，这种情况一般来说是比较少的，这也就是说呢，我们计算的时候就要考虑下余数了，我们看下小学二年级的课本[^1]

咱也不知道为什么，可能是怕小朋友吃的桃子太多了，然后下册还是除法就改成了分铅笔了，咱们不管他们分什么，我们通过这个小学二年级的例子来引出来我们今天的主题，「带余除法」。

带余除法(Euclid除法)

因为恰好整除的概率是非常低的，也就跟我们上面所说的小朋友分铅笔的例子，假设有三个小朋友，每人分三只，那么就会剩下一只，这是不是非常的简单，好，我们来看下一般的描述.

❝

「定理1」  (带余除法) 设a, b是两个整数，其中b > 0, 则存在唯一的整数q, r使得

❞

这个定理也非常的好理解，那么咱们还是根据小学二年级课本当中的例子来吧，我们也来继续分铅笔，假设有a只铅笔，然后我们要分给b个小朋友，如果要求所剩的铅笔个数是不能超过小朋友的人数的，也就是假设还剩余r只铅笔，如果r > a的话，那么我们是不是还能给每个小朋友再至少分一只铅笔，这个应该是比较好理解，不理解的话，可以自己买一把铅笔，然后去分一分，那么这个分配方案是唯一的。这个看起来是这样，但是具体是不是对的呢，接下来我们来证明一下[^2].

❝

「证明:」

❞

• **唯一性: **如果还有整数 r'和q'满足

我们和原式做一个差值，得到

然后，我们还有，然后根据整除的性质，我们可以得到, 因此唯一性成立.

• **存在性: **当时，我们可取 .当时，考虑集合

容易看出，集合T中必存在正整数，且必定存在一个最小正整数，记作

接下来，我们需要证明，必有 . 因为,所以若 则.显然，,这和我们之前说的是最小的正整数矛盾.取 这个就满足要求，然后，显然的充要条件是r=0因此定理得证.

我们看完了有关带余除法的相关知识，本文到这里也就快要结束了.

最后呢，我们来看一下有关带余除法的一般形式

❝

**定理2 **设a,b是两个整数，其中b > 0, 则对任意的正数c, 存在唯一整数q,r 使得

❞

有关这个定理的证明，可以参考下定理1的证明，这个基本相似，在这里就不重复给再来证明一下了。

小结

我们通过小朋友分铅笔的例子，如果说铅笔的个数不恰好是小朋友的整数倍，呢么铅笔就会有剩余，从而展开讲解了带余除法的相关知识，就目前而言，这几篇文章所使用到的知识还仅仅在小学二年级的范围之内，应该不难理解，然后又到了最后的文艺环节了

❝

及时当勉励，岁月不待人。—陶渊明【东晋】

❞

在这个内卷与躺平并行的时代，如果趁着年轻多多勉励自己，光阴流逝，多年以后，你是否会感激现在努力的自己呢？咱们下次再见~~~~

参考资料

• 信息安全数学基础 第二版 陈恭亮

[^1]: 苏教版二年级数学下册^[1]

[^2]: 公钥密码学的数学基础_王小云_王明强_孟宪萌^[2]

Reference