前言
小冠军是一个非常有志向的人，他立志解出下面一道题：
小冠军的梦想：证明：方程$x^3+y^3=z^3$没有$xyz\neq 0$的整数解。 然而，现在的小冠军还是一个菜稽，对这道题无从下手。徐冠军老师看到了这一幕，告诉他：在解决这道题目之前，你需要了解有关同余的知识。
同余
定义1：设$m\neq 0$，若$m|(a-b)$，则称$m$为模，$a$同余于$b$模$m$，记作： $$a\equiv b(mod\ m) \tag{1}$$ 说白了，就是$a$除$m$的余数等于$b$除$m$的余数，用带余除法就是说$a=q_1m+r$，$b=q_2m+r$（若无特别说明，数论中变量的值都是整数）。 在(1)式中，若$0\leqslant b<m$，则称$b$是$a$对模$m$的最小非负剩余。若$1\leqslant b\leqslant m$，则称$b$是$a$对模$m$的最小正剩余。若$-\frac{m}{2} < b \leqslant\frac{m}{2}$，则称$b$是$a$对模$m$的绝对最小剩余。 同余有哪些性质呢？ 首先，同余满足交换律，也具有传递性。 其次，模相同的同余式可以相加，也可以相乘，即满足$a\equiv b(mod\ m)\quad c\equiv d(mod\ m)\Rightarrow a+c\equiv b+d(mod\ m)\quad ac\equiv bd(mod\ m)$。
定义2：设$f(x)=a_nx^n+\cdots+a_0$，$g(x)=b_nx^n+\cdots+b_0$是两个整系数多项式，当$a_j\equiv b_j(mod\ m)$，$0\leqslant j \leqslant n$时，称$f(x)$同余于$g(x)$模$m$，记为： $$f(x)\equiv g(x)(mod\ m) \tag{2}$$
性质1：若(2)成立，则对于任意$x\in Z$，均有$f(x)\equiv g(x)(mod\ m)$。
性质2：设$d\geqslant 1$，$d|m$，若(1)成立，则$a\equiv b(mod\ d)$。
性质3：设$d\neq 0$，则同余式(1)等价于$da\equiv db(mod\ |d|m)$。
性质4：$ca\equiv cb(mod\ m)\Leftrightarrow a\equiv b(mod\ \frac{m}{(m,c)})$。
性质5：若$m\geqslant 1$,$(a,m)=1$，则存在$c$使得 $$ca\equiv 1(mod\ m) \tag{3}$$ 这时候，我们称$c$为$a$对模$m$的逆，记作$a^{-1}(mod\ m)$或$a^{-1}$。 证明：由贝祖定理知道存在$x_0$和$y_0$使得$ax_0+my_0=1$，取$c=x_0$，即满足要求。 性质6：同余式组$a\equiv b(mod\ m_j),1\leqslant j\leqslant k$同时成立的充分必要条件是$a\equiv b(mod\ [m_1,\cdots,m_k])$。
同余类与剩余系
定义1：把$Z$分为若干两两不相交的集合，使同一集合中任意两数对模$m$一定同余，每一个这样的集合称为$m$的同余类(剩余类)。 我们用$r\ mod\ m$表示$r$所属的模$m$的同余类。 例如，对$m=3$而言，整数集$Z$可被分成三个两两不相交的集合： $0\ mod\ 3={a|a \ mod\ 0(mod\ 3),a\in Z}$ $1\ mod\ 3={a|a \ mod\ 1(mod\ 3),a\in Z}$ $2\ mod\ 3={a|a \ mod\ 2(mod\ 3),a\in Z}$ 若再向下推，可以轻轻松松得到$0\ mod\ 3=3\ mod\ 3$。于是，我们有$r\ mod\ m=s\ mod\ m\Leftrightarrow r\equiv s(mod\ m)$。
定义2：一组数$y_1,\cdots,y_s$中，对任意$a$有且仅有一个$y_i$使得$y_j\equiv a(mod\ m)$，则称$y_1,\cdots,y_s$为模$m$的完全剩余系，也称剩余系。 例如，对$m=3$而言，在$0\ mod\ 3,1\ mod\ 3,2\ mod\ 3$三个集合中各取一个数，如$6、7、8$，这就是模$3$的完全剩余系。由此我们易得$s=m$。 类似于同余，剩余系也有特殊的： $0,1,\cdots,m-1$是模$m$的最小非负完全剩余系（同理有最大非正完全剩余系）， $1,2,\cdots,m$是模$m$的最小正完全剩余系（同理有最大负完全剩余系）， $-[\frac{m}{2}],\cdots,-[-\frac{m}{2}]-1$是模$m$的绝对最小完全剩余系。
定义3：若$(r,m)=1$，则模$m$的同余类$r\ mod\ m$称为模$m$的既约同余类。 模$m$的所有既约同余类的个数记为$\varphi(m)$，称为欧拉函数。
定义4：对于一组数$z_1,\cdots,z_t$，若$(z_j,m)=1,i\leqslant j\leqslant t$，及对任意$a$，$(a,m)=1$，有且只有一个$z_j$是的$a\equiv z_j(mod\ m)$，则这组数为模$m$的既约剩余系。 例如对$12$而言，它的既约同余类为$1\ mod\ 12,5\ mod\ 12,7\ mod\ 12,11\ mod\ 12$，则$\varphi(12)=4$。 下面介绍一些定理。
定理1：设$m=m_1m_2$，$x^{(1)}_i (1\leqslant i\leqslant m_1)$是模$m_1$的完全剩余系，
$x^{(2)}_j$ 是模$m_2$的完全剩余系，那么$x_{ij}=x^{(1)}_1+m_1x^{(2)}_j$是模$m$的完全剩余系。
证明：
易知$ x_{ij} $中有$m_1m_2=m$个数。
若存在$x_{i1},x_{i2},x_{j1},x_{j2}$，使得 $ x^{(1)}_{i1}+m_1x^{(1)}_{j1} \equiv x_{i_1j_1} \equiv x_{i_2j_2} \equiv x^{(1)}_{i_2}+m_1x^{(1)}_{j_2}(mod\ m_1m_2) $，则必有 $x^{(1)}_{i_1}\equiv x^{(2)}_{i_2}(mod\ m_1)$。
因为$x^{(1)}_{i_1}$和$x^{(2)}_{i_2}$都在模$m_1$的完全剩余系中，所以$x^{(1)}_{i_1}=x^{(2)}_{i_2}$，从而$x^{(1)}_{j_1}\equiv x^{(2)}_{j_2}(mod\ m_2)$。
同理，我们有$x^{(1)}_{j_1}=x^{(2)}_{j_2}$，则$i_1=i_2,j_1=j_2$，即$x_{ij}$中两两对$m$不同余，因此$x_{ij}$是模$m$的完全剩余系。
总结：我们要证明某个集合是模$m$的完全剩余系，有两步： (1) 证明这个集合有$m$个数。 (2) 证明这个集合元素两两不同余。
定理2：设$m=m_1m_2\cdots m_k$，
及$x_{i_1 i_2\cdots i_k}=x^{(1)}_{i_1} + m_1 x^{(2)}_{i_2}+ \cdots +m_1m_2 \cdots m_{k-1}x^{(k)}_{i_k}$,$x^{(j)}_{ij}(i\leqslant j\leqslant k)$是模$m_j$的完全剩余系时，$x_{i_1i_2\cdots i_k}$为模$m$的完全剩余系。
这个定理的证明，若还是使用上述方法，则十分复杂，这里不妨用归纳法证明。
证明：由上面可知当$k=2$时结论成立。设对$k=n(n\geqslant 2)$时结论成立，则$k=n+1$时， 设$\overline{m_n}=m_1m_2\cdots m_n$及$\overline{x}^{(n)}=x^{(1)}+m_1x^{(2)}+\cdots+m_1m_2\cdots m_{n-1}x^{(n)}$，则$$x=\overline{x}^{(n)}+\overline{m_n}x^{(n+1)} \tag{4}$$ 而由归纳假设，我们知$\overline{x}^{(n)}$为$m_n$的完全剩余系，而结合上式(4)和当$k=2$时结论成立，我们知道$\overline{x}^{(n+1)}$为$\overline{m_n}m_{n+1}=\overline{m_{n+1}}$的完全剩余系，即结论对$k=n+1$时成立。证毕。
总结：这里能想到使用数学归纳法的原因： (1)结构相似。 (2)$k$是正整数。
定理3：设$m=m_1m_2$，且$(m_1,m_2)=1$，若$x^{(1)}_i (1\leqslant i\leqslant s)$是模$m_1$的完全剩余系，$x^{(2)}_j(1\leqslant j\leqslant t)$是模$m_2$的完全剩余系，则$x_{ij}=m_2x^{(1)}_i+m_1x^{(2)}_j (1\leqslant i\leqslant s,1\leqslant j\leqslant t)$是$x_{ij}$为模$m$的完全（或既约）剩余系的充分必要条件。
定理4：设$m=m_1m_2\cdots m_k$，$m_1,m_2,\cdots,m_k$两两既约，设$m=m_jM_j(1\leqslant j\leqslant k)$及$x=M_1x^{(1)}+\cdots+M_kx^{(k)}$，则$x$遍历模$m$的完全（或既约）剩余系的充分必要条件是$x^{(1)},\cdots,x^{(k)}$也分别遍历模$m_1,\cdots,m_k$的完全（或既约）剩余系。
这两个定理的证明的思想方法与上面类似，请读者自证。
介绍完了一些定义定理，下面来看看它们的应用。
例题
例1：用模$3$的剩余系表示模$3^n(n\geqslant 2)$的剩余系。 解：看定理2，当$m_1=m_2=\cdots=m_k=n$时，我们得到下面的引论： 当$x^{(1)}$遍历模$m$的完全（既约）剩余系，$x^{(j)}(2\leqslant j\leqslant k)$分别遍历模$n$的完全剩余系时， $$x=x^{(1)}+nx^{(2)}+n^2x^{(3)}+\cdots+n^{k-1}x^{(k)}$$ 遍历模$n^k$的完全（既约）剩余系。 由上我们易知$x=x^{(1)}+3x^{(2)}+3^2x^{(3)}+\cdots+3^{k-1}x^{(k)}$
实际上，上述问题为奥数中一道经典题目：有$n$个质量为$1g$，$3g$，$3^2g$，$\cdots$，$3^{n-1}g$的砝码，可以在天平上测出$1g$到$\frac{3^n-1}{2}g$之间的物体质量（误差小于$1g$）。
例2：求模$13$的一组完全剩余系$r_1,r_2,\cdots,r_13$，满足$r_i\equiv i(mod\ 3)，r_i\equiv 0(mod 7) (1\leqslant i\leqslant 13)$。
解：
设$m_1=3$，$m_2=7$，$m_3=13$，$m=m_1m_2m_3$，则$M_1=91$，$M_2=39$，$M_3=21$。
设$x^{(i)}_i$为模$13$的完全剩余系，$i'$为$i$对模$3$的绝对最小剩余，则
$$r_i=21\cdot x^{(1)}_i+91i'+39\cdot 0(1\leqslant i\leqslant 13)\tag{4}$$
即为我们所要的模$13$的完全剩余系。取$x^{(1)}_i(1\leqslant i\leqslant 13)$依次为$-6,-5,-4,-3,-2,-1,0,1,2,3,4,5,6$，则$r_i$依次为$-35,-196,-84,28,133,-21,91,-70,42,154,-7,105,217$。
那为什么(4)能使得结论成立呢？
设存在$i_1,i_2$使得
$$21x^{(1)}_{i_1}+91i_1'\equiv 21x^{(1)}_{i_2}+91i_2'(mod\ 13)$$
则$x^{(1)}_{i_1}\equiv x^{(1)}_{i_2}(mod\ 13)$，因为它们都在模$13$的一组完全剩余系内，所以$i_1=i_2$，所以$r_i$中两两对模$13$不同余，又因为其中有$13$个数，所以$r_i$是模$13$的一个完全剩余系。
例3：若$m\geqslant 2$，则$m$的最小正既约剩余系之和为$\frac{m\varphi(m)}{2}$。 证明：若$0<r_j<\frac{m}{2}$，$r_j$为$m$的既约剩余类，则$(m-r_j,m)=(-r_j,m)=(r_j,m)=1$。 设$m$的最小正既约剩余系为$r_1,r_2,\cdots,r_{2n}$，其和为$S$， 因为$r_j+r_{2n+1-j}=m$，所以$S=r_1+r_2+\cdots+r_{n-1}+r_n+r_{n+1}+r_{n+2}+\cdots+r_{2n}$ $=(r_1+r_{2n})+(r_2+r_{2n-1})+\cdots+(r_{n-1}+r_{n+2})+(r_n+r_(n+1))$ $=\frac{\varphi(m)}{2}\cdot m$，证毕。
例4：设$p_1,\cdots,p_k$为$k$个不同的素数，则$\varphi(p_1\cdots p_k)=(p_1-1)(p_2-1)\cdots(p_k-1)$。 证明：由容斥原理知 $$\varphi(p_1\cdots p_k)=p_1\cdots p_k-\sum_{1\leqslant j\leqslant k}\frac{p_1\cdots p_k}{p_j}+\sum_{i\leqslant i<j\leqslant k}\frac{p_1\cdots p_k}{p_ip_j}+\cdots+(-1)^n=(p_1-1)(p_2-1)\cdots(p_k-1)$$ 证毕。