1、数论天津大学 (tju)1初等数论的概念n 整除性和约数：n 假设 d和 a是整数， d|a（读作 d整除 a），意味着存在某个整数 k，有 a=kd。n 如果 d|a，并且 d0，则称 d是 a的约数。n 每个整数 a都可以被其平凡约数 1和 a整除， a的非平凡约数也成为 a的因子。2初等数论的概念n 素数和和数n 对于某个整数 a1，如果它仅有平凡约束 1和 a则称 p是素数。否则 p是合数。n 可以证明素数有无限多个。n 筛法求素数。3初等数论概念n 除法定理，余数和同模n 除法定理：对任意整数 a和任意正整数 n，存在唯一的整数 q和 r，使得 a=qn+r，其中0rn。n 值 q成
2、为除法的商，值 r=a(mod n)称为除法的余数。n 根据整数模 n所得的余数，可以把整数分成 n个等价类。包含整数的模 n等价类为：an=a+kn| k Z4初等数论的概念n 公约数与最大公约数n d是 a的约数并且也是 b的约数，则 d是 b的公约数。n 两个不同时为 0的整数 a和 b的最大公约数表示为 gcd(a, b)。5初等数论的概念n gcd(a, b) 的性质：n 定理：如果 a， b是不全为 0的任意整数，则 gcd(a, b)是 a与 b的线性组合 ax+by:x,y Z中的最小正元素。n 推论 1：对于任意整数 a， b，如果 d|a并且 d|b，则d|gcd(a, b
3、)。n 推论 2：对于所有整数 a和 b以及任意非负整数 n，gcd(an, bn)=n*gcd(a,b)。n 推论 3：对所有正整数 n， a和 b，如果 n|ab并且gcd(a, n)=1，则 n|b。6初等数论的概念n 互质数：n 如果两个整数 a与 b只有公因数 1，即如果gcd(a, b)=1，则 a与 b称为互质数。n 定理：对任意整数 a， b和 p，如果 gcd(a, p)=1且 gcd(b, p)=1，则 gcd(ab, p) = 1。7初等数论概念n 唯一因子分解n 唯一质因子分解定理：合数 a仅能以一种方式，写成如下的乘积形式：n a=p1e1p2e2prern 其中 pi为素数， p1p2pr，且 ei为正整数。8初等数论基本概念n 例 1：求一个正整数 n的所有约数和。n 把正整数 n分解质因子的乘积，假设结果为 n=p1e1p2e2prer，那么正整数 n的所有因子之和为：n Sum=(1+p1+p12+p1e1)*(1+p2+p22+p2e2) *(1+pr+pr2+prer)9最大公约数n GCD递归定理：对任意非负整数 a和任意正整数 b， gcd(a, b) = gcd(b, a mod b)。10
