密码学数学基础(六)

我们接着来看，密码学有关的数学知识，这次还是直接进入主题，我们来回顾一下小学学过的认识时间[^1]

时间这个概念，相信各位读者应该都不会陌生，那么这个和我们今天要讲的东西有什么联系呢，注意观察到一个现象，对于每天的早上的8点，对于时针所指向的位置是不是都是相同的，那么这里蕴含着什么数学思想呢，我们一起来看一下本文所介绍的内容「同余」。

同余的概念

❝

「定义1」 给定一个正整数m, 两个整数a, b, 如果a - b可以被m整除，我们称两个整数a, b叫做模m同余，记作 , 否则，叫做模m不同余，记作 .

❞

如何判断同余

我们接着来看一下如何来判断同余，首先我们可以通过定义来判断，然后呢，我们在来一些其他的判别方法。

❝

「定理1」 假设m是一个正整数，设a和b同余的充要条件为存在一个整数q使得.

❞

这里为了完整，我们来给一个证明吧。

❝

「证明」

❞

我们先来证明一下充分性，因为a和b模m同余，我们根据定义有

根据整除的定义，我们可以找到一个整数q使得，也就是.

我们再来证明一下充分性，因为存在一个整数q使得，则有，再来根据整除的定义，我们有

再来根据同余的定义，我们可以知道a和b模m同余.

对于接下来的内容呢，我们先来回顾一下之前所学过的有关关系的知识，有关详细的知识，可以参考文末参考资料的相关章节[^2]，在这里只列出来几个定义了。

❝

「定义2」 如果对于每个元素 都有 我们称定义在集合A上的关系R为自反的。

❞

❝

**定义3 **对于任意的 如果只要就有我们称定义在集合A上的关系R是对称的

❞

❝

「定义4」 如果对于任意的 如果 并且 那么我们称定义在集合A上的关系R是传递的

❞

对照这上面的定义，因为同余也是针对于两个元素之间的一个二元关系，我们可以看一下同余的性质

同余的性质

• 对于任意的整数, 有

• 若 则

• 若 则

这里大家可以自行验证一下，这块的证明就不在这里给出了，应该不难去验证。好了，有关同余的知识呢，就先介绍到这里了，最后一如既往的文艺一把

❝

博观而约取，厚积而薄发 —苏轼

❞

这里面应该是富含了一个哲学的道理，量变引起质变，一点一点的积累，没准突然一个顿悟，就能够突然的理解很多之前难以理解的知识了。

参考资料

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

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

[^2]: 离散数学及其应用_[美]_Kenneth_H.Rosen^[2]

Reference