Phân loại bài tập về số nguyên tố

Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 1 ỦY BAN NHÂN DÂN TĨNH HÀ TĨNH TRƯỜNG ĐẠI HỌC HÀ TĨNH -------------------- Bµi TËp Lín Bước đầu tìm hiểu và phân loại bài tập về số nguyên tố  Gv hướng dẫn: Ths NguyÔn ThÞ Thanh T©m Sinh viên thực hiện: Ng« ThÞ Kim Nhung NguyÔn Cao ThiÖn Khoa Sư Phạm Tự Nhiên Lớp K2 Sư Phạm Toán Hà Tĩnh 12/2010 Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 2 Đồng tác giả Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 3 A - ĐẶT VẤN ĐỀ I - Lý do chọn đề tài: Toán học là công cụ giúp việc học tập các môn khác cả về kiến thức và t ư duy. Môn toán có tiềm năng phát triển năng lực trí tuệ, rèn luyện tính linh hoạt, độc lập, sáng tạo, tính chính xác, thẩm mỹ cùng sự kiên trì, nhẫn nại. Trong chương trình toán học đa dạng và phong phú của nó, các bài toán về "Số nguyên tố" luôn để lại những vấn đề mới mẻ cho người học. "Toán học là bà hoàng của khoa học". "Số học là bà chúa của toán học". Trong số học các bài toán hóc búa, thú vị hầu hết là bài toán về số nguyên tố. Từ trước công nguyên, Ơclít đã khẳng định số nguyên tố là phạm trù cơ bản của số học. Thực tế đã chứng minh, toán học dù phát triển đến đâu thì vai trò của số nguyên tố cũng không hề thay đổi. Nó vẫn là một vùng đất kì lạ dù bao năm qua đã có nhiều người thám hiểm. Do vậy không thể tránh khỏi hiện tượng các bạn học sinh, sinh viên lo sợ khi gặp các bài toán về số nguyên tố, đa phần các bạn không định hình được phương pháp giải. Vấn đề đặt ra ở đây là bổ sung các kiến thức về số nguyên tố và làm thế nào để phân chia các bài toán đó theo từng dạng cũng như định hình được phương pháp giải cho mỗi dạng toán trên cơ sở đó giải quyết các bài toán cụ thể. Đây cũng là lý do chúng tôi chọn nghiên cứu đề tài: “Bước đầu tìm hiểu và phân dạng về số nguyên tố” Chúng tôi chỉ là những sinh viên mới chập chững bước vào công việc nghiên cứu khoa học, với rất ít tài liệu cùng sự hiểu biết nhỏ bé nhưng mong rằng đề tài này sẽ không nhàm chán mà có thể hữu ích một phần nhỏ trong việc giải quyết các bài toán dễ dàng, linh hoạt, đúng đắn hơn. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 4 II - Mục đích nghiên cứu - Tìm hiểu lí thuyết chung về số nguyên tố để bổ sung thêm một số kiến thức giúp cho việc giải quyết các bài toán trong phần này. - Phân dạng các bài toán cùng hướng giải quyết giúp học sinh sinh viên định hình được phương pháp giải mỗi dạng toán trên cơ sở đó giải quyết được các bài toán với những hình thức biến tướng của nó. III - Nội dung nghiên cứu Đề tài gồm 3 phần A: Đặt vấn đề B: Nội dung C: Kết luận Nội dung chính đề tài ở phần hai gồm 2 mục là: Phần một: - Cơ sở lí thuyết Phần hai: - Phân dạng bài toán Dạng 1: Các bài toán về tập hợp số nguyên tố Dạng 2: Chứng minh một số, một biểu thức là số nguyên tố, hợp số Dạng 3: Tìm số x thõa mãn điều kiện cho trước Dạng 4: Áp dụng giải phương trình nghiệm nguyên, chia hết Dạng 5: Áp dụng, chứng minh một số bổ đề, định lí có ứng dụng trong giải các bài toán về số nguyên tố IV - Phương pháp nghiên cứu Nghiên cứu tài liệu Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 5 B – NỘI DUNG Phần một: TÌM HIỂU CHUNG VỀ LÝ THUYẾT SỐ NGUYÊN TỐ Vấn đề số nguyên tố là một trong những vấn đề trung tâm của bộ môn số học. Trong chương này ta sẽ tìm hiểu và bổ sung một số vấn đề trong lí thuyết số: số nửa nguyên tố, số giả nguyên tố. Để đơn giản, chúng ta xét khái niệm số nguyên tố trong tập hợp các số tự nhiên  I - Số nguyên tố 1. Định nghĩa Số nguyên tố là số tự nhiên chỉ chia hết cho một và chính nó. 2. Tập hợp số nguyên tố 2.1 Định lí 1: Ước nhỏ nhất lớn hơn 1 của một số tự nhiên lớn hơn 1 là một số nguyên tố. Chứng minh: (Bằng phản chứng) Giả sử a  , a > 1 và p > 1: p là ước nhỏ nhất của a thì p là một số nguyên tố. Thật vậy: p  P  p phải là hợp số nghĩa là p1\p và 1< p1 < p. Suy ra p1\a mà 1< p1 < p  mâu thuẫn (do p là ước nhỏ nhất lơn 1 của a) 2.2 Định lí Ơclit: Tập hợp số nguyên tố là vô hạn Chứng minh: Giả sử chỉ có hữu hạn số nguyên tố p 1 = 2, p2 = 3,......., pn Xét a = p1p2....pn + 1 là số tự nhiên lớn hơn 1 nên a có ít nhất một ước số nguyên tố q. Nhưng vì: Chỉ có hữu hạn số nguyên tố p1, p2,......, pn nên q phải trùng với một trong các số p1, p2,......, pn . Do đó q phải là ước của tích p1p2....pn . Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 6 Từ q là ước của a = p1p2....pn + 1 và q lại là ước của p1p2....pn suy ra q là ước của a – p1p2....pn = 1. Mâu thuẫn với giả thiết q là số nguyên tố. Vậy t ập hợp số nguyên tố là vô hạn (đpcm). 3. Tính chất của số nguyên tố 1) Nếu một số nguyên tố p chia hết cho số nguyên tố a khác 1 thì a = p 2) Nếu các số nguyên tố p1, p2,......, pn (n ≥ 2) khác nhau từng đôi một thì chúng nguyên tố cùng nhau. 3) 2 là nguyên tố chẵn nhỏ nhất cũng là số nguyên tố chẵn duy nhất. 4) Nếu p là số nguyên tố, a là số nguyên suy ra hoặc p \a hoặc (a,p) = 1 5) Ước số dương bé nhất khác 1 của một hợp số a là một số nguyên tố không vượt quá a II - Định lí cơ bản của số học Trong mục này chúng ta sẽ chứng minh một định lí nói lên vai trò quan trọng của số nguyên tố trong tập hợp số tự nhiên N. Định lí này có nhiều ứng dụng. Để thuận lợi cho việc chứng minh trước hết ta chứng minh một số bổ đề sau đây. 1) Các bổ đề: 1.1 Bổ đề 1: Với số tự nhiên a và số nguyên tố p thì hoặc a nguyên tố cùng nhau với p hoặc a chia hết cho p. Chứng minh: Giả sử: d = ƯCLN(a,p)  d\p      pd d 1 (a  , p là số nguyên tố) 1.2 Bổ đề 2: Nếu một tích gồm nhiều số tự nhiên chia hết cho số nguyên tố p thì phải có ít nhất một thừa số của tích chia hết cho p Chứng minh: Thật vậy: Giả sử các số tự nhiên không chia hết cho số nguyên tố p. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 7 Theo bổ đề 1 chúng đều nguyên tố cùng nhau với p. Do đó ta có tích các số tự nhiên nguyên tố cùng nhau với p chứ không phải chia hết p. Mâu thuẫn với giả thiết rằng p là ước của tích đó. 1.3 Hệ quả: Nếu số nguyên tố p là ước của tích các thừa số nguyên tố q1, q2,....., qn thì p phải trùng với một số trong các số nguyên tố của tích đó. 2) Định lí cơ bản Mỗi số tự nhiên lớn hơn 1 đều phân tích được thành những thừa số nguyên tố 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 đó a có một ước nguyên tố p1 nào đó Ta có: a = a1p1 trong đó 1  a1 < a - Nếu a1 = 1 thì a = p1 đó là sự phân tích a thành thừa số nguyên tố. - Nếu a1 > 1 thì a1 phải có một ước nguyên tố p2 chẳng hạn và ta có: a1 = p1a2 nên a = p1p2a2 1  a2 < a1 +) Nếu a2 = 1 thì a = p1p2 là sự phân tích a thành thừa số nguyên tố +) Nếu a2 > 1 thì với lập luận như trên ta được thừa số nguyên tố p3,... quá trình đó phải kết thúc vì ta có a > a 1 > a2 >.... nên ắt phải có an = 1 ta được p1p2....pn là dạng phân tích của a thành lũy thừa số nguyên tố b) Tính duy nhất Giả sử ta có: a = p1p2....pn = q1q2....qn là 2 dạng phân tích của a thành số nguyên tố. Thế thì ta có: p1\q1q2....qn Do đó p1 phải là ước của một thừa số nào đó chẳng hạn q1 của tích q1q2....qn. Vậy ta có p1 = q1 và ta được p2p3....pn = q2q3....qn Lập lại lý luận trên với p2, p3... cho tới khi đã ước lược hết các thừa số nguyên tố của một vế trong đẳng thức trên, vì không thể xảy ra 1 = q n+1...qm Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 8 hoặc pm+1...pn = 1 nên ta được m = n và pi = qi, i = n,1  tính duy nhất được chứng minh. Ví dụ: Phân tích a = 300; a =300 = 2.2.5.5.3 3) Ứng dụng 3.1 Tìm ước số - Cho a = p 11 p 22 ... p nn ( i, pi  ) d\a  d = p 11 p 22 ... p nn Với 0   i   i - Cho (a,b) = 1 khi đó d\ab  d\xy với (x,y) = 1 3.2 Tìm ƯCLN, BCNN Giả sử a = p 11 p 22 ... p nn với 0  i,  i  b = p 11 p 22 ... p nn Khi đó (a,b) = p 11 p 22 ... p nn với  i = min(i,  i) [a,b] = p 11 p 22 ... p nn với  i = max( i,  i) Do đó (a,b).[a,b] = ab Tính số các ước của một số tự nhiên - Với a =1 thì )(a = 1 - Với a >1 Giả sử a = p 11 p 22 ... p nn ( i  ) Muốn xác định số các ước của a cho  i lần lượt các giá trị từ 0 đến  i.. Số các ước số của a là )(a = ( 1 + 1)(  2 + 1)...(  n + 1) 3.4 Tìm tổng các ước của một số tự nhiên - Với a = 1 thì )(a = 1 - Với a > 1 Giả sử a = p 11 p 22 ... p nn thì )(a = 1 1 1 11 1   p p  1 1 2 12 2   p p  .... 1 11   n n n p p  4) Dạng phân tích tiêu chuẩn Trong sự phân tích số a >1 thành một tích những thừa số nguyên tố có thể xảy ra nhiều thừa số lặp lại. Gọi p1, p2,......, pn là các ước nguyên tố đôi một Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 9 khác nhau của a và  i (1 i  k) là số các nhân tử cùng là pi trong sự phân tích a thành thừa số nguyên tố, ta sẽ có a = p 11 p 22 ... p kn gọi là dạng phân tích tiêu chuẩn của a. VD 300 = 22.52.3 III - Một số vấn đề về số nguyên tố Trong mục này chúng ta sẽ bổ sung thêm một số vấn đề về số số nguyên tố như số nửa nguyên tố, số giả nguyên tố, một vài vấn đề tìm biểu thức lấy các giá trị là số nguyên tố và một số vấn đề khác. 1) Số nửa nguyên tố - Số nửa nguyên tố là số tự nhiên được tạo thành từ tích của hai số nguyên tố (không nhất thiết phải phân biệt) Ví dụ: các số nửa nguyên tố đầu tiên 4, 6, 9, 14, 15, 21, 15... - Tính đến nay, số nửa nguyên tố lớn nhất được biết đến là (243112609 – 1)2, với hơn 25 triệu chữ số. Nó là bình phương của số nguyên tố lớn nhất được biết. Bình phương của bất kì số nguyên tố nào cũng là số nửa nguyên tố, do đó số nửa nguyên tố tiếp theo được biết đến vẫn sẽ là bình phương số nguyên tố lớn nhất được biết (trừ khi tìm ra được một phương pháp khẳng định một số lớn là số nửa nguyên tố mà không biết hai phần tử của nó). - Giá trị của phi hàm Euler cho số nửa nguyên tố n = pq khi p và q phân biệt là: )(a = (p – 1)(q – 1) = pq – (p + q) + 1 = n – (p + q) + 1 2) Số giả nguyên tố 2.1 Số giả nguyên tố Fermat - Định nghĩa: Định lí nhỏ Fermat khẳng định: Với mọi số nguyên tố p và số tự nhiên a không chia hết cho p ta có: ap - 1  1 (mod p) - Dạng khác của định lí Fermat: Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 10 Nếu p là số nguyên tố a là số nguyên bất kỳ, ap – a sẽ chia hết p. Nghĩa là ap  a (mod p)  Định lí nhỏ Fermat là cơ sở để kiểm tra tính nguyên tố theo xác suất trong kiểm tra Fermat. 2.2 Số giả nguyên tố (Fermat) mạnh Định nghĩa: Trong đồng dư thức của định lí nhỏ Fermat với số nguyên tố lẻ p và số tự nhiên a không chia hết cho p ap – 1  1 (mod p) ta phân tích số chẵn p – 1 = 2sm, với m là số lẻ Khi đó: - Hoặc am  1 (mod p) (1) - Hoặc a m s 2 – 1 (mod p) với k nào đó  {0,1,....s} (2) Số tự nhiên lẻ n trong đó n – 1 = 2sm thỏa mãn am  – 1 (mod m) hoặc tồn tại k  {0, 1,...., s} sao cho a m s 2  – 1 (mod m) được gọi là số nguyên tố xác suất mạnh Fermat cơ sở a. Nếu n là hợp số thì n được gọi là số giả nguyên tố Fermat c ơ sở a. * Số nguyên tố xác suất Fermat mạnh được sử dụng trong kiểm tra Miller - Rabin để kiểm tra tính nguyên tố theo xác suất của số tự nhiên lẻ. Nhận xét: 1) Nếu n là số giả nguyên tố cơ sở 2 thì m = 2n – 1 cũng là số giả nguyên tố cơ sở 2. Từ đó suy ra có vô hạn số nguyên tố cơ sở 2. 2) Mọi số giả nguyên tố mạnh Fermat đều là số giả nguyên tố Fermat. 3) Số Carmichael: Hợp số n là số Carmichael nếu nó là số giả nguyên tố Fermat với mọi cơ sở a sao cho ƯCLN [a,n] = 1. 4) Nếu n < 4759123141 là hợp số thì n không thể là số giả nguyên tố mạnh Fermat đồng thời với ba cơ sở a = 2, 7 và 61 (Jaeschhe – 1993). 5) Nếu n < 341550071728312 là hợp số thì n không thể là số giả nguyên tố mạnh Fermat đồng thời với bảy cơ sở a = 2, 3, 5, 7, 11, 13 và 17 (Jaeschhe – 1993). Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 11 2.3 Số giả nguyên tố Euler Định nghĩa: Số tự nhiên lẻ n thỏa mãn đồng dư thức tương tự với một a nào đó a 2 1n   1 (mod n) được gọi là số nguyên tố xác suất Euler Nếu n là hợp số thì n được gọi là số giả nguyên tố Euler 2.4 Số giả nguyên tố Euler – Jacobi Định nghĩa: Định lí Euler khẳng định: Với mọi số nguyên tố p và mọi số a a 2 1p  ( p a ) (mod p) Trong đó: ( p a ) là kí hiệu Legendre (chỉ được định nghĩa cho nguyên tố p). Khi mở rộng kí hiệu Legendre cho số tự nhiên lẻ n và số tự nhiên a ta có kí hiệu Jacobi được kí hiệu giống như kí hiệu Legendre: ( n a ). Số tự nhiên lẻ n thỏa mãn đồng dư thức tương tự định lí Euler: a 2 1n  ( n a ) (mod n) Với a nào đó được gọi là số nguyên tố xác suất Euler – Jacobi cơ sở a. Nếu n là hợp số thỏa mãn đồng dư thức trên thì nó được gọi là số giả nguyên tố Euler – Jacobi cơ sở a. Nhận xét: 1. Mọi số giả nguyên tố Euler cơ sở a đều là số giả nguyên tố Fermat 2. Mọi số giả nguyên tố Euler – Jacobi cơ sở a đều là số giả nguyên tố Euler cơ sở a. 3. Mọi số giả nguyên tố Fermat mạnh c ơ sở a đều là số giả nguyên tố Euler – Jacobi. 4. Mọi số giả nguyên tố Euler – Jacobi cơ sở a thỏa mãn một trong hai điều kiện sau là số giả nguyên tố mạnh c ơ sở a. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 12 + n  3 (mod 4) + Kí hiệu Jacobi ( n a ) = – 1 3) Số nguyên tố Pamanujan Định nghĩa: - Số nguyên tố Ramanujan là các số Rn sao cho Rn là số nhỏ nhất thỏa mãn ®iều kiện π(x) − π(x \ 2) ≥ n, cho mọi x ≥ Rn. - Hoặc số nguyên tố Ramanujan là các số Nguyên Rn sao cho Rn là số nhỏ nhất có thể bảo đảm có n số nguyên tố giữa x và x\2 với mọi x ≥ Rn Vì Rn là số nguyên tố nhỏ nhất thỏa mãn điều kiện trên nên Rn phải là số nguyên tố Mỗi khi hàm π(x) − π(x\2) tăng lên 1 đó là do có thêm một số nguyên tố nữa. 4) Số nguyên tố Mersenne Định nghĩa: Số nguyên tố Mersenne là một số có dạng lũy thừa của 2 trừ 1: 2 n − 1 với n là số nguyên tố Ví dụ: 31 là số nguyên tố Mersenne Mn = 31 = 25 – 1 với 5 là số nguyên tố Điều kiện cần để Mn là số nguyên tố là n là số nguyên tố, 24 – 1 = 15 là hợp số vì 4 không là nguyên tố, nh ưng ngược lại không đúng: ví dụ số Mersenne 2047 = 211 − 1 không là nguyên tố vì nó chia hết cho 89 và 23, mặc dù số 11 là số nguyên tố. Hiện nay, các số nguyên tố lớn nhất được tìm thấy thường là số nguyên tố Mersenne. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 13 Phần hai: PHÂN DẠNG BÀI TOÁN VỀ SỐ NGUYÊN TỐ Trong chương này chúng ta sẽ phân dạng các bài toán về số nguyên tố cùng một số phương pháp giải, bài tập ứng dụng và đưa ra một số bài tập tương tự. Dạng 1: Các bài toán về tập hợp số nguyên tố Loại 1: Tìm tập hợp số nguyên tố Để giải quyết các bài toán dạng này ta cần vận dụng linh hoạt các tính chất của số nguyên tố, nhiều trường hợp ta kèm theo phương pháp chứng minh phản chứng. Bài toán 1: Tập hợp các số nguyên tố là vô hạn Cách 1: Cho n  , n > 2. Chứng minh n! – 1 có ít nhất một ước nguyên tố lớn hơn n. Từ đó suy ra không tồn tại số nguyên tố lớn nhất. - Gọi a = n! – 1. Do n > 2 nên a > 1 Mọi số tự nhiên lớn hơn 1 đều có ít nhất một ước nguyên tố. Gọi p là ước nguyên tố của a. Ta sẽ chứng minh p > n Thật vậy: Giả sử p  n thì tích 1.2.3......n chia hết cho p Ta có n!  p mà a  p  1\p  vô lý  p > n - Giữa n! – 1 và n có ít nhất 1 số nguyên tố. Gọi số đó là q Giả sử n là số nguyên tố lớn nhất suy ra n > 2 Theo chứng minh trên thì tồn tại q nguyên tố n < q < n! – 1  p > n  không tồn tại số nguyên tố lớn nhất  tập hợp số nguyên tố là vô hạn. Cách 2: Cho hai số tự nhiên m  n. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 14 Chứng minh rằng 22 m + 1 và 22 n + 1 nguyên tố cùng nhau. Từ đó suy ra tập hợp các số nguyên tố là vô hạn. - Giả sử m > n. Đặt m = n + r, r  N* khi đó: b = 22 m + 1 = (22 n )2 r + 1 Đặt a = 22 n + 1 ta có: b = (a – 1)2 r + 1 = ak + Z, k  (Sau khi khai triển nhị thức (a – 1)2 r ) Từ đó (a,b) = (a,2) = 1 do a là số lẻ. Gọi pn là số nguyên tố nhỏ nhất của 2 2 n + 1 (n  Z*) Theo chứng minh trên pm  pn nm . Vậy dãy số (pn) n  N là đôi một khác nhau  Tập các số nguyên tố là vô hạn. Cách 3: Chứng minh có vô số số nguyên tố bằng cách dựa vào số ước số nguyên tố của một số. Trước hết ta chứng minh với m > 2 ta có )(m > 1, từ đó suy ra có vô số số nguyên tố. Với m > 2  m – 1 > 1 và (m – 1,m) = (m,1) = 1. Do đó )(m > 1 Giả sử chỉ có k số nguyên tố p 1, p2, ...., pk Đặt m = p1.p2....pk > 2 Với mọi giá trị k nguyên sao cho 1 < k < m thì k đều có ước nguyên tố pi nào đó nên (k,m)  1. Từ đó  )(m = 1 (vì chỉ có (1,m) = 1) Vậy có vô số số nguyên tố. Bài toán 2: Có tồn tại 1000 số tự nhiên liên tiếp đều là hợp số không? Gọi A = 2.3.4.........1001 khi đó Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 15 Các số A + 2, A + 3,......, A + 1001 là 1000 số tự nhiên liên tiếp, rõ ràng các số đó là hợp số  Có tồn tại 1000 số tự nhiên liên tiếp đều là hợp số. Bài toán 3: Chứng minh mọi số nguyên tố p đều có dạng 3k  1 (k  N) Mọi số tự nhiên khi chia cho 3 có một trong các số d ư 0, 1, 2 Do đó mọi số tự nhiên đều được viết dưới một trong các dạng là: 3k, 3k + 1, 3k + 2. Vì p là số nguyên tố nên p không chia hết cho 3  p có dạng 3k + 1, 3k + 2 Mặt khác ta có 3k + 2 = 3k + 3 – 1 = 3(k + 1) – 1 = 3l – 1 Vậy với mọi số nguyên tố p đều cố dạng     13 13 k k Bài toán 4: Tìm tất cả các số nguyên tố có dạng ( 1) 2 n n  – 1 ( n  1) Giải: ( 1) 2 n n  – 1 = ( 1)( 2 ) 2 n n  p *) n = 2  p = 2, n = 3  p = 5 thỏa mãn. *) n > 3 thế thì hoặc n – 1 chẵn hoặc n + 2 chẵn nên p là hợp số.  Giá trị p cần tìm là p = 2 hoặc p = 5. Các bài tập tương tự: 1. 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ố. 2. (Iran 2008) Chứng minh rằng tồn tại vô hạn số nguyên tố p thỏa mãn 13 \(p3 + 1) 3. Chứng minh rằng: a) Mọi số nguyên tố lớn hơn 2 đều có dạng 4p  1 (p > 0) Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 16 b) Mọi số nguyên tố lớn hơn 3 đều có dạng 6p  1 (p > 0) Loại 2: Các bài toán áp dụng định lí cơ bản của số học Hầu hết các bài toán dạng này cần phải dựa vào định lí cơ bản, vận dụng dạng phân tích tiêu chuẩn, phát huy một số ứng dụng của số nguyên tố. Bài toán 1: Cho số A  N, A = axbycz trong đó a, b, c là các số nguyên tố đôi một khác nhau x, y, z là các số nguyên d ương khác 0. Chứng tỏ rằng ước số của A được tính bới công thức (x + 1)(y + 1)(z + 1). Số các ước của A: - Chỉ chứa thừa số nguyên tố a là x; ch ỉ chứa thừa số nguyên tố b là y - Chỉ chứa thừa số nguyên tố c là z; chỉ chứa 2 thừa số nguyên tố a, b là xy - Chỉ chứa 2 thừa số nguyên tố b, c là yz - Chỉ chứa 2 thừa số nguyên tố a, c là xz - Chứa cả thừa số nguyên tố a, b và c là xyz. Do đó số ước của A bằng: x + y + z + xy + yz + xz + xyz +1 = (x + 1) + y(y + 1) + z(z + 1) + yz(x + 1) = (x + 1)(1 + y + z + yz) = (x + 1)[y + 1 + z(y + 1)] = (x + 1)(y + 1)(z + 1). (đpcm) Bài toán 2: N sau khi phân tích thành thừa số nguyên tố thì có dạng: N = axbycz. Biết rằng : - Khi chia N cho a thương tìm được có 252 ước số. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 17 - Khi chia N cho b, số các ước của thương tìm được ít hơn của N là 45 ước số. - Khi chia N cho c thì số ước của thương tìm được ít hơn N là 3 ước số. Tìm x, y, z ? Giải: Theo giả thiết ta có a N = ax - 1bycz; b N = ax by - 1cz; c N = ax bycz – 1 Ta có:       (3)351)z1)(y(x-1)1)(z1)(y(x (2)451)1)y(z(x-1)1)(z1)(y(x (1)2521)1)(zx(y        )(3'351)1)(y(x )(2'451)1)(z(x )'1( x 2521)1)(z(y Từ (2’) và (3’)  1)1)(z(y1)(x 2  = 45.35 Thay (1’) vào ta có: (x + 1)2. x 252 = 45.35  (x + 1)2.4 = 25x  4x2 – 17x + 4 = 0      )(4 )( 4 1 mãnthoax loaix Thay x = 4 vào (2’)  z = 8 x = 4 vào (3’)  y = 6 Vậy số thỏa mãn yêu cầu bài toán: x = 4; y = 6; z = 8 Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 18 Bài toán 3: Tìm tất cả các số tự nhiên có dạng phân tích tiêu chuẩn n = 32 và )(n = 403 Giải: Với n = 32 thì ta có 13 13. 12 12)( 11        n = 403 = 13.31 Do tính phân tích duy nhất của dạng tiêu chuẩn ta có: -         13 13 13 3112 1 1                 2 4 33 22 273 322 31 51 1 1       -         13 13 13 3112 1 1         633 142 1 1            13 13 13 3112 1 1    vô nghiệm Vậy n = 24.32 = 144 Các bài tập tương tự: 1. Cho một N có dạng pxqyrz; p, q, r là các số nguyên tố và pq – r = 3; pr – q = 9. Biết rằng các số p N , q N , r N tương ứng có ít hơn số ước số của N là 20, 12, 15. Tìm số N ? 2. Chứng minh một số là số chính phương khi và chỉ khi số ước của nó là số lẻ. 3. Tìm số nhỏ nhất có 9 ước số Biết dạng phân tích tiêu chuẩn của m =  qp và )( 2m = 15. Tính )( 3m ? Dạng2: Chứng minh một số, một biểu thức là số nguyên tố, hợp số Loại 1: Chứng minh một số, một biểu thức là số nguyên tố Thông thường để chứng minh một số, một biểu thức là số nguyên tố người ta dùng phương pháp chứng minh bằng phản chứng. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 19 Bài toán 1: Cho 2m – 1 là số nguyên tố. Chứng minh rằng m là số nguyên tố. Chứng minh: Giả sử m là một hợp số  m = p.q ( p, q > 1; p, q  N) Ta có: 2m – 1 = 2pq – 1 = 2(p)q – 1 = (2p – 1) [2p(q - 1) + 2p(q - 2) + ... + 1] Vì p > 1  2p – 1 > 1 và 2p(q - 1) + 2p(q - 2) + ... + 1 > 1  2m – 1 là hợp số. Điều này trái với giả thiết. Nếu m = 1  2m – 1 = 1 không phải là số nguyên tố. Vậy m phải là một số nguyên tố. Hay 2m – 1 là số nguyên tố  m là số nguyên tố. Bài toán 2: Chứng minh rằng nếu: 1 + 2 n + 4n ( n Z+) là số nguyên tố thì n = 3k với k  N. Giải: Đặt n = 3k.a ( n không có dạng 3k) a  1 (a,3) = 1 m = 2 3 k ( m  2; m  N) Giả sử a > 1 ta xét 2 trường hợp sau: a = 3b + 1 và a = 3b + 2 * Nếu a = 3b + 1 (b  N) ta có: 1 + 2n + 4n = (1 + m + m2) + (m3b+1 - m) + m2( m6b – m2)  1 + m + m2 vì m6b – m2  (1 + m + m2 )  (m3b – 1)  (m3 – 1)  (1 + m + m2 ) Mặt khác ta lại có: 1+ ma + m2a > 1 + m +m2 Nên : 1 + 2n + 4n là hợp số (vô lý) Nếu a = 2b + 2 (b  N) hoàn toàn tương tự ta có 1 + 2n + 4n là hợp số (vô lý). Vậy a = 1 tức n = 3k (k  N). Bài toán 3: Chứng minh rằng nếu p chia hết (p – 1)! + 1 thì p nguyên tố. Giải: Giả sử p là hợp số. Ta có: p \(p – 1)! Mặt khác theo giả thiết p\(p – 1)! + 1  p\1 ( vô lý) Vậy p phải là số nguyên tố Bài toán 4: Cho p và 8p2 + 1 là những số nguyên tố Chứng minh rằng: 8p2 + 2p + 1 cũng là một số nguyên tố. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 20 Giải: Xét số nguyên tố p có dạng     13 3 kp p Với p = 3  8p2 + 1 = 73 là số nguyên tố và 8p2 + 2p + 1 = 79 là số nguyên tố. Với p = 3k – 1  8p2 + 1 = 8(3k – 1)2 + 1 = 72k2 – 48k + 9 = 3(24k2 – 16k + 3)  3 (vô lý vì 8p2 + 1 là số nguyên tố). Với p = 3k + 1  8p2 + 1 = 8(3k + 1)2 + 1 = 72k2 + 48k + 9 = 3(24k2 + 16k + 3)  3 (vô lý vì 8p2 + 1 là số nguyên tố). Vậy p = 3 thì 8p2 + 2p + 1 là số nguyên tố. Các bài tập tương tự: 1. Cho 3n – 2n là lũy thừa của 1 số nguyên tố với n nguyên dương. Chứng minh n nguyên tố 2. Cho p là một số nguyên tố dạng 4k + 3, a và b là các số nguyên. Chứng minh: Nếu a2 + b2  p thì a, b đều chia hết cho p. 3. Số a4 + a2 + 1 có thể là một số nguyên tố không? Loại 2: Chứng minh một số, một biểu thức là hợp số Các bài toán dạng này thường dùng để chứng minh một số, một biểu thức nào đó là hợp số, chủ yếu dựa vào tính chất chia hết và không chia hết của một số nguyên hoặc có thể đưa về dạng đồng dư với 0 theo mod p (với p nguyên tố) để kết luận số đó là hợp số. Bài toán 1: Cho p  5 là một số nguyên tố và 2p + 1 cũng là một số nguyên tố. Chứng minh rằng 4p + 1 là hợp số Giải: Xét tích: 4p(4p + 1)(4p + 2) = 8p(4p + 1)(2p + 1) Vế trái của đẳng thức là tích của ba số nguyên liên tiếp nên nó chia hết cho 3. Do (3,8) = 1, (p,3) = 1 và (2p + 1, 3) = 1 nên 4p + 1 chia h ết cho 3 Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 21 Mặt khác 4p + 1  21 nên nó là hợp số. Bài toán 2: Cho a, b, c  thỏa mãn ab = cd. Chứng minh rằng A = an + bn + cn + dn là hợp số  n  Giải: Giả sử (a,c) = t . Khi đó ta có     1 1 tcc taa với (a1,c1) = 1 Từ ab = cd  a1b = c1d mà (a1,c1) = 1 nên b  c1 Đặt b = kc1  c1d = a1kc1 c1d = k a1 Khi đó: A = an + bn + cn + dn = tna n1 + k nc n1 + t nc n1 + k na n1 = tn(a n1 + c n1 ) + k n(a n1 + c n1 ) = (tn + kn)( a n1 + c n1 ) Vì t, k, a1, c1  nên  A là hợp số. Bài toán 3: Chứng minh rằng 2 1102 n + 19 là hợp số Giải: Ta sẽ chứng minh 2 1102 n + 19  23 ( )1 n Thật vậy: Do (2,23) = 1 nên 2 )23(  222  1 (mod 23) Giả sử 210n + 1 = 22q + r 0 < r < 22  210n = 11q + r’ Do (2,11) = 1 nên 2 )11(  210  1 (mod 11) Do đó: 210n  1 (mod 11)  r’ = 1 Từ đó 210n + 1 = 22q + 2. Theo mođun 23 ta có: 2 1102 n = 222q.22  4 (mod 23)  2 1102 n + 19  0 (mod 23)  2 1102 n + 19  23  2 1102 n + 19 là hợp số (đpcm) Các bài tập tương tự: 1. (IMO 2001) Cho a, b, c, d là các số nguyên dương thỏa mãn a > b > c > d và ac + bd = k(b + d + a – c) với k  . Chứng minh rằng ab + cd không là số nguyên tố. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 22 2. Chứng minh rằng: Tồn tại k sao cho 2 nk + 1 là hợp số n  3. Cho n  . Chứng minh các số sau là hợp số: a) A = 2 122 n + 3 b) B = 2 142 n + 7 c) C = 2 162 n + 13 Dạng 3: Tìm số x thỏa mãn điều kiện cho trước Những bài toán thuộc dạng này được giải quyết dựa trên cơ sở phân tích các dữ liệu của bài toán hay yêu cầu của bài toán để quy về một tính chất nào đó rồi dùng phương pháp suy luận, loại trừ để giải. Loại 1: Tìm số nguyên tố p thỏa mãn một số điều kiện cho trước Bài toán 1: Tìm tất cả các số nguyên tố p sao cho tổng tất cả các ước tự nhiên của p4 là một số chính phương. Giải: Ta có: )( 4p = 1 + p + p2 + p3 + p4 p > 0 Giả sử )( 4p = 1 + p + p2 + p3 + p4 = n2  4 + 4p + 4p2 + 4p3 + 4p4 = 4n2 Dễ thấy : (2p2 + p)2 < (2n)2 < (2p2 + p + 2)2 Nên (2n)2 = (2p2 + p + 1)2  4 + 4p + 4p2 + 4p3 + 4p4 = 4p4 + 4p3 + 5p2 + 2p + 1  p2 – 2p – 3 = 0      )(3 )(1 mãnthoap loaip Với p = 3 ta có )3( = 1 + 3 + 32 + 33 + 34 = 121 = 112 Vậy p thỏa mãn yêu cầu bài toán. Bài toán 2: (olympic bungari 1996). Tìm tất cả các số nguyên tố p, q sao cho pq\(5p – 2q)(5q – 2p) Giải: Không mất tính tổng quát giả sử p  q Dễ thấy : (5p – 2q)(5q – 2p) là số lẻ nên p, q khác Nếu 3  5 – 2  5k – 2k (mod k) thì k = 3 Ta sẽ c\m một trong 2 số p, q tồn tại ít nhất 1 số bằng 3. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 23 Giả sử phản chứng p, q  3 Do đó : p\(5p – 2q) hay 5p  2q (mod p) Tiếp theo ta có nhận xét rằng : Nếu (a,m) = (b,m) = 1 và ax  bx (mod m), ay  by (mod m) thì : a(x,y)  (x,y) (mod m) Mặt khác theo định lí Fermat thì : 5p – 1  2p – 1 (mod p). Khi đó áp dụng nhận xét ta được : 5(p – 1,q)  2(p – 1,q) (mod p). Rõ ràng : (p – 1,q) = 1. Do đó : 5  2 (mod p).  p = 3 mâu thuẫn. Vậy p = 3. Nếu q > 3 thì q\(5q – 2p) = 53 – 23 = 9.13 và vì thế q = 13 Còn nếu q = 3 dễ dàng kiểm tra thấy thỏa mãn. Vậy tất cả các bộ (p,q) là (3,3); (3,13); (13,3) Bài toán 3: Tìm 3 số nguyên tố p; q; r sao cho pq + qp = r. Giải: Giả sử có 3 số nguyên tố p; q; r sao cho p q + qp = r. khi đó r >3  r lẻ. Vậy p; q không cùng tính chẵn, lẻ nên phải có một số nguyên tố chẵn là 2. Giả sử p = 2 khi đó 2q + q2 = r +) Nếu q không chia hết cho 3  q2  1 ( mod 3) Mặt khác q lẻ  2q – 1 ( mod 3)  2q + q2  3 ( không nguyên tố). Vậy q  3, q nguyên tố  q = 3 Khi đó r = 23 + 32 = 17 Do p, q có vai trò như nhau nên có thể p = 3 ; q = 2 Vậy có 2 bộ số được tìm là (2; 3; 17) và ( 3; 2; 17) Các bài tập tương tự: 1. Tìm số nguyên tố p thỏa mãn điều kiện p\(2p + 1) 2. Tìm số nguyên tố p sao cho: a) 2p + 1 là lập phương của một số tự nhiên. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 24 b) 13p + 1 là lập phương của một số tự nhiên. 3. Cho p là một số nguyên tố dạng 4k + 3, a và b là các số ngu yên. Chứng minh: Nếu a2 + b2  p thì a, b đều chia hết cho p. 4. Tìm số nguyên tố p sao cho a) 8p2 + 1 và 8p2 – 1 là những số nguyên tố b) p + 2, p + 6 và p + 8 là những số nguyên tố. c) p + 10, p + 14 là những số nguyên tố. Loại 2: Tìm số tự nhiên n để một số, một biểu thức là số nguyên tố Bài toán 1: Tìm số tự nhiên n để A = n1997 + n1996 + 1 là số nguyên tố Giải: ta có: Trường hợp 1: n = 0 thì A = n1997 + n1996 + 1 không là số nguyên tố Trường hợp 2: n = 1 thì A = n1997 + n1996 + 1 = 3 là số nguyên tố. Trường hợp 3: n > 1 ta có A = n1997 + n1996 + 1 = (n1997 – n2) + (n1996 – n) + ( n2 + n + 1) = n2(n1995 – 1) + n(n1995 – 1) + (n2 + n + 1) = ( n2 + n)(n1995 – 1) + (n2 + n + 1) Ta có: n1995 – 1 = (n3)665 – 1 = ( n3 – 1) [(n3)664 + (n3)663 +.......+ n2 + 1] = ( n – 1)( n2 + n +1)[(n3)664 + (n3)663 +.......+ n2 + 1]  ( n2 + n + 1) Do n > 0  n2 + n + 1 > 1. Vì vậy để n1997 + n1996 + 1 là số nguyên tố thì n1997 + n1996 + 1 = n2 + n + 1  n = 1. Bài toán 2: Tìm n  để B = n4 + 4n là số nguyên tố Giải: Trường hợp 1: n = 0 thì B = n4 + 4n = 1 không là số nguyên tố Trường hợp 2: n = 1 thì B = n4 + 4n = 5 là số nguyên tố Trường hợp 3: n > 1 - Nếu n chẵn thì B = n4 + 4n  2 mà n4 + 4n > 2 nên n4 + 4n là hợp số. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 25 - Nếu n lẻ đặt n = 2k + 1 ta có: B = n4 + 4n = n4 + 42k + 1 = n4 + (2.4k)2 = (n2 + 2.4k)2 – 2n2.2.4k = (n2 + 2.4k)2 – (2n.2k)2 = (n2 + 2.4k - 2n.2k)( n2 + 2.4k + 2n.2k) = (n2 – 2n.2k + 22k + 22k) (n2 + 2n.2k + 22k + 22k) = [(n – 2k)2 + 22k] [(n + 2k)2 + 22k] là hợp số Do [(n – 2k)2 + 22k] > 1; [(n + 2k)2 + 22k] > 1 Vậy n = 1 thỏa mãn yêu cầu bài toán. Bài toán 3: Tìm các số tự nhiên m; n để: A = 3 23 6 61m n  + 4 là số nguyên tố. Giải: Ta có 3m2 + 6n – 61 chia 3 dư 2. Ta đặt 3m2 + 6n – 61 = 3k + 2 (k N)  A =33k + 2 + 4 = 9.27k + 4 Dễ thấy rằng 9.27k  9 (mod 13)  9.27k + 4  13. Để A nguyên tố thì A = 13  33k + 2 = 9  k = 0 3m2 + 6n – 61 = 3k + 2 = 2 (vì k = 0)  3m2 + 6n – 63 = 0  m2 + 2n – 21 = 0  n < 11. Do 2n chẵn  m2 phải là số lẻ  m2 = 1, m2 = 9  Nếu m2 = 1  m = 1, n =10.  Nếu m2 = 9  m = 3; n = 6. Vậy các giá trị cần tìm là (1, 10) ; (3, 6) Các bài tập tương tự: 1. Tìm n  để a) n2009 + n2008 + 1 là số nguyên tố b) n3 – n2 + n – 1 là số nguyên tố 2. Chứng minh rằng nếu an + 1 là số nguyên tố với a > 1 thì n = 2 k với k  . 3. Tìm tất cả các số n sao cho: a. n4 + n2 + 1 là số nguyên tố. c. n1998 + n1997 + 1 là số nguyên tố. b. n3 – n2 + n – 1 là số nguyên tố. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 26 Dạng 4: Áp dụng giải phương trình nghiệm nguyên, chia hết Đây là dạng bài toán tổng hợp, cần sử dụng nhiều phương pháp phối hợp để giải các bài toán. Cần chú ý đến tính chia hết trong vành số nguyên để vận dụng phù hợp vào các bài toán. Bài toán 1: Giải phương trình nghiệm nguyên dương x2 – y3 = 7 * Mệnh đề: Cho p là một số nguyên tố dạng 4k + 3, a và là số nguyên. Khi đó nếu a2 + b2  p thì a và b đều chia hết cho p Chứng minh: Giả sử a và b đều không chia hết cho p Theo định lí nhỏ Fermat ta có:       pb pa p p   1 1 1 1        pb pa k k   1 1 24 24  a4k + 2 + b4k + 2 – 2  p  (a2)2k + 1 + (b2)2k + 1 – 2  p Vì (a2)2k + 1 + (b2)2k + 1 – 2  a2 + b2 nên  a4k + 2 + b4k + 2  p nên 2  p (vô lý) Vậy a  p hoặc b  p. Giải: x2 – y3 = 7  x2 + 1 = y3 + 8  x2 + 1 = y3 + 23  x2 + 1 = (y + 2)(y2 – 2y + 4) (2) - Nếu y chẵn thì vế phải (2) chia hết cho 4 nên x lẻ Đặt x = 2t + 1  x2 + 1 = 4t2 + 4t + 2 không chia hết cho 4 (loại) - Nếu y lẻ, x chẵn: Đặt y = 2k + 1  y2 – 2y + 4 = (2k + 1)2 – 2(2k + 1) + 4 = 4k + 3 nên nó có ư ớc nguyên tố lẻ dạng 4k + 3  x2 + 1 có ước nguyên tố dạng 4m + 3 (*) Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 27 Mặt khác ta có: Nếu (a,b) = 1 thì mọi ước nguyên tố lẻ của a2 + b2 chỉ có dạng 4m + 1 m   x2 + 1 có ước nguyên tố dạng 4m + 3 (mâu thuẫn) Vậy phương trình không có nghiệm nguyên dương. Bài toán 2: Tìm số nguyên dương x, y, z thỏa mãn hệ phương trình     222 222 13 13 tyx zyx (*) Giả sử (xo, yo, zo, to) là một nghiệm của hệ (*) Đặt (xo, yo) = d  zo  d Đặt xo = dx1 (x1, y1, z1 nguyên dương) yo = dy1 (x1, y1) = 1 zo = dz1 Từ hệ (*) ta có: 14(xo2 + yo2) = zo2 + to2  14(x12 + y12) = z12 + t12  z12 + t12  7 Theo mệnh đề ta có z1  7, t1  7  z12 + t12  49  x12 + y12  7 Áp dụng mệnh đề ta có: x1  7, y1  7. Điều này mâu thuẫn với giả thiết (x1, y1) = 1 Vậy phương trình đã cho không có nghiệm nguyên. Bài toán 3: Chứng minh với mọi số nguyên tố p > 2, thì tử số m của phân số tối giản 1 1...... 3 1 2 11  pn m chia hết cho p. Giải: Cách 1: Ta thấy tử số của phân số n m chính là  1 )!1(p i i p Cần chứng minh biểu thức đó chia hết cho p. Ta thấy có tất cả p – 1 số hạng, ta sẽ chia chúng thành từng cặp có t ổng chia hết cho p như sau : Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 28 ) )( )!1((.) )( )!1(())!1()!1(()!1( 2 1 1 2 1 1 1 1 2 1 1 ipi ppp ipi pp ip p i p i p p i p i p i p i               Tổng còn lại rõ ràng là số nguyên nên biểu thức trên chia hết cho p. Ta có đpcm. Cách 2: Do p là số nguyên tố lớn hơn 2 nên (p – 1) là số chẵn do đó ta có thể chia các số hạng của tổng thành 2 1p nhóm. Ta có: Do p là số nguyên tố mà các thừa số ở mẫu thì nhỏ h ơn p nên sau khi giản ước ở tử số vẫn còn thừa số p.  m  p Ta được đpcm. Các bài tập tương tự: 1. Tìm các nghiệm nguyên dương của các phương trình: a) 19x2 + 28y2 = 729 b) x2 + y2 = 3z2 c) x2 + y2 = 1210 2. (Chọn đội tuyển quốc gia Cộng Hòa Liên Bang Đức 1979) Cho x, y  sao cho yx yx   22 là số nguyên và là ước của 1978. Chứng minh rằng: x = y 3. Chứng minh rằng nếu p là số nguyên tố lẻ thì:         2 1 1 2 1 1 22 p i p p i pi ii chia hết cho p. Dạng 5: Áp dụng, chứng minh một số bổ đề, định lí có ứng dụng trong giải các bài toán về số nguyên tố Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 29 Thông thường các bài toán ở dạng này đều vận dụng chặt chẽ các định lý, mệnh đề, hệ quả để lập luận giải quyết bài toán một cách tối ưu nhất. * Bổ ®Ò: Giả sử p =2t.k + 1 là số nguyên tố lẻ với t, k là các số tự nhiên, k là số tự nhiên lẻ. Khi đó, nếu các số tự nhiên x, y sao cho x2 t + y2 t  p thì x và y đồng thời chia hết cho p. Chứng minh bổ đề: Ta sử dụng phép chứng minh bằng phản chứng. Giả sử x không chia hết cho p, từ giả thiết suy ra y cũng không chia hết cho p. Theo định lí nhỏ Fec-ma ta có: xp – 1  1 (mod p), yp – 1  1 (mod p) Hay: x2 t .k  1 (mod p), y2 t .k  1 (mod p) Suy ra: x2 t .k + y2 t .k  2 (mod p) Mà theo giả thiết x2 t + y2 t  0 (mod p) nên x2 t .k + y2 t .k  0 (mod p) (Do k lẻ) Vậy điều giả sử trên của ta là sai. Tóm lại ta có đpcm. Bài toán 1: T×m tÊt c¶ c¸c cÆp sè ( x, y) *N sao cho 2 2x y x y   *N vµ lµ ­íc cña 1995 Gi¶ sö 2 2x y x y   = k nguyªn d­¬ng vµ k là ­íc sè cña 1995 = 5.3.7.19 = 5n víi n = 3.7.19 C¸c sè nguyªn tè cã d¹ng 2(2m+1)+1 = 4m+3 Gäi ¦CLN cña x vµ y lµ d = (x,y) th× x = du vµ y = dv víi (u,v)=1 Tõ gi¶ thiÕt => d( 2 2u v ) = k(u-v) (1) Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 30 XÐt 2 Tr­êng hîp : 1) n  k th× k cã ­íc nguyªn tè d¹ng 4m+3 Áp dông bæ ®Ò vµo (1) => 2 2u v kh«ng chøa c¸c ­íc nguyªn tè cña k nªn k lµ ­íc sè cña d => d = kt  t.(u2 + v2) = u – v => u2 + v2 < u – v  (1) v« nghiÖm 2) k = 5m víi m lµ ­íc cña n Lóc ®ã (1) trë thµnh d(u2 + v2) = 5m(u – v)  d = mt ( t­¬ng tù nh­ trªn)  t.(u2 + v2) = 5( u – v) (2) Tõ (2) cã u2 + v2  5(u – v) => A= u2 + v2 – 5(u – v)  0 (3) MÆt kh¸c 4A = 4u2 – 20u + 25 + 4v2 +20v 25 – 50 = (2u – 5)2 + (2v + 5)2 – 50  12 + 72 – 50  0  A  0  A = 0 DÔ dµng gi¶i tiÕp Bài toán 2: Chứng minh “ định lí nhỏ Fermat”: “ p chia hết ap -1 – 1 khi p là nguyên tố và a là số nguyên tố cùng nhau với p”. Một cách tổng quát hơn: “ Nếu p là số nguyên tố và m và n là các số nguyên dương thỏa mãn m  n (mod p – 1), thì nm aaa  : (mod p)” Giải: Cách 1: Quy nạp theo a. Nếu a = 1 thì điều cần chứng minh là đúng. Giả sử mệnh đề đúng với a = k > 0, ta có (k + 1)p – (k + 1) =   p i ii p kkC 0 1 =    11 )( pi ii p p kCkk Dùng giả thiết quy nạp và 1,1/  piCp ip ta có (k + 1)p – (k + 1) chia hết cho p. Cách 2: Còn một cách chứng minh nữa cho định lí Fermat bé là dùng tổ hợp như sau: Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 31 Ta giải bài toán sau: Một đường tròn được chia thành p cung bằng nhau. Hỏi có bao nhiêu cách tô màu các cung bằng a màu? Ha i cách tô thu được qua một phép quay được coi là giống nhau. Lời giải: Ta đánh số các cung từ 1 đến p. Nếu không tính đến phép quay thì có ap cách tô các cung. Nếu tính đến phép quay thì mỗi một cách tô có 2 màu trở lên sẽ nằm trong 1 lớp với p cách tô khá c. Có a cách tô chỉ dùng 1 màu. Vì thế số cách tô sẽ là a + p aa p  Vì số cách tô phải là một số nguyên nên ta có điều phải chứng minh. Ta xÐt 1 bµi thi trong ®Ò thi HSG líp 12 tØnh B×nh §Þnh n¨m (2009): Ứng dụng: Cho n là số nguyên dương sao cho 3n – 1 chia hết cho 22009. CMR: n  22007 Gi¶i: Xét 3n  1 (mod 22009). Theo định lí Fermat, ta có (3,22009) = 1 nên ta được: 3 20092 - 1  1 (mod 22009)  n = 22009 – 1 hoặc n = a + 22009 – 1 (với a *N ). Dễ thấy 22009 – 1 và 22009 – 1 + a lớn hơn 22007, nên ta có điều phải chứng minh. Bài toán 3: Chứng minh mệnh đề: Với p là một số nguyên tố và (a,p) = 1 thì (ap – a)  p với mọi a  Giải: - Với a = 1 thì mệnh đề đúng vì (ap – a) = 1 – 1 = 0 chia hết cho mọi số. - Giả sử mệnh đề đúng với a nào đó nghĩa là: (ap – a)  p Ta sẽ chứng minh mệnh đề đúng với a + 1 Thật vậy, Áp dụng phân tích đa thức Niuton ta được: (a + 1)p – (a + 1) = ap + pf(a) + 1 – a – 1 = ap – a + pf(a)  p Vì (ap – a)  p Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 32 Pf(a)  p, ở đây f(a) là đa thức bậc p – 1 theo a, do áp dụng công thức hệ số Niuton với các thừa số có p đưa ra ngoài lập ra f(a) Vậy mệnh đề đúng với a + 1 theo nguyên lí quy nạp toán học mệnh đề đúng với mọi a  1 (đpcm). * Mệnh đề: Với một số nguyên a, số a2 + 1 không có ước nguyên tố dạng 4k + 3 Bài toán 4: Giải phương trình nghiệm nguyên dương 4xy – x – y = z2. Giải: Phương trình đã cho 4xy – x – y = z2  (4x – 1)(4y – 1) = (2z)2 + 1 (1) Giả sử (xo, yo, zo) là nghiệm nguyên dương của phương trình (1) Ta có: (4xo – 1)(4yo – 1) = (2zo)2 + 1 Vì 4xo – 1 là số nguyên tố dương không nhỏ hơn 3 và có dạng 4k + 3. nên nó có ít nhất một ước nguyên tố p dạng 4k + 3. Nhưng theo mệnh đề trên thì (2z)2 + 1 không có ước nguyên tố dạng 4k + 3. Do đó phương trình (1) vô nghiệm Vậy phương trình đã cho không có nghiệm nguyên dương. Các bài tập tương tự: 1. Chứng minh định lí Fermat nhỏ: Nếu p là số nguyên tố và (a,p) = 1 thì (ap – 1 – 1)  p  a  . 2. Cho số nguyên tố dạng p = 4k + 3. CMR: Nếu các số tự nhiên x, y thỏa mãn x2 + y2  p và y đều chia hết cho p. 3. Cho số nguyên tố dạng p = 4k + 1, k là số tự nhiên lẻ. CMR: Nếu các số tự nhiên x, y thỏa mãn x4 + y4  p thì x và y đều chi hết cho p. 4. Giả sử a, b là hai số tự nhiên khác 0 nguyên tố cùng nhau. Khi đó các ước số nguyên tố lẻ của a2 + b2 chỉ có dạng 4m + 1 với m là số tự nhiên. Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 33 Dạng 6: Các dạng khác Bài toán 1: Chứng minh rằng: Nếu a2 – b2 là một số nguyên tố thì a2 – b2 = a + b Ta có a2 – b2 = (a + b)(a – b) mà (a + b) > (a – b) kết hợp với a2 – b2 là số nguyên tố ta suy ra a – b = 1 Nên a2 – b2 = a + b Bài toán 2: Tìm 3 số nguyên tố sao cho tích của chúng gấp 5 lần tổng của chúng. Giải: Gọi 3 số nguyên tố đó là a, b, c lúc đó ta có: a.b.c = 5( a + b + c )  5  abc . mà a, b, c nguyên tố nên một trong 3 số phải bằng 5 Giả sử a = 5  b.c = 5 + b + c  ( b – 1)(c – 1) = 6        7 2 61 11 c b c b        4 3 31 21 c b c b  Trường hợp này loại vì c = 4 không nguyên tố. Vậy bộ 3 số nguyên tố cần tìm là (2; 5; 7) Bài toán 3: Số n = 561 thuộc loại số giả nguyên tố n ào? Giải: Số n = 561 = 3.11.17 là một hợp số Lấy a = 2 ta có:       )17(mod1)2(2 )11(mod1)2(2 )3(mod142 3516560 5610560 280560 2560  1 (mod 561) Do đó Số n = 561 là số giả nguyên tố Fermat c ơ sở 2. Bài toán 4: Chứng minh rằng với p là số nguyên tố lớn hơn 2 có vô số số tự nhiên thỏa mãn p\(n.2n – 1) Giải: Ta có 2p – 1  1 (mod p) Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 34 Ta cần tìm n = m(p – 1) sao cho n.2n  1 (mod p) n.2n = m(p – 1).2m(p – 1)  n.2n = m(p – 1).2m(p – 1)  m(p – 1) (mod p) (do 2p – 1  1 (mod p)) Do n.2n  1 (mod p) nên m(p – 1)  1 (mod p)  (mp – m – 1)  p  ( – m – 1)  p  m = kp – 1 Vậy với n = (kp – 1)(p – 1) với (k  N) thì (n.2n – 1)  p Mà k  N nên có vô số số tự nhiên n thỏa mãn p\(n.2n – 1) Các bài tập tương tự: 1. (Việt Nam TST 2003) Cho n là 1 số nguyên dương. Chứng minh rằng không có ước nguyên tố dạng 8k – 1 với k nguyên dương. 2. (IMO lần thứ 37) Giả sử a, b là các số nguyên dương sao cho 15a + 16b và 16a – 16b đều là các số chính phương. Tìm giá trị nhỏ nhất của số nhỏ nhất trong hai số chính phương ấy. 3. Cho p là số nguyên tố. Chứng minh 7p + 3p – 1 không là số chính phương. * Ứng dụng số nguyên tố trong đời sống: Toán học không chỉ là lí thuyết. Nó có vai trò rất l ơn trong khoa học ngày nay. Trước khi kết thúc chuyên đề ta cùng thư giãn một chút và cũng để hiểu từ đầu đến giờ ta học số nguyên tố để làm gì? Đầu tiên là trong ngành bảo mật. Chắc chắn rất nhiều ng ười từng nghe qua việc dùng toán học trong mật mã hóa, tuy vậy có thể đã quên, chủ đề này được tạo với mục đích giới thiệu về ứng dụng của toán học trong mật mã hóa, vì trình độ có hạn Những khái niệm cần thiết - Hàm số Eurler (kí hiệu là φ ): Cho n tự nhiên, khi đó φ(n) = số các số tự nhiên nhỏ hơn n và nguyên tố cùng nhau với n. Viết dưới dạng tập hợp: Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 35 A = { u| 0 φ(n) = card(A). - Căn nguyên thủy: Cho n tự nhiên, khi đó a được gọi là căn nguyên thủy của n nếu: (i) 1 (ii) (a,n)=1 (iii) a^d != 1 (mod n) với mọi 0 - Định lí : Nếu p nguyên tố, a là một căn nguyên thủy của p, khi đó với mọi b thuộc Z\pZ có thể viết được dưới dạng b = a^i trong đó 0 < i < p-2 Từ định lí này suy ra: I. Bây giờ chúng ta sẽ cùng tìm hiểu một số ph ương pháp mã hóa: ffice:smarttags" \>I. Chia sẻ chìa khóa: A và B muốn có chung 1 chìa khóa, họ sẽ chọn : - p nguyên tố và công khai. - a căn nguyên thủy của p, a công khai - Mỗi nguời một số bí mật Xa và Xb với 1 < Xa, Xb < p -1 A sẽ gửi cho B a^Xa (mod p) B sẽ gửi cho A a^Xb (mod p) Khi đó, A và B sẽ cùng có chung 1 chìa khóa K = a^(Xa.Xb) (mod p) II. Mã hóa "không chìa khóa": Cho 1 thông tin (dưới dạng số) M < p, A cần gửi M cho B 1. A chọn a < p, (a,p-1)=1 (a bí mật) B chọn b < p, (b,p-1)=1 (b bí mật) 2. A gửi cho B số C = M^a (mod p) 3. B gửi lại cho A số D = C^b (mod p) 4. A tính a' sao cho 0 < a' < p và a.a' = 1 (mod p-1) (a' được gọi là nghịch đảo (mod p-1) của a), sau đó gửi cho B số E = D^a' = C^(b.a') = M^(a.b.a') Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 36 5. B tính nghịch đảo b' của b, sau đó tính E^b' = M^(aba'b') = M (mod p) vì aa' = bb' = 1 (mod p-1) và theo định lí nhỏ Fermat, M^(p-1) = 1 (mod p) III. Mã hóa với chìa khóa công khai p nguyên tố, p công khai N người muốn chia sẻ thông tin một cách bí mật, họ sẽ chọn: a căn nguyên thủy của p (như thế hàm số mũ đông dư của a sẽ là song ánh), mỗi người 1 số bí mật Xn, với 1 < Xn < p-1 Họ công khai Yn = a^Xn (mod p) IV. Hệ thống RSA Đây là hệ thống mã hóa khá thông dụng hiện nay, lấy tên từ thuật toán RSA, do Rivest, Shamir, Adelman tìm ra vào n ăm 1977. Người sử dụng muốn trao đổi thông tin: - Chọn 2 số nguyên tố p và q - Tính n = pq - Chọn d (lớn) và nguyên tố cùng nhau với φ(n) = (p-1)(q-1) - Tính e nghịch đảo của d mod (p-1)(q-1) Công khai e và n. A muốn gửi thông tin M cho B, A sẽ gửi C = M^e (mod n) B muốn tìm lại M sẽ tính C^d = M^(ed) = M (mod n) Chú ý rằng thông tin bị che giấu ở đây là hai số p và q, như chúng ta đều biết, cho trước 1 số tự nhiên, việc phân tích thành thừa số nguyên tố đòi hỏi 1 khoảng thời gian rất lớn (với những thuật toán hiện đại) Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 37 C - KẾT LUẬN Quá trình học tập và nghiên cứu về số nguyên tố đã giúp chúng tôi cũng như nhiều bạn sinh viên tìm thấy niềm vui, sự thú vị khi học toán. Dẫu biết rằng hiểu biết của mình vẫn còn hạn hẹp, chỉ là giọt n ước trên biển cả tri thức, tuy nhiên qua đề tài này chúng tôi cũng đã rút ra cho mình nhiều kinh nghiệm, nhiều hiểu biết mới lạ. Đề tài trên đây không thể đề cập được hết tất tất cả các dạng toán mà chỉ nêu lên một số dạng toán cơ bản và cách giải quyết của nó. Chúng tôi cũng hi vọng rằng với khối lượng kiến thức nhỏ gọn trên đây cũng phần nào giúp được các bạn học sinh, sinh viên trong việc giải quyết những khó khăn khi gặp bài toán về số nguyên tố. Trên đây là một vài suy nghĩ, kinh nghiệm kiến thức mà qua quá trình học tập, tìm hiểu của chúng tôi tích lũy được, thiết nghĩ rằng đây cũng là một vấn đề quan trọng để nâng cao hiệu quả việc học tập nghiên cứu. Chắc chắn trong đề tài còn có nhiều thiếu sót và có những hạn chế nhất định. Kính mong sự đóng góp ý kiến chân thành của quý thầy cô và các bạn để đề tài được hoàn thiện hơn. Hà Tĩnh, ngày tháng năm 2010 Ngư ời làm đề tài Nguyễn Cao Thiện Ngô Thị Kim Nhung Tìm hiểu lí thuyết – phân dạng bài tập về số nguyên tố 38 TÀI LIỆU THAM KHẢO 1) Nâng cao và phát triển toán 6 (tập 1) - Vũ Hữu Bình 2) Toán nâng cao và các chuyên đề toán 6 - Vũ Dương Thụy, Nguyễn Ngọc Đạm 3) 500 bài toán chọn lọc 6 - Ngô Long Hậu, Nguyễn Ngọc Đạm 4) Bài tập số học - Nguyễn Tiến Quang 5) Giáo trình số học - Lại Đức Thịnh 6) Lí thuyết số - Nguyên Hữu Hoan 7) Chuyên đề số ngyên tố - Lê Huy Toàn 8) Internet