概念
首先，同余是数论中一个非常重要的内容，信息学中的数论无非就是围绕着素数和同余等转来转去，所以，这一块要好好学阿。
同余的定义：有两整数$a，b$，若它们除以整数$m$所得的余数相等，则称$a$与$b$对于模$m$同余或$a$同余于$b$模$m$
记作：$aequiv b pmod{m}$
再简单点说，对于两个数$a，b$，$adiv m=xldots r$，$bdiv m=yldots r$，这两个表达式的余数相同，就说$a$和$b$关于模$m$同余。例如，$34div 7=4ldots 6$，$20div 7=2ldots 6$，$34$和$20$除以$7$得到的余数相同，都是$6$，就是$34$和$20$关于模$7$同余。很简单吧。
下面要用到的：$(a,b)$表示$a$和$b$的最大公约数，还可表示为$gcd(a,b)$。类似的，$[a,b]$表示$a$和$b$的最小公倍数，还可表示为$lcm(a,b)$
同余的十条性质
- 若 $aequiv b pmod{m}$，则$bequiv a pmod{m}$
- 若 $aequiv b pmod{m}$，$bequiv c pmod{m}$，则$aequiv c pmod{m}$
- 若 $a_1equiv b_1 pmod{m}$，$a_2equiv b_2 pmod{m}$，则$a_1+a_2equiv b_1+b_2 pmod{m}$
- 若 $a+bequiv c pmod{m}$，则$aequiv c-b pmod{m}$
- 若 $aequiv b pmod{m}$，并且$a=a_1d$，$b=b_1d$，$(d,m)$=1，则$a_1equiv b_1 pmod{m}\$ 证明一下？可知$a-bequiv 0 pmod{m}$，$a_1d-b_1dequiv 0 pmod{m}$，则$d(a_1-b_1)equiv 0 pmod{m}$，$mmid d(a_1d-b_1)$，所以$mmid a_1d-b_1$
- 若 $aequiv b pmod{m}$，$k>0$，则$akequiv bk pmod{mk}$
- 若 $aequiv b pmod{m}$，$d$是$a，b$及$m$的任意整数，$ frac{a}{b}equiv frac{b}{d} pmod{frac{m}{d}} $
- 若 $aequiv b pmod{mi}$，$i=1,2ldots k$，则$aequiv b pmod{[m_1,m_2ldots m_k]}$
- 若 $aequiv b pmod{m}$，$dmid m$，$d>0$，则$aequiv b pmod{d}$
- 若 $aequiv b pmod{m}$，则$(a,m)=(b,m)$，若$dmid m$及$a,b$二数之一，则$dmid a,b$另一个
同余类（剩余类）
设$n$是一个正整数，任意一个整数被$n$除后，所得的余数一共有$n$中情形，$0,1,2ldots n-1$，它们中每一个数对模$n$不同余。所以说，每个整数恰与这$n$个整数中某一个对模n同余。这样一来，按模$n$是否同余对整数集进行分类，可以将整数集分成$n$个两两不相交的子集。我们把（所有）对模$n$同余的整数构成的一个集合叫做模n的一个剩余类。
简单点说：由关于模$m$同余的数组成的集合，每一个集合叫做关于模$m$的同余类（剩余类）
这定义是从网上copy下来的，基本都是这么说的，有没有一些些糊涂qwq，我第一次看也是。来举个栗子吧，模$5$的剩余类，其中一个是$1,6,11,16,21ldots $，这些数模$5$都等于$1$，所以这些数在一个剩余类内，模$5$的另外一个剩余类：$2,7,12,17,22ldots $，它们模$5$都等于$2$，所以它们在一个剩余类内
完全剩余系
完全剩余系其实更好理解，再来copy一下定义：从模$n$的每个剩余类中各取一个数，得到一个由$n$个数组成的集合，叫做模$n$的一个完全剩余系
举个栗子就明白了：关于模$5$的一个完全剩余系是$0,1,2,3,4$，这就是从上面的每个剩余类中拿了第一个数，组成了这个完全剩余系。
最简单的模$m$的完全剩余系是$0,1,2,ldots ,m-1$，也叫作模$m$的最小非负完全剩余系。显然$m$个相邻整数构成模$m$的一个完全剩余系
区分剩余系与完全剩余系：剩余系就是一个整数集中的数模$n$后余数的集合。如果一个剩余系中包含了这个正整数所有可能的余数(一般地，对于任意正整数$n$，有n个余数:$0,1,2,ldots ,n-1$)，那么就称这个剩余系为模$n$的一个完全剩余系。
应用
同余有几种题型，比如证明能不能被整除，求余数与末尾数，解不定方程
来看几道经典的题
例一：一个整数除$300,262,205$的余数相同（余数不为零），则这个整数是_____。
分析：按照同余的性质，如果$n$分别除以$a,b$后得到相同的余数，那么$n$一定能整除$a-b(a>b)$
所以，这个题就变成了求$gcd(300-262,262-205)$
例二：求$6^{592}$被$11$除的余数
分析：由费马小定理，$6^{10}equiv 1 pmod{11}$，$(6,11)=1$，所以$6^{592}=6^{10*59}*6^2=(6^{10})^{59}*6^2$
$(6^{10})^{59}equiv 1 pmod{11}$，$6^2*(6^{10})^59equiv 6^2 pmod{11}$，所以$6^{592}equiv 3 pmod{11}$
例三：$1986$年$2$月$9$日是星期日，请问再过$1988$天是星期几？那么再过$1988^{1986}$天是星期几？
分析：日期问题本质上就是循环问题，循环周期是$7$，过了多少天是星期几，就是转化成天数除以$7$的余数是多少，有点找规律的感觉。$1988div 7=284ldots 0$，余数为$0$，所以再过$1988$天还是星期天，但是后面那个怎么解决呢？这就需要一些技巧了。要知道，余数的幂决定幂的余数，几个被除数相乘，每一个被除数除以同一个余数所得的余数乘积，决定了这几个被除数相乘的乘积除以这个除数所得的余数，来看一下
$8div 7=1 ldots 1\$ $9div 7=1 ldots 2\$ $72div 7=10 ldots 2$
可以看出，余数相乘的乘积决定了$8$与$9$乘积$72$除以$7$所得的余数，所以对本题来说，我们可以吧$1988$除以$7$得出余数，余数相乘进而求得整体除以$7$所得的余数。$1988div 7=284ldots 0$，余数为0，余数相乘得 $0^{1986}=0$，所以$1988^{1986} div 7$余数为$0$，所以当天还是星期日。
例四：已知整数列${x_n}$满足$x_{n+1}=x_1^2+x_2^2+ldots +x_n^2,nge 1$，求$x_1$的最小值，使得$2006$整除$x_{2006}$
分析：可知$x_{n+1}=sum_{i=1}^n x_n^2=x_n+x_n^2=x_n(x_n+1)$
所以，$2mid x_{n+1}$，
故$2006mid x_{2006} Longleftrightarrow 1003mid x_{2006}Longleftrightarrow 17mid x_{2006}$ 且$59mid x_{2006}$
若$x_nequiv c pmod {17}$，则
$x_n(x_n+1)equiv 0 pmod {17}Longleftrightarrow cequiv 0pmod {17}$或$cequiv -1pmod {17}$
而$x(x+1)equiv -1pmod {17}$无解，于是，
若$17mid x_{2006}$，则
$x_{2006}equiv {x_{2005}(x_{2005}+1)} pmod {17}$
若$x_{2005}equiv -1 pmod {17}$，则$x_{2004}$无解
所以，$17mid x_{2005}$，
递推知$17mid x_2$，从而
$x_1equiv 0 pmod {17}$或$x_1equiv -1pmod {17}$
若$x_nequiv c pmod {59}$，则
$x_n(x_n+1)equiv 0 pmod {59} Longleftrightarrow cequiv 0 pmod {59}$或$cequiv -1 pmod {59}$
而$x(x+1)equiv -1 pmod {59}$无解，故同上可知，$x_1equiv 0$或$-1 pmod {59}$
若$x_1equiv 0 pmod {59}$，$x_1equiv 0 pmod {17}$，从而，$x_1$的最小值为$1003$
若$x_1equiv -1 pmod {59}$，$x_1equiv 0 pmod {17}$，从而，$x_1$的最小值为$15*59-1=884$
若$x_1equiv -1 pmod {17}$，$x_1equiv 0 pmod {59}$，从而，$x_1$的最小值为$118$
若$x_1equiv -1 pmod {17}$，$x_1equiv -1 pmod {59}$，从而，$x_1$的最小值为$1003$
综上所述，$x_1$最小值为$118$
还有很多题目然而我太菜了不会证qwq
热烈欢迎来指错
后面会有各个定理的介绍，正在咕咕中 （LaTeX真TM难打）