初中数学 01 整数数论
一、整除理论
整除的定义与性质：若整数\(a\)除以非零整数\(b\)，商为整数且余数为零，就说\(b\)整除\(a\)，记作\(b\mid a\)。例如\(6\div3 = 2\)，余数为\(0\)，则\(3\mid6\)。整除具有传递性等性质，即若\(a\mid b\)且\(b\mid c\)，则\(a\mid c\).
最大公因数与最小公倍数：几个整数公有的因数中最大的一个称为最大公因数，记作\((a,b)\)等；公有的倍数中最小的一个称为最小公倍数，记作\([a,b]\)等 。例如\((12,18)=6\)，\([4,6]=12\)，它们之间满足\([a,b]=\frac{ab}{(a,b)}\).
辗转相除法：也叫欧几里得算法，是求两个整数最大公因数的有效方法。通过反复做除法运算，将较大数除以较小数得到余数，再用除数和余数继续做除法，直到余数为\(0\)，此时的除数就是最大公因数。例如求\((48,30)\)，\(48 = 30\times1+18\)，\(30 = 18\times1 + 12\)，\(18 = 12\times1+6\)，\(12 = 6\times2\)，所以\((48,30)=6\).
二、同余理论
同余的定义：设\(m\)是正整数，若整数\(a\)和\(b\)除以\(m\)所得的余数相同，则称\(a\)与\(b\)对模\(m\)同余，记作\(a\equiv b(\bmod m)\)。例如\(17\)和\(5\)除以\(3\)的余数都是\(2\)，所以\(17\equiv5(\bmod3)\).
同余的性质：同余具有自反性\(a\equiv a(\bmod m)\)、对称性若\(a\equiv b(\bmod m)\)则\(b\equiv a(\bmod m)\)、传递性若\(a\equiv b(\bmod m)\)且\(b\equiv c(\bmod m)\)则\(a\equiv c(\bmod m)\)等。同余式还可以进行加、减、乘等运算，如若\(a\equiv b(\bmod m)\)，\(c\equiv d(\bmod m)\)，则\(a+c\equiv b+d(\bmod m)\)，\(ac\equiv bd(\bmod m)\).
剩余系与完全剩余系：对于给定的正整数\(m\)，所有对模\(m\)同余的整数构成一个剩余类，全体剩余类构成的集合称为模\(m\)的剩余系。从每个剩余类中任取一个数组成的集合称为模\(m\)的一个完全剩余系。例如模\(3\)的一个完全剩余系可以是\(\{0,1,2\}\)。
三、素数与合数
素数的定义与性质：一个大于\(1\)的自然数，如果除了\(1\)和它自身外，不能被其他自然数整除的数叫做素数（质数）。素数有无穷多个，这是数论中的一个重要结论。例如\(2\)、\(3\)、\(5\)、\(7\)、\(11\)等都是素数.
合数的定义与性质：一个大于\(1\)的自然数，如果除了\(1\)和它本身还有别的因数，这样的数叫做合数。合数可以分解成若干个素数的乘积，这就是算术基本定理，例如\(4 = 2\times2\)，\(6 = 2\times3\)等.
素数的判定与筛法：判定一个数是否为素数有多种方法，如试除法，即用小于该数的平方根的所有素数去除这个数，若都不能整除则该数为素数。筛法是求一定范围内素数的常用方法，如埃拉托色尼筛法，通过剔除不大于给定数的平方根的所有素数的倍数，剩下的就是素数.
四、不定方程
一次不定方程：形如\(ax + by = c\)（\(a,b,c\)是整数，\(a,b\)不全为\(0\)）的方程是一次不定方程。若\((a,b)\mid c\)，则方程有整数解，并且可以通过扩展欧几里得算法来求解。例如\(3x + 5y = 7\)，因为\((3,5)=1\)且\(1\mid7\)，所以该方程有整数解.
高次不定方程：如费马方程\(x^n + y^n = z^n\)（\(n\geq3\)）等，当\(n = 2\)时就是勾股方程，有许多整数解，如\(3^2 + 4^2 = 5^2\)；而当\(n\geq3\)时，费马大定理指出方程无正整数解，该定理历经多年才被证明.
五、数论函数
欧拉函数：\(\varphi(n)\)表示小于等于\(n\)且与\(n\)互质的正整数的个数。例如\(\varphi(6)=2\)，因为小于等于\(6\)且与\(6\)互质的正整数为\(1\)和\(5\)。欧拉函数具有许多重要的性质，如若\(p\)为素数，则\(\varphi(p)=p - 1\)；若\(n = p^k\)（\(p\)为素数，\(k\)为正整数），则\(\varphi(n)=p^k - p^{k - 1}\)等.
莫比乌斯函数：\(\mu(n)\)是定义在正整数集上的函数，当\(n = 1\)时，\(\mu(1)=1\)；当\(n\)有平方因子时，\(\mu(n)=0\)；当\(n = p_1p_2\cdots p_k\)（\(p_i\)为不同的素数）时，\(\mu(n)=(-1)^k\)。莫比乌斯函数在数论中有重要应用，如莫比乌斯反演公式等。
六、原根与指数
原根的定义：设\(m\)是正整数，\(a\)是整数，若\(a\)模\(m\)的阶等于\(\varphi(m)\)，则称\(a\)是模\(m\)的一个原根。例如，\(2\)是模\(5\)的一个原根，因为\(\varphi(5)=4\)，且\(2^1\equiv2(\bmod5)\)，\(2^2\equiv4(\bmod5)\)，\(2^3\equiv3(\bmod5)\)，\(2^4\equiv1(\bmod5)\)，\(2\)的阶为\(4\)等于\(\varphi(5)\).
指数的概念：若\(a\)是模\(m\)的原根，对于与\(m\)互质的整数\(b\)，存在唯一的整数\(k\)，\(0\leq k<\varphi(m)\)，使得\(b\equiv a^k(\bmod m)\)，则称\(k\)为\(b\)对模\(m\)的以\(a\)为底的指数。原根和指数在密码学等领域有重要应用。
