第2单元 数学背景.pptVIP

Basic of Basic 数论基础（1） 因数和倍数 素数和合数 最大公因数 模运算 同余 欧拉函数 一次同余式 1 因数和倍数 定义1.1 设 a,m,b为整数，b≠0. 若有一整数m, 使得 a = mb, 则称 b是a的因数; 并称b整除a, 记为b|a 若a=mb,而b既非a又非1,则称b是a的真因数. 例如 12的因子：1，2，3，4，6，12 12的真因子：2，3，4，6 1 因数和倍数 关于整除，显然有下列定理： 定理1.1 ①对所有a, 1|a，a|0，a|a. ② 若a|b且b|c, 则a|c. 例如 3|6,6|12, 则3|12 ③ 若a|b, 则对任意的c, 有ac|bc. ④ 若ac|bc且c≠0, 则a|b. ⑤ 若 a | b且a|c,则对任意的 m,n,有 a|(bm+cn). 2 素数和合数 在正整数中, 1只能被它本身整除. 任何大于1的整数都至少能被1和它本身整除． 定义2.1 一个大于1且只能被1和它本身整除的整数, 称为素数; 否则, 称为合数. 由该定义可知，正整数集合可分三类: 素数、合数和1. 素数常用符号p或p1, p2…,来表示. 2 素数和合数 定义2.2 若正整数a有一因数b,而b又是素数,则称b为a的素因数． 例:12=3×4, 其中3是12的素因数, 而4则不是. 定理2.1 若a是大于1的整数, 则a的大于1的最小因数一定是素数. 定理2.2 正整数n是素数当且仅当它不能被任何整数d整除，其中1d=n1/2 3 最大公因数(greatest common divisor) 定义3 .1：设m,n和d都是正整数,若d|m, d|n, 则称d是m,n的公因（约）数. 在公因数中最大的那一个数, 称为m,n的最大公因数, 记为(m,n). 若gcd(m,n)=1, 称m,n是互素的. 计算最大公因数： gcd(11,77)； gcd(33,77)；gcd(24,36)； gcd(24,25) 3 最大公因数 定理3.1 设a和b都是正整数, 且ab, a=bq+r 0rb 其中q和r都是正整数. 则: ① (a,b)=(b,r) 证明： ①若d|a且d|b, 则d|(a-bq)或d|r. 这即表明: d是a和b的公因数, d必是b和r的公因数. ②若d|b且d|r, 则: d|(bq＋r)或d|a. 这即是说d是b和 r的公因数, d也必是a和b的公因数. 3 最大公因数 ② 若(a,b)=d, 则 (a|d, b|d)=1 证明：假设c=(a/d,b/d). 显然c≥1, 只要再证明c≤1即得c=1. 因为c|(a/d), c|(b/d), 于是a/d=cu, b/d=cv或(cd)u=a, (cd)v=b, 即知d是a和b的公因数, 所以cd≤(a,b), 即cd≤d. 由于d≥1, 可得c≤1, 因此, c=1. 这个定理实际提供一个求解最大公约数的方法 欧几里德算法（求最大公约数） 对任何非负整数a和非负整数b: (a≥b), a=bq+r 0≤r|b| gcd(a,b)=gcd(b,r) =gcd(b，a mod b) 欧几里德算法 定理 (Euclid)欧几里德算法. 设: a≥b＞0, 且: a=bq1+r1, 0＜rl＜b b=r1q2+r2, 0＜r2＜r1 r1=r2q3+r3, 0＜r3＜r2 ……. rn-2=rn-1qn+rn, 0＜rn＜rn-1 rn-1=rnqn+1+0 则(a,b)=rn. 欧几里德算法 证明: 由于: b＞r1＞r2＞…＞rn＞0, 故欧几里德算法中的带余除法必在有限步内得到一个余数是零的等式, 即rn+1=0. 根据定理3．1可知： (a,b)=(b,r1)=…=(rn-1,rn)=rn=(rn,0). 欧几里德算法也称辗转相除法. 欧几里德算法实例 gcd(372,164) = gcd(372 mod 164, 164). 372 mod 164 = 372?164·2 = 372?328= 44 gcd(164,44) = gcd(164 mod 44, 44). 164 mod 44 = 164?44·3 = 164?132 = 32. gcd(44,32) = gcd(44 mod 32, 32) = gcd(12, 32) = gcd(32