EXAMPLE2 数论 定义2设d,a1,a2…,n1(m>=2)是任意整数,若有 da1,da2,…,dlan 则称d是a1a2,…,1a公因子/ common divisor s 若 d是a1a2y…y an的一个公因子,对 a1,a) an的任 个公因子c,存在cd,则称d是a1,a2,21的最大公因子 greatest common divisor,记为(a;a2,,an)。或gcd (a1,a2x…,an)或GCD( 1942。an 2/24/202111:15PM Deren Chen Zhejiang univ
数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 6 EXAMPLE 2 定义2 设d,a1 ,a2 ,…,an (n>=2)是任意整数，若有 d|a1 , d| a2 , … , d| an 则称d是a1 ,a2 ,…,an的公因子/common divisor。 若d是a1 ,a2 ,…,an的一个公因子，对a1 ,a2 ,…,an的任一 个公因子c，存在cd，则称d是a1 ,a2 ,…,an的最大公因子 /greatest common divisor ，记为(a1 ,a2 ,…,an )。或 gcd （ a1 ,a2 ,…,an ）或GCD （ a1 ,a2 ,…,an ）
theorem 3 数论 定理3设a、b∈I且满足 a=b*g+r 这里a>b,0<r<b,则 gcd(a, b )=gcd(b, r) 2/24/202111:15PM Deren Chen Zhejiang univ
数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 7 theorem 3 定理3 设a、bI 且满足 a=b*q+r 这里 ab，0rb，则 gcd(a,b) = gcd(b,r)
Theore 4 数论 定理4任意两个整数都存在最大公因子。 求两个整数的最大公因子的欧几里德算法 ( Euclid,也称辗转相除法)。 设a、b是任意两个整数,a=q;b+r1 i=0、1、2、 2/24/202111:15PM Deren Chen Zhejiang univ
数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 8 Theorem 4 定理4 任意两个整数都存在最大公因子。 求两个整数的最大公因子的欧几里德算法 （Euclid，也称辗转相除法）。 设a、b是任意两个整数， a=qi b+ ri i=0、1、2、…
Example 1 数论 例1:求133和301的最大公因子 k 2 3 3 35 28 7 2/24/202111:15PM Deren Chen Zhejiang univ
数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 9 Example 1 例1：求133 和301 的最大公因子 k 0 1 2 3 4 qk 2 3 1 4 rk 35 28 7 0
Theorem 5 数论 定理5设a、b是正整数,则存在整数s、t,满足 s*a+t*b=ged (a, b) s*t+tb:gcd(a,b的线性组合表达/ linear combination 例2、求gcd(252,198)的线性组合表达。 2/24/202111:15PM Deren Chen Zhejiang univ
数 论 2/24/2021 11:15 PM Deren Chen, Zhejiang Univ. 10 Theorem 5 定理5 设a、b是正整数，则存在整数s、t，满足 s*a + t*b = gcd（a，b） s*t+t*b：gcd(a,b)的线性组合表达/ linear combination 例2、 求gcd(252,198)的线性组合表达