1、2005年浙江省队培训第 1讲 数论初步刘汝佳目录一、基本概念二、进位制三、模算术与方程四、杂题一、基本概念基本概念 整除与约数、倍数 . 注意负数 可整除性的基本性质 若 a|b, a|c, 则 a|(b+c) 若 a|b, 那么对所有整数 c, a|bc 若 a|b, b|c, 则 a|c 整除关系具有传递性 . 它是偏序关系 (partial order), 是一个格素数和合数 如果大于 1的正整数 p仅有的正因子是 1和 p, 则称 p为素数 (prime) 大于 1又不是素数的正整数称为合数(compound) 如果 n是合数 , 则 n必有一个小于或等于 n1/2的素因子算术基本定
2、理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的 “乘积 ”可以有 0个、 1个或多个素因子）。 换句话说 , 任意正整数 n可以写成 n=2a1*3a2*5a3*,其中 a1,a2,a3等为非负整数 这个定理也叫做 惟一分解定理 。它是一个定理而不是公理！虽然在大多人看来，它是 “显然成立 ”的，但它的确是需要证明的定理除法和同余 令 a为整数， d为正整数，那么有惟一的整数 q和 r，其中 0rd，使得 a=dq+r 可以用这个定理来定义除法： d叫除数， a叫被除数， q叫商， r叫余数。如果两个数 a,b除以一个数 c的余数相等，说 a和 b关于模 c同
3、余，记作 ab(mod c) 同余 为什么有同余 ? 132412341+432435.2=24.7 余数可以作为原数的一个 signature(标记 ). 如果标记下的运算错误 , 一定错误 如果标记下的运算正确 ?最大公约数和最小公倍数 令 a和 b是不全为 0的两个整数，能使 d|a和d|b的最大整数称为 a和 b的最大公约数，用gcd(a,b)表示，或者记为 (a,b)。 令 a和 b是不全为 0的两个整数，能使 a|d和b|d的最小整数称为 a和 b的最小公倍数，用lcm(a,b)表示，或者记为 a,b 定理 : ab = gcd(a,b) * lcm(a,b)定理的证明 使用惟一分解定理 . 设 则有 : 容易验证定理成立
