Giáo viên h ng d n: Th y Thi nướ ẫ ầ ệ
Nhóm thuy t trình VI: Ti n, Long, Trinh.ế ể
Bài gi ng ả
UCLN VÀ THU T TOÁN -CLITẬ Ơ
I. M c Tiêuụ
•Nh m giúp giáo sinh hi u m t cách h th ng,t ng quát t c => C =>UCLN c a các sằ ể ộ ệ ố ổ ừ Ướ Ư ủ ố
t nhiên(đ n s nguyên). Trong đó trình bày t ph ng pháp tìm UCLN : b ng cách phânự ế ố ừ ươ ằ
tích các s ra th a s nguyên t => đ n thu t toán -clit.(thuy t trình thu t toán -clit mố ừ ố ố ế ậ Ơ ế ậ Ơ ở
r ng và thu t toán -clit tìm UCLN c a hai hay nhi u đa th c).ộ ậ Ơ ủ ề ứ
•Xây d ng h th ng bài t p c ng c .ự ệ ố ậ ủ ố
II. Chu n B ẩ ị
•B ng ph ,th c k , ph n màu.ả ụ ướ ẻ ấ
•Sgk toán 6 t p .ậ
•Đ i s s c p và th c hành gi i toán(Hoàng Kì).ạ ố ơ ấ ự ả
•Lý thuy t s (Nguy n H u Hoan).ế ố ễ ữ
III. N i Dungộ
Ho t đ ng c a GV và HSạ ộ ủ N i Dungộ
Ho t Đ ng 1 : Ki m Tra Bài Cũạ ộ ể
Câu 1:
a. S t nhiên ố ự a chia h t cho s t nhiênế ố ự b
khác 0 khi nào ?.
HS: S t nhiên ố ự a chia h t cho s t nhiênế ố ự b
khác 0 khi t n t i s t nhiên ồ ạ ố ự q sao cho
a= b.q
b, Khi y ấb là gì c aủ a ?.
HS: b là c c a ướ ủ a (a là b i c a ộ ủ b)
c, tìm c c a 4 và 6?ướ ủ
HS : (4)={1;2;4}Ư
(6)={1;2;3;6}Ư
Câu 2:
a, c chung c a hai s Ướ ủ ố a và b là gì ?
HS : c chung c a hai s Ướ ủ ố a và b là c c aướ ủ
hai s đó .ố
GV: c chung c a hai hay nhi u s là cƯớ ủ ề ố ướ
c a t t c các s đó.ủ ấ ả ố
b, tìm C c a 4 và 6 ?Ư ủ
HS : C(4;6)= (4)Ư Ư
I
(6)={1;2}Ư
GV: S nào là s l n nh t trong t p h p cácố ố ớ ấ ậ ợ
c chung c a 4 và 6?ướ ủ
HS: S “2” s l n nh t trong t p h p các cố ố ớ ấ ậ ợ ướ
chung c a 4 và 6.ủ
1. cƯớ :
S t nhiên ố ự a chia h t cho s t nhiênế ố ự b
khác 0 khi t n t i s t nhiên ồ ạ ố ự q sao cho
• a= b.q (b là c c a ướ ủ a )
(4)={1;2;4}Ư
(6)={1;2;3;6}Ư
2, Ưc chung c a hai hay nhi u s là cớ ủ ề ố ướ
c a t t c các s đó.ủ ấ ả ố
C(4;6)= (4)Ư Ư
I
(6)={1;2}Ư
GV: S “2” đ c g i là gì ? chúng ta cùng điố ượ ọ
qua bài h c hôm nay đ tìm đáp án cho câu h iọ ể ỏ
này.
Ho t đ ng 2: Tìm CLN B ng Cách Phân Tích Các S Ra Th a S Nguyên Tạ ộ Ư ằ ố ừ ố ố
1. CLNƯ
Vd1: T câu 2 ta có : C(4;6)={1;2}ừ Ư
•2 là C c a 4 và 6Ư ủ
•2 là s l n nh t trong t p các c chungố ớ ấ ậ ướ
c a 4 và 6.ủ
Số 2 đ c g i là c chung l n nh t c a 4ượ ọ ướ ớ ấ ủ
và 6 . KH : CLN(4;6)Ư
Vd2: CLN(8,12) = ?Ư
GV h ng d n:ướ ẫ
•B1: tìm C(8,12)Ư
•B2: S nào là s l n nh t trong t pố ố ớ ấ ậ
h p các c chung c a 8 và 12?ợ ướ ủ
HS: B1: C(8,12)={1;2;4}Ư
B2: S “4” là s l n nh t trong t p h pố ố ớ ấ ậ ợ
các c chung c a 8 và 12.ướ ủ
V y CLN(8,12)= 4.ậ Ư
Vd3: CLN(36;84;168) = ?Ư
GV h ng d n : ướ ẫ
•Đ tìm C(36;84;168) thì ta ph iể Ư ả
li t kê t ng (36); (84); (168)ệ ừ Ư Ư Ư
thì r t lâu và khó. ấ
•Đó là cách tìm c chung theo đ nhướ ị
nghĩa (li t kê t ng c=> tìm cệ ừ ướ ướ
chung=>l y s l n nh t).ấ ố ớ ấ
•Có ph ng pháp nào giúp ta tìmươ
CLN c a nhi u s có giá tr t ngƯ ủ ề ố ị ươ
đ i l n m t cách d dàng ! (kh cố ớ ộ ễ ắ
ph c h n ch li t kê t ng c).ụ ạ ế ệ ừ ướ
2.Tìm CLN b ng cách phân tích các sƯ ằ ố
ra th a s nguyên từ ố ố
? Phân tích m t s t nhiên l n h n 1 ra th aộ ố ự ớ ơ ừ
s nguyên t là gì?ố ố
HS: Phân tích m t s t nhiên l n h n 1 raộ ố ự ớ ơ
th a s nguyên t là: vi t s đó d i d ng tíchừ ố ố ế ố ướ ạ
các th a s nguyên t .ừ ố ố
Vd1: Phân tích s 30 ra th a s nguyên t ?ồ ừ ố ố
HS : 30= 2.3.5
Vd1 (Vd3 ph n 1): CLN(36;84;168) = ?ầ Ư
GV h ng d n : ướ ẫ
B1 :Phân tích 3 s đó ra th a s nguyên tố ừ ố ố
•36= ?
•84=?
•168=?
HS: 36= 2.2.3.3 = 22.32
84= 2.2.3.7 = 22.3.7
168= 2.2.2.3.7 = 23.3.7
B2 : Ch n các th a s chung l y s mũ nhọ ừ ố ấ ố ỏ
nh t ?ấ
1. CLNƯ
CLN c a hai hay nhi u s là s l n nh tƯ ủ ề ố ố ớ ấ
trong t p h p các c chung c a các s đó.ậ ợ ướ ủ ố
Nh n Xétậ :
•T t c các c chung c a 4 vàấ ả ướ ủ
6(là1;2) đ u là c c aề ướ ủ
CLN(4;6). Ư
•V y đ tìm các c chung c a các sậ ể ướ ủ ố
đã cho thì ta tìm c c a “ CLN c aướ ủ Ư ủ
các s đó”.ố
Vd 2: CLN(8,12) = ?Ư
B1: C(8,12)={1;2;4}Ư
B2: S “4” là s l n nh t trong t p h pố ố ớ ấ ậ ợ
các c chung c a 8 và 12.ướ ủ
V y CLN(8,12)= 4.ậ Ư
2. Tìm CLN b ng cách phân tích cácƯ ằ
s ra th a s nguyên tố ừ ố ố
a, phân tích m t s t nhiên l n h n 1 raộ ố ự ớ ơ
th a s nguyên t là: vi t s đó d i d ngừ ố ố ế ố ướ ạ
tích các th a s nguyên t .ừ ố ố
Vd1: 30= 2.3.5
Quy t c: Mu n tìm CLN c a hai hayắ ố Ư ủ
nhi u s l n h n 1, ta th c 3 b c :ề ố ớ ơ ự ướ
B1 :Phân tích m i s đó ra th a s nguyênỗ ố ừ ố
t .ố
B2 : Ch n các th a s chung l y s mũ nhọ ừ ố ấ ố ỏ
nh t.ấ
B3 : L p tích các th a s đã ch n ,m i th aậ ừ ố ọ ỗ ừ
s l y v i s mũ nh nh t c a nó.Tích đó làố ấ ớ ố ỏ ấ ủ
Ho t đ ng 3 :Thu t Toán -clitạ ộ ậ Ơ
1. Thu t Toán -clitậ Ơ
Vd1(Vd3 ph n 2): CLN(396;378) = ?ầ Ư
Ta có : 396 = 378.(…)+ (…) ?
HS: 396 = 378.1+ 18
Theo b đ 2ổ ề ta đ c:ượ
•CLN(396;378) = CLN(…;...) ?Ư Ư
(*)
HS: CLN(396;378) = CLN(378;18) (*)Ư Ư
Ta có : 378 = 18.(…) + (…) ?
HS: 378 = 18.21 + 0
Theo b đ 1ổ ề :
•CLN(378;18) = … ? (**)Ư
HS: CLN(378;18) = 18 (**)Ư
V y t (*) và (**) ta có: … = …ậ ừ
HS: V y t (*) và (**) ta có:ậ ừ
CLN(396;378) = 18.Ư
Vd2: CLN(126;51) = ?Ư
Áp d ng theo t ng b c c a thu t toán Oclit.ụ ừ ướ ủ ậ
HS:
•B1 : Ta có 126 = 51.2 + 24
Vì 24
0 nên
CLN(126;51)= CLN(51;24)Ư Ư
•B2; 51 = 24.2 + 3
Vì 3
0 nên
CLN(126;51)= CLN(51;24)= CLN(24;3)Ư Ư Ư
•B3; 24 = 3.8 + 0
V y :ậ
CLN(126;51)= CLN(51;24)= CLN(24;3)=Ư Ư Ư
3
GV h ng d n cách ghi sau:ướ ẫ
126 51
51 24 2
24 3 2
0 8
Vd3: a, CLN(57;38) = ?Ư
323 57
57 38 5
1. Thu t Toán -clitậ Ơ
Đ nh lí : ị
∃
CLN(a;b) Ư
∀
a, b
Z*.
V i hai s nguyên a,b khác 0 ta cóớ ố
CLN(a;b) = CLN(|a|;|b|) Ư Ư nên ta có th giể ả
thi t a>0,b>0 và a>b.ế
a, B đ 1ổ ề : CLN(a;b) = b n u aƯ ế
M
b .
Vd : CLN(12;48) = 1Ư2.
b, B đ 2 ổ ề : n u a = bq + r , 0ế
r < b thì
CLN(a;b) = CLN(b;r) Ư Ư
Thu t Toán :ậ cho a,b là 2 s nguyên (a >ố
b > 0) tìm s t nhiên d = ố ự CLN(a;b) Ư
Th c hi n phép chia có d :ự ệ ư
a = bq + r (*) 0
r < b
Đ tặ: a = ro , b= r1 , r = r2 , q = q1 khi đó (*) trở
thành:
ro = r1.q1 + r2 (0
r2 <r1)
B1: N u rế2 = 0 (hay a
M
b) theo b đ 1 taổ ề
đ c: ượ
d= CLN(a;b) = CLN(Ư Ư ro ;r1) = r1 = b .
K t thúcế
B2: N u rế2
0 (hay a
M
b) theo b đ 2 taổ ề
đ c: ượ
d= CLN(a;b)= CLN(Ư Ư ro ;r1) =CLN(Ưr1; r2)
Th c hi n phép chia có d :ự ệ ư
r1 = r2.q2 + r3 (0
r3 <r2)
B3: N u rế3 = 0 thì d = r2
K t thúc.ế
B4: N u rế3
0 quay l i ạB2 ……
Th c hi n liên ti p quá trình này ta đ c dãyự ệ ế ượ
gi m nghiêm ng t nh ng s t nhiên:ả ặ ữ ố ự
r1 > r2 > r3 ………….
0
Quá trình trên ph i k t thúc, không quá b b cả ế ướ
(
∃
n <= b sa o cho rn-1 = rn.qn)
d= CLN(a;b)= CLN(Ư Ư ro ;r1) =CLN(Ưr1; r2)
………. = CLN(Ưrn-1 ;rn) .
H Qu ệ ả : N u d = CLN(a;b) ế Ư
∃
x,y
Z
sao cho d = a.x + b.y.
Khi d = 1 thì a,b nguyên t cùng nhauố
Vd2: CLN(126;51) = ?Ư
•B1 : Ta có 126 = 51.2 + 24
Vì 24
0 nên CLN(126;51)= CLN(51;24)Ư Ư
38 19 1
0 2
CLN(323;57) = Ư19 .
b, Tìm x,y
Z sao cho 19 = 323.x + 57.y ?
GV h ng d n :ướ ẫ
T thu t toán -clit ta suy ra đ c m t thu từ ậ Ơ ượ ộ ậ
toán cho phép tìm đ ng th i d = CLN(a;b)ồ ờ Ư
và c p s x,yặ ố
Z sao cho d =a.x + b.y.Đ cượ
g i là ọthu t toán -clit m r ngậ Ơ ở ộ .
2 Thu t Toán -clit m r ngậ Ơ ở ộ
Vd1 (Vd3 b):
Tìm x,y
Z sao cho 19 = 323.x + 57.y ?
•B2; 51 = 24.2 + 3
Vì 3
0 nên
CLN(126;51)= CLN(51;24)= CLN(24;3)Ư Ư Ư
•B3; 24 = 3.8 + 0
V y :ậ
CLN(126;51)= CLN(51;24)= CLN(24;3)=Ư Ư Ư
3
2. Thu t Toán -clit m r ngậ Ơ ở ộ
Tìm công th c c a xứ ủ k ,yk sao cho t ng b cở ừ ướ
c a thu t toán -clit x y ra đ ng th c :ủ ậ Ơ ả ẳ ứ
rk = a.xk + b.yk (*)
Vì: r0 = a = a.1+ b.0 nên l y xấ0= 1, y0 =0
r1 = b = a.0+ b.1 nên l y xấ0= 0, y0 =1
Gi s tính đ c xả ử ượ k-2 , yk-2 và xk-1, yk-1 thì :
•xk= xk-2 - xk-1.qk-1
•yk= yk-2 - yk-1.qk-1 (2
k
n)
Khi thu t toán k t thúc thì rậ ế n+1 =0 và d = rn .
(*) tr thành : rởn = a.xn + b.yn
V i :ớ xn= xn-2 – xn-1.qn-1
yn= yn-2 – yn-1.qn-1
V y: ậ d = rn và x = xn ,y = yn
d = CLN(a;b) và d =a.x + b.y Ư
i q r0r1r2x0x1x2y0y1y2
0 5 323 57 38 1 0 1 0 1 -5
1 1 57 38 19 0 1 -1 1 -5 6
2 2 38 19 0 1 -1 -5 6
Vd2 :Tìm x,y
Z sao cho d = 41.x + 24.y
V i d = CLN(41;24) ? ớ Ư
i q r0r1r2x0x1x2y0y1y2
0 1 41 24 17 1 0 1 0 1 -1
1 1 24 17 7 0 1 -1 1 -1 2
2 2 17 7 3 1 -1 3 -1 2 -5
3 2 7 3 1-1 3 -7 2 -5 12
4 3 3 10 3 -7 -5 12
CLN(41;24) = 1 và 1 = 41.(-7) + 24.12Ư