数论基础：整除性、素数与同余

"数论初步" 数论是数学的一个分支，主要研究整数的性质及其相互关系。本文档是2005年浙江省队培训的第一讲，由刘汝佳主讲，涵盖了数论的基本概念、进位制、模算术与方程以及一些混合题目。 首先，讲解了整除和约数、倍数的概念。整除是指一个整数a可以被另一个整数b无余数地除尽，此时我们说a能被b整除，记作a|b。关于整除，有三个基本性质：如果a|b且a|c，那么a|(b+c)；若a|b，对所有整数c，有a|bc；如果a|b且b|c，则a|c。整除关系构成偏序关系，形成一个格结构。 接下来，介绍了素数和合数的概念。素数是只有1和自身两个正因子的正整数，例如2、3、5等。合数则是除了1和自身之外还有其他正因子的正整数。如果n是合数，那么n必然有一个小于或等于n平方根的素因子。素数在数论中扮演着基础角色，因为每个正整数都能唯一地分解为素数的乘积，这就是著名的算术基本定理，也称为惟一分解定理。这个定理表明，比如12可以表示为2^2 * 3^1，且这种分解是唯一的。 文档还涉及了除法和同余的概念。除法定理指出，对于任何整数a和正整数d，存在唯一整数q和r（0≤r<d），使得a=dq+r。同余是整数除法的延伸，如果a和b除以c的余数相同，我们就说a和b模c同余，记作a≡b(modc)。同余在计算和简化问题中非常有用，因为它允许我们将问题转化为更简单的形式。 最大公约数(gcd)和最小公倍数(lcm)是数论中的重要概念。gcd(a,b)是能同时整除a和b的最大整数，而lcm(a,b)是能同时被a和b整除的最小整数。两者之间存在关系：ab=gcd(a,b)*lcm(a,b)，这个定理可以通过惟一分解定理进行证明。 数论初步涉及的这些概念和定理是解决数论问题的基础，对于理解整数性质和解决相关数学竞赛问题至关重要。通过深入学习和掌握这些知识，可以为更高层次的数论研究打下坚实基础。