Sáng kiến kinh nghiệm về số nguyên tố

Số nguyên tố được nghiên cứu từ nhiều thế kỷ trước công nguyên, nhưng cho đến nay nhiều bài toán về số nguyên tố vẫn chưa được giải quyết trọn vẹn, các nhà toán học cũng chưa tìm được một dạng tổng quát của số nguyên tố, vì thế mà việc nhận biết một số có là số nguyên tố hay không thì cũng rất phức tạp. Nhưng việc sử dụng các số nguyên tố trong số học thì lại rất cần thiết, đặc biệt trong việc bồi dưỡng học sinh giỏi. Qua tham khảo, học hỏi và thử nghiệm tôi có một số khái quát về số nguyên tố và ứng dụng của nó trong việc bồi dưỡng học sinh giỏi. Rất mong được sự tham khảo, góp ý của các đồng nghiệp. A : Nội dung I) Khái niệm về số nguyên tố. 1.Định nghĩa : Số nguyên tố là số tự nhiên lớn hơn 1 và chỉ có hai ước là 1 và chính nó Hợp số là số tự nhiên lớn hơn 1 và có nhiều hơn 2 ước Số tự nhiên lớn hơn 1 nếu không là số nguyên tố thì số đó là hợp số. N = { 0; 1 } U P U A Trong đó P là tập hợp các số nguyên tố , A là tập hợp các hợp các hợp số * Nhận xét: + p là số nguyên tố p > 1; q\ p q = 1 hoặc q = p + a là hợp số a > 1 và q sao cho q\a ; 1< q < a + Số 2 là số nguyên tố chẵn duy nhất, mọi số nguyên tố lớn hơn 2 đều là số lẻ Dựa vào các nhận xét trên, học sinh dễ dàng nhận biết được một số là số nguyên tố hay hợp số trong một số trường hợp đơn giản. Ví dụ : Chứng tỏ rằng các số sau là hợp số a) A = 31111411111 b) B = 7.9.11.13.15 -17 c) C = 7.19.23.29 - 14 *Hướng dẫn giải A=31111411111 =31111100000 +311111 = 311111 ( 100000 + 1 ) = 311111 . 100001 A 311111 , mà A > 311111 A là hợp số B = 7.9.11.13.15 - 17 Ta có tích 7.9.11.13.15 là một số lẻ B =7.9.11.13.15 - 17 là một số chẵn , mà B > 2 B là hợp số c ) C = 7.19.23.29 - 14 Ta chứng minh C 7 mà C > 7 C là hợp số 2. Mệnh đề: Ước nhỏ nhất khác 1 của một số tự nhiên lớn hơn 1 là một số nguyên tố. Chứng minh: Giả sử a N; a > 1; p là ước nhỏ nhất khác 1 của a; p > 1 ta chứng minh p là số nguyên tố. Giả sử p không là số nguyên tố p là hợp số q N sao cho 1 < q < p; q\p mà p\a q\a. Vậy q; 1 < q < p; q\a trái với giả thiết p là ước nhỏ nhất khác 1 của a vậy p phải là số nguyên tố. * Hệ quả: Mọi số tự nhiên lớn hơn 1 đều có ít nhất 1 ước nguyên tố 3. Định lý Ơclít: Có vô số số nguyên tố. Chứng minh: Tồn tại số nguyên tố khác n số nguyên tố đã cho Giả sử P1; P2 ; ....; Pn là n số nguyên tố đã biết Xét số A = P1 . P2 ... Pn + 1 > 1 Suy ra tồn tại số nguyên tố P sao cho P là ước của A + Nếu P = Pi; i = 1;2;...; n Suy ra P\P1P2 ...Pn Mà P\ A suy ra P\1 ( Điều này vô lý) vì P phải là số nguyên tố Vậy P Pi. Do đó tồn tại số nguyên tố khác n số nguyên tố đã cho. Vậy có vô số số nguyên tố hay tập các số nguyên tố là tập vô hạn iI) Sàng Ơratôxten: ( Thuật toán tìm tất cả các số nguyên tố không vượt quá một số tự nhiên n nào đó) 1. Bổ đề: Mỗi hợp số a đều có ít nhất một ước nguyên tố nhỏ hơn hoặc bằng . Chứng minh: Giả sử P là ước nhỏ nhất khác 1 của a P là số nguyên tố. P\a a = P . q q\a ; q > 1 ( vì nếu q = 1 a = P, điều này vô lý vì a là hợp số còn P là số nguyên tố ) Vậy q P a = P.q P2 P ( Điều cần chứng minh) * Hệ quả : Nêú số tự nhiên n > 1 không có ước nguyên tố nào từ 2 đến căn bậc hai của n thì n là một số nguyên tố Ví dụ: Số 113 có là số nguyên tố hay không Các số nguyên tố nhỏ hơn hoặc bằng là 2; 3; 5; 7 113 không chia hết cho 2 hoặc 3 hoặc 5 hoặc 7 vậy 113 không là số nguyên tố 2. Sàng Ơratôxten: Cách tìm tất cả các số nguyên tố trong một khoảng nào đó. + Ta biết các số tự nhiên từ 1 đến n rồi gạch đi những số không phải là số nguyên tố thì các số còn lại là số nguyên tố. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .... - Gạch số 1 - Số 2 là số nguyên tố gạch các bội của 2 - Số đầu tiên không bị gạch là số 3 số 3 là số nguyên tố; gạch các bội của 3 - Số 5 là số đầu tiên không bị gạch ( sau bước 2) số 5 là số nguyên tố; gạch các bội của 5 .... Sau khi gạch các bội của số nguyên tố lớn nhất, nhỏ hơn thì tất cả các số còn lại đều là số nguyên tố. * Nhà toán học cổ Hy Lạp Ơratôxten là người đầu tiên tìm ra cách này. Ông viết các số lên giấy cỏ sậy căng trên một cái khung rồi dùi thủng các hợp số được một vật tương tự như cái sàng; các số không phải là số nguyên tố thì được qua sàng, còn các số nguyên tố thì được giữ lại. III) Định lý cơ bản 1. Bổ đề: Cho p là một số nguyên tố thì a) Với mọi số tự nhiên a thì a p hoặc ( a; p) = 1 b) Nếu p\a.b thì p\a hoặc p\b Chứng minh: a) Xét ( a;p) = 1 hoặc p Nếu ( a;p) = 1 Điều cần chứng minh Nếu (a;p) = p a p Vậy với mọi số tự nhiên a thì a p hoặc ( a; p) = 1 b) p\a.b + Nếu p không chia hết a (a;p) = 1 p\b vậy Nếu p\a.b thì p\a hoặc p\b * Mở rộng: p\a1a2... an ai; i { 1; 2; ...: n } sao cho p\ai ; i{1;2;...; n} 2. Định lý cơ bản: Mọi số tự nhiên a lớn hơn 1 đều phân tích được thành tích các thừa số nguyên tố và sự phân tích đó là duy nhất nếu không kể đến thứ tự. Chứng minh: * Chứng minh tồn tại sự phân tích + Vì a>1 P1 nguyên tố; P1\a a = P1. a1 Nếu a1 = 1 a = P1 là sự phân tích Nếu a1 > 1 P2 nguyên tố ; P2\a1 a1 = p2 a2 Nếu a2 = 1 a = P1 P2 là sự phân tích Nếu a2> 1 ta lại lặp lại như trên ........... Quá trình trên dừng lại sau hữu hạn bước vì có dãy a > a1 > a2 > ... Mà dãy a1 ; a2 ; ... là dãy số tự nhiên giảm dần nên đến bước thứ n nào đó phải có an = 1 nên khi đó a = P1 P2 ... Pn * Chứng minh tính duy nhất Giả sử có 2 sự phân tích là a = P1P2... Pn và a = q1q2... qm Ta chứng minh n = m và Pi = qi với i = 1; 2; ...; n P1P2... Pn = q1q2 ... qm q1\P1P2...Pn q1\P1 P1 = q1 vì P1; q1 là các số nguyên tố P1 = q1 P2P3...Pn= q2q3...qm Lập lại lập luận trên, suy ra P2 = q2 Lập luận trên có thể tiếp tục cho đến khi một trong hai vế không còn thừa số nguyên tố nào, nhưng khi đó vế kia cũng hết thừa số nguyên tố vì ngược lại sẽ xẩy ra 1 = qn+1... qm hoặc 1 = Pm+1...Pn điều này vô lý vì qn+1;...qm là các số nguyên tố; Pm+1;... Pm cũng là các số nguyên tố. Vậy n = m và Pi = qi 3. Sự phân tích chính tắc Sự phân tích chính tắc của số tự nhiên a lớn hơn 1 có dạng: a = P1 . P2...Pk ni 1; i = 1; 2; ... ; k Đó là sự phân tích chính tắc của a Ví dụ: 360 = 23. 32. 5 là sự phân tích chính tắc của số 360 4. ứng dụng của định lý cơ bản a) ước của 1 số tự nhiên Nếu a = P1. P2...Pk là sự phân tích chính tắc của số a thì d\a d = P1.P2... Pk; 0 li ni ; i = 1; 2; ...; k * Hệ quả: Số các ước của số tự nhiên a ký hiệu là T(a) xác định như sau: T(a) = ( n1 + 1) (n2 + 1)...(nk + 1) Vậy muốn tìm số các ước số của một số tự nhiên a lớn hơn 1 ta chỉ cần phân tích a ra thừa số nguyên tố ở dạng chính tắc rồi vận dụng công thức: T(a) = ( n1 + 1) (n2 + 1)...(nk + 1) b) Tìm ƯCLN; BCNN Giả sử P1; P2;...; Pk là tất cả các ước nguyên tố chung của a và b Giả sử a = P. P2 .... Pk b = P1.P2... Pk ni 0; mi 0; i = 1; 2; ... ; k khi đó (a;b) = P1 . P2... Pk li = min (ni; mi) [ a ; b] = P1 . P2... Pk ; ti = max (n1; mi) * Hạn chế của phương pháp trên là khi tìm ƯCLN của 2 số tự nhiên lớn thì rất phức tạp trong việc phân tích các số đó ra thừa số nguyên tố. Ví dụ: Tìm ( 137543212; 17354) thì không nên sử dụng phương pháp trên mà ta nên dùng thuật toán Ơclít để tìm ƯCLN IV) Dạng tổng quát của một số nguyên tố. Hiện nay ta chưa tìm được dạng tổng quát của một số nguyên tố Ta có thể chứng minh được a) Mọi số nguyên tố lớn hơn 2 đều có dạng 4n + 1 hoặc 4n + 3; nN b) Mọi số nguyên tố lớn hơn 3 đều có dạng 6n + 1 hoặc 6n + 5; nN Chứng minh: a) Gọi P là số nguyên tố lớn hơn 2 Chia P cho 4 được thương là k; dư r Suy ra P = 4k + r ; 0 r < 4 Vì P là số nguyên tố lớn hơn 2 suy ra P không chia hết cho 2 mà 4k 2 r không chia hết cho 2 r = 1; 3 Vậy P chia cho 4 dư 1 hoặc 3 Hay P có dạng 4n + 1 hoặc 4n + 3; nN b) Gọi P là số nguyên tố lớn hơn 3; khi chia P cho 6 được thương là k; dư r Ta có P = 6k + r ; 0 r < 6 Vì P là số nguyên tố lớn hơn 3 suy ra P là số lẻ suy ra P không chia hết cho 2 mà 6k 2 suy ra r không chia hết cho 2 Vĩ P là số nguyên tố lớn hơn 3 suy ra P không chia hết cho 3 mà 6k chia hết cho 3, suy ra r không chia hết cho 3 Vậy r không chia hết cho 2 và 3 mà 0 r < 6 suy ra r = 5 hoặc r = 1 Vậy P chia cho 6 dư 1 hoặc 5. Hay P có dạng 6n + 1 hoặc 6n + 5; n N V) cách nhận biết một số P có là số nguyên tố hay không 1. Chia số đó lần lượt cho các số nguyên tố từ nhỏ đến số nguyên tố nhỏ hơn hoặc bằng - Nếu có một phép chia hết thì số đó không là số nguyên tố - Nếu chia cho đến lúc số thương nhỏ hơn số chia mà các phép chia vẫn có số dư thì số đó là số nguyên tố. 2. Một số có 2 ước số lớn hơn 1 thì số đó không phải là số nguyên tố. VI) Số nguyên tố cùng nhau: 1. Khái niệm: - Hai hay nhiều số được gọi là nguyên tố cùng nhau khi ƯCLN của chúng bằng 1. - Ba số được gọi là nguyên tố sánh đôi khi từng đôi một nguyên tố cùng nhau. 2. Chú ý: Ba số nguyên tố sánh đôi thì chúng nguyên tố cùng nhau; còn ngược lại thì không đúng. B : một số bài tập tham khảo Bài 1:Tìm các số nguyên tố p để: p+10 ; p+14 cũng là các số nguyên tố p+2 ; p+4 cũng là các số nguyên tố p=2 ; p +6 ; p+8 ; p+14 cũng là các số nguyên tố Bài 2 : tìm tất cả các số tự nhiên k để k+1 ; k+3 ; k+7 ;k+9 ;k+13 ;k+15 là các số nguyên tố k+4 là các số nguyên tố k- k+k -1 là các số nguyên tố k+ k+1 là các số nguyên tố Bài 3 : Chứng minh rằng a)mọi số nguyên tố khác 2 và 3 có dạng 6m+1 hoặc 6m-1 b)có vô số số nguyên tố dạng 6m -1 Bài 4:Chứng minh rằng với mọi số nguyên n >1 thì 19.8 + 17 là hợp số 2+3 là hợp số 2 +7 là hợp số Bài 5 : Cho p và p +4 là các số nguyên tố ( p > 3 ) .Chứng minh rằng p + 8 là hợp số Cho p và 8p -1 là các số nguyên tố.Chứng minh rằng 8p + 1 là hợp số Bài 6: Chứng minh rằng nếu 1+2+ 4 ( n) là số nguyên tố thì n =3 với k Bài 7:cho các số nguyên dương a,b,c,d thoả mãn a. b = c.d Chứng minh rằng A= a +b + c + d là hợp số với mọi n Bài 8 :Tìm các số nguyên tố x ; y ; z thoả mãn x- 2.y- 1 = 0 x+ y = z x.y.z = 3( x + y + z ) Bài 9: Tìm các số nguyên tố có bốn chữ số sao cho ; là các số nguyên tố và b = + b - c Bài10 :Cho A = n ! + 1 , B = n+1 ( nZ ) . Chứng minh rằng nếu AB thì B là số nguyên VII) Kết luận Trên đây là một số kiến thức mở rộng về số nguyên tố, chúng tôi đã sử dụng để bồi dưỡng học sinh giỏi phần chuyên đề số nguyên tố. Qua thực tiễn giảng dạy tôi thấy học sinh tiếp thu tốt, biết vận dụng linh hoạt, sáng tạo vào việc giải các bài tập và thu được kết quả tốt. Chắc chắn những vấn đề nêu trên không tránh khỏi những thiếu sót, vậy rất mong được sự góp ý của các đồng nghiệp và các cấp lãnh đạo. Trực Ninh, ngày 20 tháng 5 năm 2004 Người viết Ngô Văn Vịnh