Lý thuyết số về thuật toán Oclit

Chia sẻ: Nguyễn Văn Cường | Ngày: | Loại File: DOC | Số trang:7

Thêm vào BST

Báo xấu

1.225
lượt xem 80
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

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ố.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Lý thuyết số về thuật toán Oclit

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ũ 1.Ước: Câu 1: a. Số tự nhiên a chia hết cho số tự nhiên b Số tự nhiên a chia hết cho số tự nhiên b khác 0 khi nào ?. khác 0 khi tồn tại số tự nhiên q sao cho HS: Số tự nhiên a chia hết cho số tự nhiên b (b là ước của a ) a= b.q • 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 ?. Ư(4)={1;2;4} HS: b là ước của a (a là bội của b) Ư(6)={1;2;3;6} c, tìm ước của 4 và 6? HS : Ư(4)={1;2;4} 2, Ước chung của hai hay nhiều số là ước Ư(6)={1;2;3;6} của tất cả các số đó. Câu 2: ƯC(4;6)=Ư(4) I Ư(6)={1;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.
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 1.ƯCLN Vd1: Từ câu 2 ta có : ƯC(4;6)={1;2} Ư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ố đó. • 2 là ƯC của 4 và 6 • 2 là số lớn nhất trong tập các ước chung Nhận Xét : của 4 và 6. • Tất cả các ước chung của 4 và Số 2 được gọi là ước chung lớn nhất của 4 6(là1;2) đều là ước của và 6 . KH :ƯCLN(4;6) ƯCLN(4;6). Vd2: ƯCLN(8,12) = ? • Vậy để tìm các ước chung của các số GV hướng dẫn: đã cho thì ta tìm ước của “ƯCLN của • B1: tìm ƯC(8,12) các số đó”. • B2: Số nào là số lớn nhất trong tập hợp các ước chung của 8 và 12? Vd 2: ƯCLN(8,12) = ? HS: B1: ƯC(8,12)={1;2;4} B1: ƯC(8,12)={1;2;4} B2: Số “4” là số lớn nhất trong tập hợp B2: Số “4” là số lớn nhất trong tập hợp các ước chung của 8 và 12. các ước chung của 8 và 12. Vậy ƯCLN(8,12)= 4. 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ố 2. Tìm ƯCLN bằng cách phân tích các ra thừa số nguyên tố 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 a, phân tích một số tự nhiên lớn hơn 1 ra số nguyên tố là gì? thừa số nguyên tố là: viết số đó dưới dạng HS: Phân tích một số tự nhiên lớn hơn 1 ra tích các thừa số nguyên tố. thừa số nguyên tố là: viết số đó dưới dạng tích Vd1: 30= 2.3.5 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ố Quy tắc: Muốn tìm ƯCLN của hai hay • 36= ? nhiều số lớn hơn 1, ta thực 3 bước : • 84=? B1 :Phân tích mỗi số đó ra thừa số nguyên • 168=? tố. HS: 36= 2.2.3.3 = 22.32 B2 : Chọn các thừa số chung lấy số mũ nhỏ 84= 2.2.3.7 = 22.3.7 nhất. 168= 2.2.2.3.7 = 23.3.7 B3 : Lập tích các thừa số đã chọn ,mỗi thừa B2 : Chọn các thừa số chung lấy số mũ nhỏ số lấy với số mũ nhỏ nhất của nó.Tích đó là nhất ?
Hoạt động 3 :Thuật Toán Ơ-clit 1. Thuật Toán Ơ-clit 1. Thuật Toán Ơ-clit Định lí : ∃ ƯCLN(a;b) ∀ a, b Z*. Vd1(Vd3 phần 2): ƯCLN(396;378) = ?  Với hai số nguyên a,b khác 0 ta có Ta có : 396 = 378.(…)+ (…) ? ƯCLN(a;b) = ƯCLN(|a|;|b|) nên ta có thể giả HS: 396 = 378.1+ 18 Theo bổ đề 2 ta được: thiết a>0,b>0 và a>b. • ƯCLN(396;378) = ƯCLN(…;...) ? a, Bổ đề 1: ƯCLN(a;b) = b nếu a Mb . Vd :ƯCLN(12;48) = 12. (*) HS: ƯCLN(396;378) = ƯCLN(378;18) (*) b, Bổ đề 2 : nếu a = bq + r , 0 r < b thì ƯCLN(a;b) = ƯCLN(b;r) Ta có : 378 = 18.(…) + (…) ? HS: 378 = 18.21 + 0  Thuật Toán : cho a,b là 2 số nguyên (a > Theo bổ đề 1 : b > 0) tìm số tự nhiên d = ƯCLN(a;b) • ƯCLN(378;18) = … ? (**) Thực hiện phép chia có dư: HS: ƯCLN(378;18) = 18 (**) a = bq + r (*) 0 r< b Vậy từ (*) và (**) ta có: … = … Đặt: a = ro , b= r1 , r = r2 , q = q1 khi đó (*) trở HS: Vậy từ (*) và (**) ta có: thành: ƯCLN(396;378) = 18. ro = r1.q1 + r2 (0 r2 r3 …………. 0 126 51 Quá trình trên phải kết thúc, không quá b bước ( ∃ n
B2; 51 = 24.2 + 3 19 • 38 1 Vì 3 0 nên ƯCLN(126;51)=ƯCLN(51;24)=ƯCLN(24;3) 0 2 • B3; 24 = 3.8 + 0 ƯCLN(323;57) = 19 . Vậy : b, Tìm x,y Z sao cho 19 = 323.x + 57.y ? ƯCLN(126;51)=ƯCLN(51;24)=ƯCLN(24;3)= GV hướng dẫn : 3 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): 2. Thuật Toán Ơ-clit mở rộng Tìm x,y Z sao cho 19 = 323.x + 57.y ? Tìm công thức của xk ,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 x0= 1, y0 =0 r1 = b = a.0+ b.1 nên lấy x0= 0, y0 =1 Giả sử tính được xk-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ì rn+1 =0 và d = rn . (*) trở thành : rn = 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 r0 r1 r2 x0 x1 x2 y0 y1 y2 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 r0 r1 r2 x0 x1 x2 y0 y1 y2 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 1 0 3 -7 -5 12 ƯCLN(41;24) = 1 và 1 = 41.(-7) + 24.12
Vd3 : ƯCLN(f(x);g(x)) = ? f(x) = x4 – 4x3 + 3x2 + 4x – 4 và g(x) = x4 – 4x3 + 5x2 – 2x GV hướng dẫn : để tìm ƯCLN của 2 đa thức ta có thể dùng thuật toán Ơ-clit như tìm ƯCLN của hai số nguyên không ? 3Thuật Toán Ơ-clit tìm ƯCLN của đa 3Thuật Toán Ơ-clit tìm ƯCLN của đa thức thức • Định lí 1. Đối với hai đa thức khác không Để tìm UCLN của hai đa thức, ta dùng thuật toán f(x) và g(x) của P(x) luôn tồn tại và duy nhất giống như thuật toán Ơclit để tìm UCLN của hai UCLN của chúng. số nguyên. Vì UCLN của hai số nguyên là 1 trường Giả sử f(x) và g(x) là hai đa thức trên trường số hợp đặc biệt của UCLN của hai đa thức, khi hai đa P. Ta gọi đa thức h(x) là ước chung của f(x) và thức chỉ có hạng tử tự do. g(x) nếu f(x) và g(x) đều chia hết cho h(x). Vd1 (Vd3 phần 2): ƯCLN(f(x);g(x)) = ? f(x) Đa thức d(x) P[x] được gọi là ước chung lớn = x4 – 4x3 + 3x2 + 4x – 4 và g(x) = x4 – 4x3 + 5x2 nhất (UCLN) của f(x) và g(x), kí hiệu là: d(x) = – 2x UCLN(f(x), g(x))nếu: a) d(x) là ước chung của f(x) và g(x). b) d(x) chia hết cho mọi ước chung của f(x) và g(x). c) hệ số cao nhất của d(x) bằng 1. Hai đa thức f(x) và g(x) được gọi là nguyên tố cùng nhau nếuUCLN(f(x), g(x)) = 1 • Định lí 2. Giả sử (f(x), g(x)) = d(x), khi đó tồn tại các đa thức u(x) và v(x) sao cho: f(x).u(x) + g(x).v(x) = d(x) Hoạt động 4 : Củng Cố Bài tập 1: Tìm x là số tự nhiên lớn nhất sao cho: 72 Mx ; 48Mx a,Theo cách phân tích các số ra tích các thừa số nguyên tố b,Theo thuật toán Ơ-clit Hướng dẫn : ta có 72 Mx theo định nghĩa thì x là ….của 72 ? 48Mx theo định nghĩa thì x là ….của 48 ? Ta lại có đề bài cho “x là số tự nhiên lớn nhất” Vậy: x là gì của 72 và 48 ? Bài tập 2: Môt căn phòng tắm có kích thước nền là 4,2(m) x 2,8(m). Tìm kích thước viên gạch nát nền hình vuông sao cho vừa vặn lát kín căn phòng (không phải xẻ thêm viên nào để chèn vào chỗ còn thừa) và số lượng viên gạch là ít nhất. Hướng dẫn : Gọi x là cạnh viên gạch hình vuông cần tìm. Để thuận lợ cho quá trình tính toán , đổi : 4,2m =….cm ? 2,8m =….cm ?
Vì : Viên gạch nát nền hình vuông sao cho vừa vặn lát kín căn phòng thì …………. Số lượng viên gạch là ít nhất nên…………… Bài 3: Tìm x,y Z sao cho d = 204.x + 63.y .Với d = ƯCLN(204;63) ? Bài 4: Tìm ƯCLN của các đa thức f(x) = x4 +4x3 – 3x2 – 4x – 1 và g(x) = x3 + x2 – x–1