1、 算法艺术与信息学竞赛 标准课件数论 (一 ): 概念与应用刘汝佳目录一、基本概念二、进位制三、模算术与方程四、杂题一、基本概念概念 1: 整除关系 整除与约数、倍数 . 注意负数 可整除性的基本性质 若 a|b, a|c, 则 a|(b+c) 若 a|b, 那么对所有整数 c, a|bc 若 a|b, b|c, 则 a|c 整除关系具有传递性 . 它是偏序关系 (partial order), 是一个格概念 2: 素数和合数 如果大于 1的正整数 p仅有的正因子是 1和 p, 则称 p为素数 (prime) 大于 1又不是素数的正整数称为合数(compound) 如果 n是合数 , 则 n必
2、有一个小于或等于 n1/2的素因子定理 1: 算术基本定理 每个正整数都可以惟一地表示成素数的乘积，其中素数因子从小到大依次出现（这里的 “乘积 ”可以有 0个、 1个或多个素因子）。 换句话说 , 任意正整数 n可以写成 n=2a1*3a2*5a3*,其中 a1,a2,a3等为非负整数 这个定理也叫做 惟一分解定理 。它是一个定理而不是公理！虽然在大多人看来，它是 “显然成立 ”的，但它的确是需要证明的定理概念 3: 除法和同余 令 a为整数， d为正整数，那么有惟一的整数 q和 r，其中 0rd，使得 a=dq+r 可以用这个定理来定义除法： d叫除数， a叫被除数， q叫商， r叫余数。
3、如果两个数 a,b除以一个数 c的余数相等，说 a和 b关于模 c同余，记作 ab(mod c) 概念 4: 最大公约数和最小公倍数 令 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 想一想 : 为什么不定义最小公约数和最大公倍数 ?最大公约数的性质 GCD: Greatest Common Divisor 把 a, b写成素数分解式 则 (a,b)的公式为最大公约数的性质 知道了最大公约数 a, b，经常把 a和 b写为a=a1*(a,b), b=b1*(a,b)，则 (a1,b1)=1，称 a1和 b1互素 (relatively prime) GCD满足 分配律 (ma,mb)=m(a,b) 结合律 (a,b,c)=(a,b),c)=(a,(b,c) 幂等律 (a,a)=a 交换律 (a,b)=(b,a) 吸收律 a,(a,b)=a
