第二章代数基础 陆以勤 2005年3月
第二章 代数基础 陆以勤 2005年3月
一、整数的一些基本性质 1.基本概念 素数 合数 因数（约数） 素因数 0 公约数 最大公约数(greatest common divisor) a,b的最大公约数记为GCD(a,b)或(a,b) ■ 最小公倍数((least common multiple) a,b的最小公倍数记为LCM(a,b)或[a,b]
一、整数的一些基本性质 1. 基本概念 ◼ 素数 ◼ 合数 ◼ 因数（约数） 素因数 公约数 最大公约数（greatest common divisor) a,b的最大公约数记为GCD(a,b) 或(a,b) ◼ 最小公倍数 (least common multiple） a,b的最小公倍数记为LCM(a,b) 或 [a,b]
2.整数的初等运算及性质 加、减、乘、除 定理1。任何正整数a均可唯一地分解为素因数的积。 a=pp22.....om (p1、P2、…pn素数，「1、2、、rn为正整数) 《水浒》 天罡星：36=22×32 地煞星：72=23×32 好汉：108=22×32+23×32=22×32（1+2)=22×33
2. 整数的初等运算及性质 加、减、乘、除 定理1。任何正整数a均可唯一地分解为素因数的积。 a=p1 r1p2 r2……pn rn (p1、p2 、 ……pn素数， r1、r2、……、rn为正整数） 《水浒》 天罡星：36＝2 2 × 3 2 地煞星：72＝2 3 × 3 2 好汉： 108＝2 2 × 3 2 + 23 × 3 2 = 22 × 3 2（1＋2）＝ 2 2 × 3 3
3.欧几里德除法（求最大公约数） 定理2（欧几里德除法）：设b是正整数，则任意大于b的正整数a 可唯一地表示为： a=qb+r0≤r<b 解释：两个正整数相除，商和余数是唯一的。 定理3：a、b为正整数，且a>b,设a=bq+r,则(a,b)=(b,r)。 解释：利用欧几里德除法求最大公约数。 例2.1.求(150,42) 150=3×42+24 42=24+18 24=18+6 18=3×6 (150,42)=(42,24)=(24,18)=(18,6)=6 求(（a,b,c)=(a,b),c
3. 欧几里德除法（求最大公约数） 定理2（欧几里德除法）：设b是正整数，则任意大于b的正整数a 可唯一地表示为： a=qb+r 0r < b 解释：两个正整数相除，商和余数是唯一的。 定理3：a、b为正整数，且a>b, 设a=bq+r, 则(a,b)=(b,r)。 解释：利用欧几里德除法求最大公约数。 例2.1. 求(150,42) 150=342+24 42=24+18 24=18+6 18=3 6 (150,42)=(42,24)=(24,18)=(18,6)=6 求（a,b,c)=((a,b),c)
4.欧几里德算法 定理4：给定任意a、b,(a,b)=Aa+Bb,(A、B为整数)。 解释：两个正整数的最大公约数可表示为它们的线性组合。 如何求？ (150,42) 150=3×42+24 42=24+18 24=18+6 18=3×6 (150,42)=(42,24)=(24,18)=(18,6)=6 (150,42)=24-18=24-(42-24)=2×24-42 =2×(150-3×42)-42 =2×(150-3×42)-42 =2×150-7×42
4. 欧几里德算法 定理4：给定任意a、b， (a,b)=Aa+Bb, (A、B为整数）。 解释：两个正整数的最大公约数可表示为它们的线性组合。 如何求？ (150,42) 150=342+24 42=24+18 24=18+6 18=3 6 (150,42)=(42,24)=(24,18)=(18,6)=6 （150，42）=24-18=24-（42-24）=2 24-42 =2 (150-3 42)-42 =2 (150-3 42)-42 = 2 150- 7 42