Một Số định Lý Cơ Bản Của Số Học - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Tải bản đầy đủ (.pdf) (54 trang)

Trang chủ

Khoa học tự nhiên

Toán học

Một số định lý cơ bản của số học

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (618.33 KB, 54 trang )

Một số định lý cơ bản của số họcTrường đại học sư phạm hà nội 2Khoa Toán=====o0o=====NGÔ THỊ MINH DIỆUMột số định lý cơ bảncủa số họcKhoá Luận tốt nghiệp đại họcChuyên ngành: Đại sốHà Nội – 2008Ngô Thị Minh Diệu1K30G – Sư phạm ToánMột số định lý cơ bản của số họcTrường đại học sư phạm hà nội 2Khoa Toán=====o0o=====NGÔ THỊ MINH DIỆUMột số định lý cơ bảncủa số họcKhoá Luận tốt nghiệp đại họcChuyên ngành: Đại sốNgười hướng dẫn khoa họcTh.s Nguyễn Huy HưngHà Nội - 2008Ngô Thị Minh Diệu2K30G – Sư phạm ToánMột số định lý cơ bản của số họcLời cảm ơnBản khoá luận tốt nghiệp này là bước đầu tiên để em làm quen với việcnghiên cứu khoa học. Trước sự bỡ ngỡ và gặp nhiều khó khăn khi mới làmquen với công tác nghiên cứu khoa học em đã nhận được sự giúp đỡ, độngviên của các thầy cô giáo và các bạn sinh viên trong khoa. Em xin chân thànhcảm ơn sự giúp đỡ quý báu của các thầy cô trong tổ Đại số, các thầy cô trongkhoa Toán, các thầy cô trong trường ĐHSP Hà Nội 2 và các bạn sinh viên.Đặc biệt em xin gửi lời cảm ơn chân thành sâu sắc tới Thạc sĩ Nguyễn HuyHưng người đã giúp đỡ, hướng dẫn tận tình để em hoàn thành khoá luận này.Em cũng xin chân thành cảm ơn ban chủ nhiệm khoa Toán đã tạo điều kiệncho em có cơ hội để tập dượt với việc nghiên cứu khoa học.Hà Nội, tháng 5 năm 2008Sinh viênNgô Thị Minh DiệuNgô Thị Minh Diệu3K30G – Sư phạm ToánMột số định lý cơ bản của số họcLời cam đoanKhoá luận của em được hoàn thành dưới sự hướng dẫn của Thạc sỹNguyễn Huy Hưng cùng với sự cố gắng của bản thân. Trong quá trình nghiêncứu và thực hiện khoá luận em có tham khảo tài liệu của một số tác giả có nêutrong mục tài liệu tham khảo. Em xin cam đoan những kết quả trong khoáluận là kết quả nghiên cứu của bản thân, không trùng với kết quả của các tácgiả khác. Nếu sai em xin hoàn toàn chịu trách nhiệm.Hà Nội, tháng 5 năm 2008Sinh viênNgô Thị Minh DiệuNgô Thị Minh Diệu4K30G – Sư phạm ToánMột số định lý cơ bản của số họcMục lụcTrangLời cảm ơn…………………………………………………………..1Lời cam đoan………………………………………………………..2Mục lục……………………………………………………………...3Lời mở đầu…………………………………………………………..4Chương 1. Một số định lý cơ bản về số nguyên tố1.1 Định nghĩa số nguyên tố……………………………………61.2 Một số định lý cơ bản về số nguyên tố……………………61.3 Một số ứng dụng…………………………………………….101.4 Một số bài toán về số nguyên tố……………………………11Chương 2. Một số định lý cơ bản về đồng dư2.1 Quan hệ đồng dư…………………………………………....212.2 Định lý Euler. Định lý Wilson……...………………………252.3 Phương trình đồng dư………………………………………272.4 Định lý Thặng dư Trung Hoa……………………………….312.5 Thặng dư toàn phương. Luật thuận nghịch bình phương…342.6 Một số bài tập áp dụng……………………………………...40Kết luận…………………………………………………………......49Tài liệu tham khảo………………………………………………....50Ngô Thị Minh Diệu5K30G – Sư phạm ToánMột số định lý cơ bản của số họcLời mở đầuToỏn học là mụn khoa học cơ bản, là chỡa khoỏ mở ra nhiều mụn khoahọc khỏc. Từ thời xa xưa, do yờu cầu của thực tế đời sống, sản xuất, sinhhoạt, đầu thế kỷ thứ VII, người Ấn Độ đó biết dựng cỏc ký hiệu đặc biệt đểviết cỏc chữ số 0, 1, 2…, 9 ( Ngày nay gọi là cỏc chữ số Ả Rập ). Từ thế kỷ IItrước cụng nguyờn, người La Mó đó dựng hỡnh ảnh ngún tay, bàn tay để kýhiệu chỉ cỏc chữ số 1, 5… Rồi đến sự ra đời của chiếc bàn tớnh đầu tiờn, đếnnay là chiếc mỏy tớnh với nhiều chức năng tinh vi, hiện đại.Cỏc kiến thức về số học mà điểm xuất phỏt đầu tiờn là số tự nhiờn làchỡa khoỏ để mở cửa vào thế giới cỏc con số.Những kiến thức nền múng và quan trọng về Toỏn học núi chung và sốhọc núi riờng sẽ mang đến cho chỳng ta nhiều điều mới mẻ và thỳ vị.Ngay từ cấp học Tiểu học, học sinh đó được làm quen và cú kỹ năngthành thạo khi giải cỏc bài toỏn liờn quan đến cỏc phộp tớnh cộng, trừ, nhõn,chia số tự nhiờn. Khi học sinh học lờn cấp học THCS, THPT bờn cạnh việcđược ụn tập, hệ thống hoỏ cỏc nội dung về số tự nhiờn đó học, cỏc em cũntỡm hiểu thờm nhiều nội dung mới: phộp nõng lờn luỹ thừa, số nguyờn tố vàhợp số, ước chung và bội chung, quan hệ đồng dư…Trong chương trỡnh toỏn phổ thụng, lý thuyết số được xem là nội dungkhú với những bài toỏn phức tạp với nhiều cỏch giải thỳ vị. Trong cỏc kỳ thihọc sinh năng khiếu, học sinh giỏi cỏc cấp, nội dung số học: Số nguyờn tố,quan hệ đồng dư… chiếm tỷ lệ khỏ cao trong cỏc đề thi. Vỡ vậy, để giỳp cỏcem học sinh cú cỏch nhỡn tổng quỏt, toàn diện về hệ thống số, đặc biệt là cỏckiến thức, cỏc định lý cơ bản để từ đó cú thể giải được những bài toỏn về sốnguyờn tố, bài toỏn về quan hệ đồng dư… nờn em chọn nội dung: “ Một sốđịnh lý cơ bản của số học” làm luận văn nghiờn cứu.Khoá luận của em gồm hai chương :Ngô Thị Minh Diệu6K30G – Sư phạm ToánMột số định lý cơ bản của số họcChương 1 : Một số định lý cơ bản về số nguyên tố.Chương 2 : Một số định lý cơ bản về đồng dư.Mặc dù đã có nhiều cố gắng song không tránh khỏi những thiếu sót, vìvậy em rất mong nhận được ý kiến đóng góp của các thầy cô giáo và các bạnsinh viên cho bài khoá luận của em. Em xin chân thành cảm ơn!Hà Nội, tháng 5 năm 2008Sinh viên:Ngô Thị Minh DiệuNgô Thị Minh Diệu7K30G – Sư phạm ToánMột số định lý cơ bản của số họcChương 1. Một số định lý cơ bản vềsố nguyên tố1.1 Định nghĩa số nguyên tố :* Định nghĩa:- Một số tự nhiên lớn hơn 1 và không có ước tự nhiên nào khác ngoài 1và chính nó được gọi là số nguyên tố.Ký hiệu P là tập hợp các số nguyên tố. Khi đó :P = { p    p nguyên tố }.- Số tự nhiên lớn hơn 1 mà không là số nguyên tố gọi là hợp số.- Ước của số tự nhiên khác 1 và khác chính nó được gọi là ước thực sự.Khi đó định nghĩa số nguyên tố có thể được phát biểu lại như sau: Số tựnhiên lớn hơn 1 được gọi là số nguyên tố nếu nó không có ước thực sự.* Nhận xét :- Số 1 và số 0 đều không phải là số nguyên tố mà cũng không phải làhợp số ( số 1 chỉ có một ước số, số 0 có vô số ước số ).- Mỗi số tự nhiên n   * có một và chỉ một trong ba khả năng : n = 1;n là số nguyên tố, n là hợp số.1.2. Một số định lý cơ bản về số nguyên tố:Bổ đề 1.2.1 :Mọi số nguyên lớn hơn 1 đều chia hết cho ít nhất một số nguyên tố .Chứng minh:Ta chứng minh bằng quy nạp.+ Với n = 2, do 2 là số nguyên tố nên bổ đề đúng.+ Xét n > 2 và giả sử bổ đề đúng với mọi số nguyên lớn hơn 1 và nhỏhơn n. Ta sẽ chứng minh bổ đề đúng với n.Nếu n là số nguyên tố thì n  n và bổ đề đúng.Nếu n là hợp số thì n có ước dương a với a ≠ 1, a ≠ n. Giả sử n = a.b.Ngô Thị Minh Diệu8K30G – Sư phạm ToánMột số định lý cơ bản của số họcNếu a > n thì từ b ≥ 1 ta có n = a.b > n.1 = n, mâu thuẫn. Vậy 1 < a < n.Theo giả thiết quy nạp, a có ước nguyên tố p. Từ p | a, a | n suy ra p | n.Vậy bổ đề đúng với mọi n > 1.Định lý 1.2.2 ( Định lý Euclid )Tồn tại vô hạn các số nguyên tố.Chứng minh:Giả sử chỉ có hữu hạn các số nguyên tố là p1, p2,…, pn.Khi đó đặt N = p1.p2…pn + 1, thế thì theo bổ đề (1.2.1), N chia hết chomột số nguyên tố p nào đó ( vì N > 1 ). Số nguyên tố p này bắt buộc phải làmột trong các số pi, do chỉ có n số nguyên tố p1, p2,…, pn mà thôi. Tuy nhiên,theo định nghĩa của N, N không thể chia hết cho số pi nào cả. Mâu thuẫn nàycho ta điều phải chứng minh.Định lý 1.2.3 :Cho số tự nhiên a và một số nguyên tố p. Khi đó hoặc p | a hoặc(a,p)=1.Chứng minh :Gọi d = (a,p)  d | p với p là số nguyên tố. Từ đó hoặc d = 1 hoặc d = p.+ Nếu d = 1 thì (a, p) = 1.+ Nếu d = p thì p | a.Định lý 1.2.4 : ( Bổ đề cơ bản các số nguyên tố - Bổ đề Euclid) :Nếu một số nguyên tố p chia hết tích ab của hai số nguyên a và b thì pphải chia hết ít nhất một trong hai số a và b.Chứng minh :Giả sử p | ab nhưng p không chia hết a và không chia hết b. Khi đó theođịnh lý (1.2.3) ta có (a,p) =1 và (b,p) = 1, từ đó ta có (ab,p) =1 ( trái giả thiết p| ab). Từ đó, ta có điều phải chứng minh.Ngô Thị Minh Diệu9K30G – Sư phạm ToánMột số định lý cơ bản của số họcNhận xét : Bằng quy nạp, chúng ta có thể mở rộng kết quả này cho nhiều sốvà khi đó định lý (1.2.4) được mở rộng như sau:Nếu một số nguyên tố p chia hết tích a1.a2 … an thì p chia hết ai, với inào đó thuộc { 1, 2,…, n }.Ví dụ : Giả sử p là số nguyên tố.a. Chứng minh rằng nếu p | a3 thì p | a.b. Chứng minh rằng nếu p | b và p | ( a2 + b2 ) thì p | a.Giải:a. Giả sử p | a3 = a.a.a. Khi đó theo bổ đề Euclid ta có p | a hay p | ahay p | a, tức là p | a.b. Giả sử p | b và p | ( a2 + b2 ). Khi đó ta có :p | [( a2 + b2 ) - b.b] = a.aTừ đó và từ bổ đề Euclid ta có p | a.Hệ quả 1.2.5:Nếu một số nguyên tố p chia hết tích của nhiều số nguyên tố thì nóphải trùng với một trong các số nguyên tố đó.Bổ đề 1.2.6 :Mọi hợp số có ước thực sự nhỏ hơn hoặc bằng căn bậc hai của nó.Chứng minh:Cho n là hợp số. Khi đó ta có thể viết n = a.b với 1 < a, b < n.Nếu đồng thời a, b >n thì n =n .n < ab = n < mâu thuẫn >.Vậy có ít nhất một trong hai số a, b phải nhỏ hơn hoặc bằng n .Từ bổ đề này ta có nhận xét sau :Mỗi hợp số phải có ước nguyên tố nhỏ hơn hoặc bằng căn bậc hai củanóDựa vào nhận xét trên ta có thể kiểm tra xem một số nguyên dương chotrước bất kỳ là số nguyên tố hay không?Ngô Thị Minh Diệu10K30G – Sư phạm ToánMột số định lý cơ bản của số họcVí dụ : Để xác định a = 89 có là số nguyên tố không ta chỉ cần xem nó cóước nguyên tố bé hơn hoặc bằng89 không? Ta có89 = 9,43 và các sốnguyên tố nhỏ hơn hoặc bằng 9,43 là 2; 3; 5; 7 đều không là ước của 89.Vậy 89 là số nguyên tố.Cho một số tự nhiên a > 1 bất kỳ. Vấn đề đặt ra là liệu có thể biểu thị adưới dạng tích của các thừa số nguyên tố được hay không và có bao nhiêucách biểu thị như vậy? Vấn đề đó được giải quyết trong định lý sau:Định lý 1.2.7 < Định lý cơ bản của số học >Mọi số tự nhiên a > 1 đều phân tích được thành tích những thừa số nguyêntố và sự phân tích đó là duy nhất nếu không kể đến thứ tự của các thừa số.Chứng minh:a. Sự phân tích được :Giả sử a   , a > 1. Khi đó theo bổ đề (1.2.1) a có ít nhất một ướcnguyên tố p1 nào đó và ta có a = p1 . a1, a1 Nếu a1 = 1 thì a = p1 là cách phân tích tầm thường của a.Nếu a1 > 1 theo lý luận trên, a1 có ước nguyên tố p2 nào đó và ta có :a1 = p2 . a2, a2  nên a = p1.p2.a2Nếu a2 = 1 thì a = p1. p2 là phân tích của a .Nếu a2 > 1 lại tiếp tục lý luận như trên, có số nguyên tố p 3 ,…Quá trình này phải kết thúc, nghĩa là ắt có n sao cho an = 1, an-1 = pn làmột số nguyên tố, bởi vì ta có a, a1, a2,… là một dãy những số tự nhiên màa > a1 > a2 >… Như vậy, ta được a = p1 .p2… pn là sự phân tích của a thànhtích những thừa số nguyên tố .b. Sự duy nhất:Giả sử ta có a = p1.p2…pn = q1.q2…qm là hai dạng phân tích của a thànhtích của những thừa số nguyên tố. Đẳng thức trên chứng tỏ p 1 là ước củaq1.q2…qm nên p1 phải trùng với một qj nào đó ( 1 ≤ j ≤ m ). Vì không kể đếnNgô Thị Minh Diệu11K30G – Sư phạm ToánMột số định lý cơ bản của số họcthứ tự của các thừa số nên có thể coi p 1 = q1 từ đó ta được p2.p3…pn =q2.q3..qm. Ta lấy p2 và lặp lại cho đến khi ở một vế không còn thừa số nguyêntố nào nữa. Nhưng lúc đó, ở vế còn lại cũng không còn thừa số nguyên tố nàovì nếu ngược lại sẽ xảy ra hoặc 1 = qn+1.qn+2…qm hoặc pm+1.pm+2…pn = 1 làkhông thểđược. Vì vậy phải có m = n và pi = qi , i = 1, 2,…, n nghĩa là phân tích của a làduy nhất.Chú ý :- Nếu trong sự phân tích ra thừa số nguyên tố của một số tự nhiên a,một thừa số nguyên tố pi được lặp lại i lần thì ta viết :a = p11 . p22 ... pnni  1 i = 1, 2,…, n- Nếu thừa số nguyên tố pm không có mặt trong sự phân tích thì ta cóthể viết a = p11 . p22 ... pnn pm0 từ đó suy ra mọi số tự nhiên a đều có sự phântích duy nhất a = p11 . p22 ... pkk pk  P, i  0 gọi là dạng phân tích tiêu chuẩncủa số tự nhiên a.- Từ đó với mọi số nguyên n ≠ 0 đều có dạng phân tích tiêu chuẩn :n =  p11 . p22 ... pkk1.3. Một số ứng dụng :1.3.1 ước số :+) Cho a = p11 . p22 ... pnni  1,2,..., nd | a  d = p11 . p22 ... pnnvới 0 ≤ õi ≤ i i = 1, 2,.., n+) Muốn xác định tất cả các ước của a ta cho các õ i lần lượt chạy từ 0 đếni. .Vậy số các ước của a là (1 + 1) (2 + 1 )… (n + 1 )+) Cho ( a, b) =1. Khi đó :d | ab  d = xy với x | a, y | b và (x , y) = 1.Ngô Thị Minh Diệu12K30G – Sư phạm ToánMột số định lý cơ bản của số học1.3.2 Ước chung lớn nhất ( ƯCLN ):- Một số nguyên c được gọi là ước chung của các số nguyên a1, a2,…,an khi c là ước của từng số đó.- Một ước chung d của các số nguyên a1, a2 ,.., an được gọi là ước chunglớn nhất nếu mọi ước chung của chúng đều là ước của d.- Giả sử cho các số tự nhiên lớn hơn 1 là a1, a2 ,.., an. Gọi p1, p2 ,.., pn làcác ước nguyên tố phân biệt của các số đó.Giả sử các số ai có dạng :ai = p1i1 . p2i 2 ... pkikij ≥ 0 , j = 1, 2,…, k ; i = 1, 2,…, n.thế thì số d = p11 . p22 ... pkk với ỡj = min ( 1j, 2j,…, nj ) là số nhỏ nhất trongcác số 1j, 2j,…, nj sẽ là ước chung lớn nhất của a1, a2 ,.., an.Thật vậy, d | ai i = 1, 2,.., n và mọi ước chung của a1, a2,.., an đều là ước củad.1.3.3 Bội chung nhỏ nhất ( BCNN ):- Một số nguyên m được gọi là bội chung của các số nguyên a 1, a2,.., ankhi m là bội của mỗi số đó.- Một bội chung m của các số nguyên a1, a2,.., an được gọi là BCNNnếu mọi bội chung của chúng đều là bội của m.- Cũng bằng các ký hiệu ở trên ta có :Số m = p11 . p2 2 ... pk k với j = max ( 1j , 2j ,…, nj ) là số lớn nhất trongcác số 1j , 2j ,…, nj là BCNN của a1, a2,.., an. Thật vậy, m là bội chung củaa1, a2,.., an và mọi bội chung của a1, a2,.., an đều là bội của m.Ví dụ :Tìm ƯCLN, BCNN của 720, 225, 1000Ta có 720225= 24 . 32 . 5=Ngô Thị Minh Diệu32 . 5213K30G – Sư phạm ToánMột số định lý cơ bản của số học1000 = 23.53Vậy ( 720, 225, 1000 ) = 20 . 30 . 5 = 5[ 720, 225, 1000 ] = 24 . 32 . 53 = 18000.1.4. Một số bài toán về số nguyên tố:1.4.1 Dạng 1:Dùng phương pháp phân tích để:i. Tìm điều kiện để một số là số nguyên tố.ii. Chứng minh một số là hợp số.Bài 1:Tìm tất cả các số tự nhiên n để:a, n4 + 4 là số nguyên tố.b, n1991 + n1990 + 1 là số nguyên tố.Giải: a. n4 + 4 = n4 + 4n2 + 4 - 4n2= ( n2 + 2 )2 - (2n)2= ( n2 + 2 - 2n ) ( n2 + 2 + 2n )Vì n2 + 2 + 2n > 1 nên để n4 + 4 là số nguyên tố thìn2 + 2 - 2n = 1 n2 - 2n + 1 = 0 n=1Với n = 1 thì n4 + 4 = 5 là số nguyên tố.Kết luận: n = 1 thì n4 + 4 là số nguyên tố. b.n1991 + n1990 + 1 = n1991 - n2 + n1990 - n + n2+ n + 1= n2( n1989 - 1 ) + n( n1989 - 1 ) + n2 + n + 1  n2 + n + 1( Vì n1989 - 1 = (n3 )663  1n3  1n2  n  1 )Vậy để n1991 + n1990 + 1 là số nguyên tố thì n1991 + n1990 + 1 = n2+ n + 1 n = 1.Ngô Thị Minh Diệu14K30G – Sư phạm ToánMột số định lý cơ bản của số họcVới n = 1 thì n1991 + n1990 + 1 = 3 là số nguyên tố.Bài 2:Chứng minh rằng nếu 1 + 2n + 4n ( n   * ) là số nguyên tố thì n = 3kvới k   .Giải :Đặt n = 3k. m với ( m , 3 ) = 1. Giả sử m > 1 xét hai trường hợp :a. m = 3l + 1 ( l   * ). Ta có :1 + 2n + 4n = 1 + 23 (3l 1)  43 (3l 1) = 1 + a3l+1 + a6l+2 ( với a = 23 )kkksuy ra 1 + 2n + 4n = a ( a3l - 1 ) + a2 ( a6l - 1 ) + a2 + a + 1  a2 +a + 1nn 1 + 2 + 4 là hợp số.b. m = 3l + 2 ( l   * ).Ta có :1 + 2n + 4n = 1 + 23 (3l 2)  43 (3l 2)kk= 1 + a3l+2 + a6l+4= a ( a6l+3 - 1) + a2( a3l - 1) + a2 +a + 1  a2 +a + 13k( với a = 2 )Suy ra 1 + 2n + 4n là hợp số.Vậy m = 1 tức n = 3k.Bài 3 :a. Tìm số nguyên tố p sao cho :p + 2 , p + 6 , p + 8 , p + 14 là những số nguyên tố.b. Tìm 3 số nguyên tố liên tiếp p, q, r, sao cho p 2  q 2  r 2 cũng là sốnguyên tố.Giải :a. Ta lần lượt xét các trường hợp :Ngô Thị Minh Diệu15K30G – Sư phạm ToánMột số định lý cơ bản của số học+) p = 2 thì p + 2 = 4 là hợp số.+) p = 3 thì p + 6 = 9 là hợp số.+) p = 5 thì p + 2 = 7 ; p + 6 = 11; p + 8 = 13 ; p + 14 = 19 là nhữngsố nguyên tố.Vậy p = 5 là số cần tìm.+) Với p > 5 thì p có dạng p = 5k  1; p = 5k  2 ( k  * )- Nếu p = 5k + 1 thì p + 14 = 5p + 15 = 5 ( k + 3 ) là hợp số.- Nếu p = 5k – 1 thì p + 6 = 5k + 5 = 5 ( k + 1 ) là hợp số.- Nếu p = 5k + 2 thì p + 8 = 5k + 10 = 5 ( k + 2 ) là hợp số.- Nếu p = 5k – 2 thì p + 2 = 5k là hợp số.Vậy tất cả các số nguyên tố lớn hơn 5 đều không thoả mãn.Kết luận : p = 5 là số nguyên tố duy nhất cần tìm.b. Tìm ba số nguyên tố liên tiếp p, q, r. TH1 : p = 2 ; q = 3 ; r = 5có p 2  q 2  r 2 = 4 + 9 + 25 = 38 không là số nguyên tố.Vậy trường hợp 1 không thoả mãn. TH2 : p = 3; q = 5; r = 7 thì p 2  q 2  r 2 = 9 + 25 + 49 = 83 là sốnguyên tố.Vậy trường hợp 2 thỏa mãn. TH3 : p, q, r là các số nguyên tố liên tiếp lớn hơn 3.Do p, q, r đều nguyên tố nên chúng không chia hết cho 3.Lúc đó p, q, r có dạng : p 2  9k 2  6k  1 p  3k  1 22*( k, l, m   * )q  3l  1 ( k, l, m   ) nên q  9l  6l  1r  3m  1 r 2  9m 2  6m  1Ngô Thị Minh Diệu16K30G – Sư phạm ToánMột số định lý cơ bản của số họccó p 2  q 2  r 2 = 9(k 2  l 2  m2 )  6(k  l  m)  3 chia hết cho 3 nên nókhông là số nguyên tố.Vậy có duy nhất bộ ( p, q, r ) = ( 3, 5, 7 ) thoả mãn đề bài.Bài 4 :Cho a, b, c, d   * thoả mãn ab = cd. Chứng minh rằng :A = an + bn + cn + dn là hợp số với mọi n   .Giải:Giả sử (a, c) = t. Khi đó : a = ta1 , c = tc1 với (a1,c1) = 1.Từ ab = cd suy ra a1b = c1d  b  c1Đặt : b = kc1  c1d = a1.kc1  d = ka1.Khi đó :A = an + bn + cn + dn= tn. a1n + kn. c1n + tn. c1n + kn. a1n= ( kn + tn )( a1n + c1n ).Vì k, t, a1, c1  * nên A là hợp số.Bài 5:Chứng minh rằng với n   , n > 1 các số sau là hợp số:n1 n 1a, A  (22  22  1)3b, B = n4 + 4nGiải:a, Ta có :   nn 2nn1 n 11A  (22  22  1)   22  2.22  1  22  332nn 1 21  1  22n  22n 1  1 (22n  1  22n 1 )   22  1  22 3 3Do n ≥ 2 nên 22  22  1  1 và 22  22  1  1nn1Ngô Thị Minh Diệunn117K30G – Sư phạm ToánMột số định lý cơ bản của số họcn1 n 1Suy ra A  (22  22  1) là hợp số.3b, B = n4 + 4nXét hai trường hợp:+) n chẵn thì B  2+) n lẻ đặt n = 2k + 1 , k   * ,Ta có : n4 + 4n = n4 + 42k+1= ( n2 + 22k+1)2 - 2n2.22k+1= ( n2 + 22k+1 + n.2k+1).( n2 + 22k+1 - n.2k+1)= [ ( n + 2k )2 + 22k ] [ ( n - 2k )2 + 22k ]Do k   * nên ( n + 2k )2 + 22k > 1 và ( n - 2k )2 + 22k > 1 .Vậy B là hợp số.1.4.2 Dạng 2 : Sử dụng tính vô hạn của tập số nguyên tố:Bài 6 :Chứng minh rằng tích của các số có dạng 4m + 1 là một số có dạng ấy.Từ đó chứng minh có vô số số nguyên tố dạng 4m + 3.Giải:- Chứng minh tích của hai số có dạng 4m + 1 là số có dạng 4m + 1.Giả sử a = 4p + 1 ; b = 4q + 1.Khi đó:a.b = ( 4p + 1 ).( 4q + 1 )= 16pq + 4p + 4q + 1= 4 ( 4pq + p + q ) + 1= 4k + 1 ( với k = 4pq +p + q )Vậy tích của hai số có dạng 4m + 1 là số có dạng 4m + 1. Nếu ta nhânthêm với các thừa số thứ ba, thứ 4 … có dạng 4m + 1 thì sẽ cho kết quả là mộtsố có dạng 4m + 1.Ngô Thị Minh Diệu18K30G – Sư phạm ToánMột số định lý cơ bản của số học- Chứng minh có vô số số nguyên tố có dạng 4m + 3 :Trước hết chứng minh : Nếu p là số nguyên tố thì p chỉ biểu diễn đượcdưới dạng 4m + 1 hoặc 4m + 3.Thật vậy :- Nếu p = 4m thì p chia hết cho 4 nên p là hợp số.- Nếu p = 4m + 2 thì p = 2 ( 2m + 1 ) là tích của hai số lớn hơn 1 nênlà hợp số.Vậy p = 4m + 1 hoặc p = 4m + 3.Giả sử có hữu hạn số có dạng 4m + 3 là : p1  3; p2  7,..., pn , n   *Xét số a  4 p1. p2 ... pn  1 (*)a có ít nhất một ước nguyên tố có dạng 4m + 3.Bởi vì : nếu a có tất cả các ước có dạng 4m + 1 thì theo chứng minhtrên, a có dạng 4m + 1 ( mâu thuẫn với (*) )Gọi ước nguyên tố đó là u = 4m + 3.u không thể bằng một trong các số p1, p2 ,..., pn .Thật vậy, nếu u = pi nào đó ( i = 1, 2, …, n ) thìa  4 p1. p2 ... pi ... pn  1 = q1q2 ...qi1 pi qi1...qm pi (4 p1... pi 1 pi 1... pn  q1...qi 1qi 1...qm ) = 1suy ra pi  1 ( vô lý )Vậy có vô số số nguyên tố có dạng 4m + 3 .Hoàn toàn tương tự ta cũng chứng minh được tích của các số có dạng6m + 1 là số có dạng ấy. Từ đó suy ra có vô số số nguyên tố có dạng 6m + 5.Bài 7 :Chứng minh rằng với m > 2 giữa m và m! có ít nhất một số nguyên tố,từ đó suy ra rằng có vô số số nguyên tố.Giải:Ngô Thị Minh Diệu19K30G – Sư phạm ToánMột số định lý cơ bản của số học* Do m > 2 nên m! – 1 > 1, theo bổ đề (1.2.1) có số nguyên tố p saochop  ( m! – 1 )(1).Khi đó, p  ( m! – 1 ) < m! tức là có p < m!(2)Bây giờ ta chứng tỏ p > m.Giả sử ngược lại p ≤ m. Khi đó p  m!(3)+ Từ (1) và (3) suy ra p  [ m! - ( m! – 1 ) ] =1 ( mâu thuẫn) vì p là số nguyêntố. Vậy p > m.(4)+ Từ (2) và (4) có m < p < m!Vậy với m > 2 thì giữa m và m! có ít nhất một số nguyên tố.* Chứng minh có vô số số nguyên tố bằng phản chứng.Giả sử chỉ có hữu hạn số nguyên tố là p1, p2 ,..., pnĐặt m = p1. p2 ... pn . Khi đó m > 2.Theo chứng minh trên có số nguyên tố p sao cho m < p < m!Nhưng vì m = p1. p2 ... pn < p nên p ≠ pi ( i = 1, 2, …, n ) điều này mâu thuẫnvới giả sử ở trên.Nghĩa là có vô số số nguyên tố .1.4.3 Một số bài toán khác :Bài 8 :Chứng minh rằng với p là một số nguyên tố lớn hơn 3 ta có 24  p 2  1 .Từ đó hãy cho biết với p, q là những số nguyên tố lớn hơn 3 thì p 2  q 2 chiahết cho bao nhiêu?Giải :- Do p là một số nguyên tố lớn hơn 3 nên p có dạng p = 3k ± 1 ( k  )Từ đó : p 2  1 = (3k  1)2  1  9k 2  6k  3(3k 2  2k )3Ngô Thị Minh Diệu20(1)K30G – Sư phạm ToánMột số định lý cơ bản của số họcLại có p 2  1 = ( p + 1 ) ( p – 1 ) là tích của hai số chẵn liên tiếp nênp2  1  8(2).Và (3,8) = 1 nên từ (1) và (2) ta có p 2  1  24. Vậy 24  p 2  1 . (ĐPCM)*) Với p, q là những số nguyên tố lớn hơn 3 ta có :p 2  q 2 = ( p2  1)  (q2  1)Theo chứng minh trên p 2  1 24 2q  1 24Vậy p 2  q 2  24Bài 9:p là số nguyên tố và một trong hai số 8p + 1 ; 8p – 1 là số nguyên tố, sốthứ ba là số nguyên tố hay hợp số.Giải:p = 3 thì 8p + 1 = 25 là hợp số.8p – 1 = 23 là số nguyên tố.p ≠ 3 ta có 8p – 1; 8p; 8p + 1 là ba số tự nhiên liên tiếp nên có một sốchia hết cho 3. Vì p nguyên tố khác 3 nên 8p  3 do đó 8p – 1 hoặc 8p + 1chia hết cho 3. Vậy số thứ ba là hợp số.Bài 10:Tìm số tự nhiên k để dãy : k + 1 , k + 2, …, k + 10 chứa nhiều sốnguyên tố nhất.Giải:+) k = 0 ta có dãy 1, 2, …, 10 chứa 4 số nguyên tố là 2, 3, 5, 7.+) k = 1 ta có dãy 2, 3, …, 11 chứa 5 số nguyên tố là 2, 3, 5, 7, 11.+) k = 2 ta có dãy 3, 4, 5, …, 12 chứa 4 số nguyên tố là 3, 5, 7, 11Ngô Thị Minh Diệu21K30G – Sư phạm ToánMột số định lý cơ bản của số học+) k  3 dãy k + 1, k + 2,…, k + 10 chứa 5 số lẻ liên tiếp, các số lẻ nàyđều lớn hơn 3 nên có một số chia hết cho 3, mà 5 số chẵn trong dãy hiểnnhiên không là số nguyên tố. Vậy trong dãy có ít hơn 5 số nguyên tố.Kết luận : Với k = 1 thì dãy k + 1, k + 2, … , k + 10 chứa nhiều sốnguyên tố nhất.Bài 11 :a. Cho 2k  1 là số nguyên tố ( gọi là số nguyên tố Fermat ).Chứng minh rằng k = 0 hoặc k = 2 n .b. Cho 2k  1 là số nguyên tố ( gọi là số nguyên tố Merssenne ).Chứng minh rằng k là số nguyên tố .Giải:a. Giả sử phản chứng rằng k > 0 và k ≠ 2 n với mọi n.Khi đó k = 2 n . t , với t lẻ, t > 1. Ta có :2k  1 = (22 )t  1  22  1 ( vô lý với 2k  1 là số nguyên tố ).nnVậy k = 0 hoặc k = 2 n .b. Giả sử k = m.t với 1 < t < k. Khi đó :2k  1 = (2t )m  12t  1 suy ra 2k  1 là hợp số vì 2t  1 > 1.Vậy k là số nguyên tố.* Bài tập đề nghị :Bài 1 :Tìm n để :a. n4  n  1 là số nguyên tố.b. n3  n2  n  1 là số nguyên tố.Bài 2 :Chứng minh rằng với n > 1 các số sau là hợp số :a. 3.22  1 ( n ≥ 1 )2nNgô Thị Minh Diệu22K30G – Sư phạm ToánMột số định lý cơ bản của số họcb. 222 n1 3.Bài 3 :Chứng minh rằng với m > 2 ta có (m) > 1, từ đó suy ra có vô số sốnguyên tố.Bài 4:Hai số 2n  1 và 2n  1 ( n > 2 ) có thể đồng thời là số nguyên tố hayđồng thời là hợp số được hay không?Bài 5 :Chứng minh rằng với số nguyên tố bất kỳ p > 2, tử số m của phân sốm1 11 1    ... ( với m , n  N ) chia hết cho p.n2 3p 1Chương 2. Một số định lý cơ bản về đồng dư2.1. Quan hệ đồng dư :Định nghĩa 2.1.1 :Cho hai số nguyên a và b. Ta nói a có quan hệ đồng dư modulo m vớib, ký hiệu a ≡ b ( mod m ) nếu và chỉ nếu m | (a - b ), trong đó m là số nguyêndương.Nếu a không đồng dư modulo m với b, ta ký hiệu a  b ( mod m).Ví dụ :7 ≡ 2 (mod 5) ; 18 ≡ 2 (mod 4).Định nghĩa 2.1.2 ( định nghĩa nghịch đảo modulo ) :Ngô Thị Minh Diệu23K30G – Sư phạm ToánMột số định lý cơ bản của số họcCho m   * , a   , nếu có ax ≡ 1 ( mod m ) thì ta nói x là nghịch đảocủa a theo modulo m, ký hiệu a-1, phần tử này xác định duy nhất theo modulom.Ví dụ : 3 là nghịch đảo của 6 ( hay ngược lại 6 là nghịch đảo của 3) theomodulo 17 vì 3.6 ≡ 1 ( mod 17 ).Định lý 2.1.3 :Nghịch đảo của a theo modulo m tồn tại và duy nhất nếu và chỉ nếu anguyên tố cùng nhau với m.Chứng minh :Nếu ax ≡ 1 ( mod m) thì ax = 1 + km  ax - km = 1 với k nguyên nàođó suy ra a nguyên tố cùng nhau với m.Đảo lại, nếu a nguyên tố cùng nhau với m thì tồn tại x, y sao choax + my = 1 suy ra ax = 1 - my, do đó ax ≡ 1 ( mod m).Nghịch đảo x là duy nhất theo modulo m.Thật vậy, vì nếu có thêm nghịch đảo x’ thì ax ≡ ax’ ≡ 1 ( mod m).Do đó :x  xax ≡ xax’ ≡ x’ ( mod m )Định nghĩa 2.1.4 ( Định nghĩa hệ thặng dư đầy đủ) :Tập hợp m số nguyên a1, a2 ,.., am được gọi là một hệ thặng dư đầy đủmodulo m nếu với i ≠ j thì ai  aj ( mod m) hay điều kiện tương đương làai ≡ aj (mod m ) thì i = j.Ví dụ :Với m = 7 thì tập hợp { 14; -6; 9; 17; 25; -9; 6 } là hệ thặng dư đầy đủmodulo 7.Định nghĩa 2.1.5 : ( Hệ thặng dư đầy đủ không âm nhỏ nhất ) :H = { 0; 1; 2;…; m - 1 } là một hệ thặng dư đầy đủ modulo m và đượcgọi là hệ thặng dư đầy đủ không âm nhỏ nhất.Ngô Thị Minh Diệu24K30G – Sư phạm ToánMột số định lý cơ bản của số họcVí dụ : m = 4 thì hệ { 0, 1, 2, 3 } là hệ thặng dư đầy đủ không âm modulo 4nhỏ nhất.Nhận xét : Từ định nghĩa ta thấy nếu { a1, a2,…, am } là hệ thặng dư đầy đủmodulo m, thì với mọi số nguyên tuỳ ý z, luôn tồn tại số ai nào đó của hệ đểz ≡ ai (mod m ).Định nghĩa 2.1.6 ( Định nghĩa (m) )Cho m là số tự nhiên khác 0.+) m = 1 ta định nghĩa (1) = 1+) m > 1 ta định nghĩa (m) là số các số tự nhiên khác 0 và nguyên tốvới m.Định lý 2.1.7 ( Công thức tính (m)): Với m = p, ở đó p là số nguyên tố và    * ta có(p) = p - p-1 = p ( 1-1)p Với m > 1 có dạng phân tích tiêu chuẩn m = p11 p22 ... pkk ta có : (m) = m(1 111).(1  )...(1  )p1p2pk(1)Chứng minh : Trong tập hợp các số tự nhiên khác 0 không vượt quá p có p số, trongđó các số không nguyên tố với p là và chỉ là p, 2p, …, p-1p nghĩa là có p-1số như vậy. Các số còn lại đều là những số nguyên tố với p nên ta có :(p) = p - p-1 = p ( 1-1)p Ta chứng minh công thức (1) quy nạp theo k.Với k = 1 (1) đúng ( theo chứng minh phần trước)Giả sử (1) đúng với các số tự nhiên có k - 1 ước nguyên tố và giả sửNgô Thị Minh Diệu25K30G – Sư phạm Toán