同余学习笔记

声明：由于本蒟蒻太菜了，所以有些东西是从别的书上弄来的，具体请见《初等数论》、《基础数论》等。

写在前面

同余是个啥？？

在日常生活中，我们所注意的常常不是某些整数，而是这些数用某一固定的数去除所得到的余数，例如我们问现在是几点钟，就是用\(24\)去除某一个总的时数所得的余数，又如问现在是星期几，就是问用\(7\)去除某一个总的天数所得的余数，同是几点钟或同为星期几，常常在生活中有同样的意义，这样就在数学中产生了同余的概念

同余式不仅相当有趣，而且应用广泛，以后就要经常用到。任何尚未真正掌握同余式的人，都不能自称熟悉数论，所以，同余是数论里非常重要的一部分内容，作为一个蒟蒻，一定要好好学，不然你死都不知道自己怎么死的（LMC的经典语录）

在这里，我们将会写一些关于同余的比较简单的东西，一起来看看吧！

定义

若\(a,b\)为两个整数，且他们的差\(a-b\)能被某个自然数\(m\)所整除（即\(m\vert(a-b)\)）,则称\(a\)就模\(m\)来说同余于\(b\)，或者说\(a\)和\(b\)关于模\(m\)同余，记为\(a\equiv b(mod \ m)\)。它意味着：\(a-b=m\ast k\)（\(k\)为某一个整数）

性质

对于整数\(a,b,c\),和自然数\(m\),对模\(m\)同余具有以下一些性质：
1.自反性：\(a\equiv b(mod\ m)\)
2.对称性：若\(a\equiv b(mod\ m)\)，则\(b\equiv a(mod\ m)\)
3.传递性：若\(a\equiv b(mod \ m)\)，\(b\equiv c(mod \ m)\)，则\(a\equiv c(mod\ m)\)
4.同加性：若\(a\equiv b(mod \ m)\)，则\(a+c\equiv b+c(mod \ m)\)
5.同乘性：若\(a\equiv b(mod \ m)\)，则\(a\ast c\equiv b\ast c(mod \ m)\)，若\(a\equiv b(mod \ m)\)，\(c\equiv d\)，则\(a\ast c\equiv b\ast d(mod \ m)\)
6.同幂性：若\(a\equiv b(mod m)\)，则\(a^n\equiv b^n(mod\ m)\)