13 最大公约数.ppt

定理1. 3. 4 证明: 记 m=[a1 ，a2 ， …，ak ] (必要性) 由M = mq + r (0≤ r m) , M，m 都是a1 ,a2 , …,ak 的公倍数，由带余除法整除性质知，a1 ,a2, …, ak也能整除 r. ∴ r 也是a1, a2, …, ak的公倍数，因为0≤ r m ，所以 r 只能是零, 即r＝0，因此 m | M． 如何用自然语言叙述此定理？你对最小公倍数的“最小”二字有什么新的理解？ (充分性) 充要条件是 3．最大公约数与最小公倍数性质 定理1. 3. 5 定理1. 3. 6 定理1. 3. 7 定理1. 3. 8 与 定理1. 3. 9 定理1. 3. 10 定理1. 3. 11 定理1. 3. 12 本节定理较多，定理1.3.4和1.3.5是对GCD与LCM的本质描述，定理1.3.6是定理1.3.3推论3的推广。 重点掌握定理1.3.6、定理1.3.8与定理1.3.12及推论。 ∴ D 是 a1 ,a2 , …,ak 的公约数 由 (2) 及整除的性质知： d ≤ D . 定理1. 3. 5的充分必要条件是 证明: (充分性证明) ∵ D | ai 即, D 是 a1 ,a2 , …,ak 的公约数中最大的. ∴( a1 ,a2 , …,ak )＝ D （必要性证明） 若( a1 ,a2 , …,ak )= D，由公约数定义知 (1) 成立。同时存在 m1 ,m2 , …,mk 使裴蜀等式 m1a1 + m2a2 + … + mk ak = D 成立。若d | ai , i =1 ,2 , …, k, 则 d | (m1a1 + m2a2 + … + mk ak),即 (2) 成立。定理得证。 由此可知, 几个数的任一公约数一定是 它们最大公约数的约数，最大公约数的约数 就是它们的全体公约数. 定理1. 3. 6  (a1，a2，…，ak) = d的充要条件是 证明： (必要性) 如果 那么 这样 dc 便是a1，a2，…，ak的公约数 这与 d 是最小公约数矛盾，则 定理1. 3. 6 (a1，a2，…，ak) = d的充要条件是 (充分性) 当 　　　　　　　时，若(a1, a2, …, ak) ≠ d， 　　　　　　　　　　　而最大公约数是公约数的倍数，∴ (a1，a2，…，ak)=dh，h1，则有dh | ai， 即 这样h是　　　　　　大于1 故(a1，a2，…，ak)=d，证毕。 的公约数，与　　　　　　　　矛盾。 这个定理相当于定理1.3.6的推论： 定理 1.3.6 是充要条件，即得结论。 k=2即定理1.3.3推论3 定理1. 3. 8 定理1. 3. 9 定理1.3.8与定理1.3.6 具有某种对称性, 它们的证明有相似之处，都要用反证法，留给同学们自学练习。 多个数的最大公约数和最小公倍数 由此表明，多个数的最大公约数、最小公倍数可以由求两个数的最大公约数与最小公倍数逐步求出． 定理1.3.10 定理1.3.11 只证明定理1.3.10的(3) 证: 设 (a1, a2 , …, ak+r) = d1， (a1, a2 , …, ak) = d2. 　(ak+1, ak+2 , …, ak+r) = d3， (d2，d3) = d． 　　∵d1 | ai，(i =1 ,2 , …, k+r), 　　∴ d1 | d2 ， d1 | d3，则d1 | d． 反过来，由 (d2，d3) = d 得 d | d2 ， d | d3 , ∴ d | ai，(i =1, 2, …, k+r), 即, d 是 a1 , a2 , …, ak+r 的公约数, ∴ d | d1． ∵ d , d1 ∈N+ , 由定理1.1.1 (7) 可知 d1 = d． 结论成立． 这里用到的就是：公约数整除最大公约数。 定理1. 3. 12 两个数的最大公约数与最小公倍数的积等于这两个数的积，即　　　 (a，b)× [a，b] = ab 证明 设(a, b) = d, [a, b] = m，则有 即 md = ab，定理得证。 比教材P39上的证明简化多了！请思考这个证明是否严密。 md = ab，定理得证。 例4 已知两个数的最大公约数为8，最小公倍数为64，求这两个数． 解 设这两个数为a，b，由公约数定义, 存在整数t1，t2，使a＝8t1，b=8t2． 因为ab＝(a，b) × [a，b]，所以得 64 t1t2 =8 × 64， t1t2＝8 由定理1. 3. 6的推论 2 可知 (t1，t2) = 1, 所以 t1=