Tài liệu Cấp số nguyên căn nguyên thuỷ và ứng dụng

SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT CHUYÊN VĨNH PHÚC CHUYÊN ĐỀ CẤP SỐ NGUYÊN, CĂN NGUYÊN THUỶ VÀ ỨNG DỤNG Họ và tên: Nguyễn Duy Liên Giáo viên tổ: Toán--Tin Trường: THPT Chuyên Vĩnh Phúc Vĩnh Yên: Tháng 6 -Năm 2013 1 PHẦN I .BẢNG CÁC KÝ HIỆU � : Tập hợp các số tự nhiên :  0;1;2;3;... �* : Tập hợp các số tự nhiên khác 0 :  1;2;3;... Z : Tập hợp các số nguyên :  ...; 3; 2; 1;0;1;2;3;... � : Tập hợp các số nguyên tố � � : : Tập hợp các số hữu tỉ Tập hợp các số phức � : Tập hợp các số thực x �Z : x thuộc Z ; x là số nguyên aM b : a chia hết cho b , a là bội của b b aM : a không chia hết cho b b|a : b là ước của a , b chia hết a b | a : b không là ước của a a �b  mod m  : a đồng dư với b theo môđun m , a  b chia hết cho m  a, b  : ƯCLN của a và b  a, b  : BCNN của a và b  a; b  : cặp số ,nghiệm của phương trình hai ẩn số � : Suy ra � : Tương đương với ,khi và chỉ khi (đpcm) : Điều phải chứng minh , kết thúc bài toán hay một phép chứng minh , : Tồn tại,mọi ,hoặc, giao , , ��   n  : Hàm Ơle của số nguyên dương n LỜI NÓI ĐẦU 2 Ngạn ngữ Pháp có câu: "Le Mathématique est le Roi des Sciences mais L’Arithmétique est la Reine",dịch nghĩa:"Toán học là vua của các khoa học nhưng Số học là Nữ hoàng". Điều này nói lên tầm quan trọng của Số học trong đời sống và khoa học. Số học giúp con người ta có cái nhìn tổng quát, sâu rộng hơn, suy luận chặt chẽ và tư duy sáng tạo. Trong các kì thi chọn học sinh giỏi các cấp THCS, THPT cấp tỉnh, cấp Quốc gia,cấp khu vực, cấp quốc tế, các bài toán về Số học thường đóng vai trò quan trọng. Chúng ta có thể làm quen nhiều dạng bài toán Số học, biết nhiều phương pháp giải, nhưng cũng có bài chỉ có một cách giải duy nhất. Mỗi khi gặp một bài toán mới chúng ta lại phải suy nghĩ tìm cách giải mới. Sự phong phú đa dạng của các bài toán Số học luôn là sự hấp dẫn đối với mỗi giáo viên, học sinh giỏi yêu toán. Xuất phát từ những ý nghĩ đó tôi đã sưu tầm và hệ thống lại một số bài toán để viết lên chuyên đề "Cấp số nguyên, căn nguyên thuỷ và ứng dụng ” Chuyên đề gồm các phần : -Báng các kí hiệu - Lời nói đầu -Phần I: Kiến thức cơ bản. -Phần II:Ứng dụng Ứng dụng 1: Ứng dụng trong giải các bài toán chứng minh chia hết Ứng dụng 2: Ứng dụng trong giải các bài toán tìm số nguyên thoả mãn tính chất cho trước Phần III: Bài tập tương tự. Phần IV: Tài liệu tham khảo Mục tiêu ở đây là một số bài mẫu, một số bài khác biệt căn bản đã nói lên được phần chính yếu của chuyên đề. Tuy vậy, những thiếu sót nhầm lẫn cũng không thể tránh khỏi được tất cả , về phương diện chuyên môn cũng như phương diện sư phạm. Lối trình bày bài giải của tôi không phải là một lối duy nhất. Tôi đã cố gắng áp dụng cách giải cho phù hợp với chuyên đề, học sinh có thể theo mà không lạc hướng. Ngoài ra lúc viết tôi luôn luôn chú ý đến các bạn vì nhiều lí do phải tự học, vì vậy giản dị và đầy đủ là phương châm của tôi khi viết chuyên đề này. Tôi xin trân thành cảm ơn các thầy cô giáo,các em học sinh góp ý thêm cho những chỗ thô lâu và phê bình chân thành để có dịp tôi sửa chữa chuyên đề này hoàn thiện hơn. Vĩnh Yên, Mùa hạ , năm 2013 NGUYỄN DUY LIÊN PHẦN I. KIẾN THỨC CƠ BẢN 3 Từ định lý Ơ-Le ta có nếu m là số nguyên dương và nếu a là số nguyên , nguyên m tố cùng nhau với m thì a   �1 mod m  . Do đó , phương trình đồng dư a x �1 mod m  luôn luôn có nghiệm . Theo tính chất thứ tự tốt của tập hợp số nguyên dương , phải tồn tại số nguyên dương nhỏ nhất thoả mãn đồng dư trên. Định nghĩa 1.1 Giả sử a và m là các số nguyên dương nguyên tố cùng nhau. Khi đó số nguyên dương h nhỏ nhất sao cho a h �1 mod m  được gọi là cấp của a môđulô m . Ta kí hiệu cấp của a môđulô m bởi ord m a . Ví dụ ord5 2  4 , ord5 4  2 , ord11 5  5 .... Định lí 1.2 k i) Giả sử cấp của a mod n là h . Khi đó a �1 mod n  khi và chỉ khi k chia hết cho h . ii) Giả sử a có cấp h  mod n  , b có cấp l  mod n  và  h, l   1 thì ab có hl  mod n  . iii) Cho các số n1 , n2 , n3 , ...., nk đôi một nguyên tố cùng nhau và n  n1n2 L nk Giả sử với mỗi i , hi là cấp của a  mod ni  . Khi đó cấp của a  mod n  là h  BCNN  h1 , h2 ,..., hk  k Chứng minh i) Giả sử a �1 mod n  , nếu k  qh  r , 1 �r  h thì ta có r ak � a  ah  q a r  mod n  ar 1(mod n ). Điều này trái với cách chọn h . Vậy r  0 hay k chia hết cho h . Điều ngược lại hiển nhiên đúng. hl ii) Giả sử t là cấp của ab mod n . Ta có  ab   a hl b hl �1 mod n  � hl Mt (*), ta th cũng có 1 � ab   a thbth �bth  mod n  � th M l vì  h, l   1 � t Mh . Tương tự tMl mà do  h, l   1 nên t Mhl (**) .Từ (*) và (**) � t  hl iii) Gọi h là cấp của a  mod n  . Ta có a h �1 (mod ni ) � hi | h vậy h là một bội chung của h1 , h2 ,..., hn . Nếu l là một bội chung bất kỳ của h1 , h2 ,..., hn . Nên ta có l a l �1 mod ni   a 1(mod n) � h | l � h  BCNN  h1 , h2 ,..., hk  . Từ iii) của định lí trên ta thấy rằng bài toán tìm cấp của a môđulô n . Quy về bài s toán tìm cấp của a  mod p  , với p là số nguyên tố. s * Định lí 1.3. Cho a là số nguyên lẻ và n  2  s ��  . Giả sử a  1  2u b và a 2  1  2v c trong đó 1 �u  v, b, c là các số lẻ . Gọi h là cấp của a  mod n  . 4 1 neu u �s � Khi đó : h  �max 1,s 1v 2 neu u  s � s s Chứng minh : Ta có h |   2  � h  2 .t �s  1 . Rõ ràng nếu u �s thì a  1 Mn do đó h  1. Nếu s u h 2   h 2 4 2 t 1 . Ta có a  1   a  1  a  1 ... a  1 . t 1 Nếu u  s �v � n | a 2  1 � h  2. Nếu s  v từ đẳng thức trên suy ra a h  1  2vt 1 nó chia hết cho 2s � v � t  1 �s t s 1 v 2 vậy t bé nhất là t  s  1  v . Định lí 1.4. Cho p là số nguyên tố lẻ  a, p   1 và n  p s . Giả sử r là cấp của a  mod p  và a r  1  pu q ( với  p, q   1 ) . Gọi h là cấp của a  mod n  . Khi r khi u �s � đó h  � s u rp khi u  s � Chứng minh : Trường hợp 1. r  1 . Rõ ràng nếu u �s � h  1 . Xét u  s . Giả sử h pt h  p t q ( với  p, q   1 ). Nếu q  1 thì do a �1 mod p  � a  1  a  1 b với  p, b   1 . Vậy   a p  1 �1 mod n  trái giả thiết h là bé nhất . Vậy h  p t , t  0 . Ta t có bổ đề . n * Bổ đề : Với mọi n �� thì a p  1  p nu A ( với  p, A   1, A �� ). Chứng minh bổ đề quy nạp theo n . Với n  0 đúng . Giả sử đúng với n . Đặt n p n 1 p p 1 p2 pn b  a p ta có a  1  b  1   b  1  b  b  L  b  1  a  1 B . Ta có   b �1 mod p  , p lẻ BMp và B M  p 2 . Do đó a p  1  p n u 1 A ,  A, p   1. Bổ đề được chứng minh. h t u s  t s u 1 vậy t bé Theo bổ đề ta có a  1  p A ,  A, p   1. Vậy t �u � nhất là t  s  u � h  p s u . Trở lại Trường hợp 2. với r bất kỳ . h 1 mod   n a h 1 mod p  h lr . Đặt b  a r . Vì a h  bl dễ thấy Khi đó a �� cấp của b  mod p  là 1 và l là cấp của b  mod n  . Vậy theo trường hợp đặc biệt 1 khi u �s � r  1 áp dụng đối với b ta có l  � s u . Vậy h  rl (dpcm) p khi u  s � Tóm lại tìm cấp của một số theo mod n được quy hoàn toàn về tìm cấp theo modlô nguyên tố. Hệ quả 1.5. Nếu a và n là các số nguyên nguyên tố cùng nhau, n  0 thì ord n a |   n  n 1 5 Hệ quă 1.6. Nếu a và n là các số nguyên nguyên tố cùng nhau, n  0 thì đồng i j dư thức a �a  mod n  nghiệm đúng nếu và chỉ nếu i �j  mod ord n a  . Hệ quả 1.7. Giả sử ord m a  t và u là một số nguyên dương . t u Khi đó ord m  a    t  u . Định nghĩa 2.1 Nếu a và n là các số nguyên nguyên tố cùng nhau, n  0 đồng thời ord n a    n  thì a được gọi là căn nguyên thuỷ mod n. Định lí 2.2. Nếu a và n là các số nguyên nguyên tố cùng nhau, n  0 và a là căn nguyên thuỷ mod n. . Khi đó các số a1 , a 2 ,..., a  n  là hệ thặng dư thu gọn mod n. k * Chứng minh :+ Do  a, n   1 �  a , n   1 k �� Vậy mọi luỹ thừa trên đây nguyên tố cùng nhau . i j + Giả sử trong dãy có hai số đồng dư mod n. : a �a  mod n  từ hệ quả 1.6 ta có i �j  mod   n   , do a là căn nguyên thuỷ . Vì 1 �i �  n  ,1 �j �  n  � i  j Vậy trong dãy trên không có hai số nào đồng dư với nhau theo mod n . Định lí được chứng minh. Hệ quả 2.3 . Giả sử g là căn nguyên thuỷ mod m , trong đó m là số nguyên dương lớn hơn 1. Khi đó g u là căn nguyên thuỷ mod m khi và chỉ khi  u,   m    1 Định lí 2.4. Nếu số nguyên dương m có căn nguyên thuỷ , thì nó có cả thảy     m   căn nguyên thuỷ . PHẦN II. ỨNG DỤNG VÀO GIẢI TOÁN II .1. Ứng dụng trong giải các bài toán chứng minh chia hết. Bài toán 1.1: n n Cho hai số nguyên dương a, b nguyên tố cùng nhau . Đặt A  a 2  b 2 với n là số nguyên dương. Chứng minh rằng mọi ước lẻ của A có dạng 2n1 k  1 trong đó k là số nguyên dương. Giải: Ta chỉ cần chứng minh mọi ước lẻ nguyên tố của A là đủ.Gọi p là số nguyên tố lẻ n n n n  a���2 � b 2 0  mod p  a2 b 2  mod p   1 . bất kỳ p là ước của A� � 1,2,..., p  1 : bb� �1 mod p  .Từ Do  a, b   1 �  a, p   1,  b, p   1 từ đó b�   1 a 2  b 2  mod p    h. Gọi ord p  ab� n 1 n 1 2n 1  ab�  2n 1  bb�   mod p  2n 1  ab�  1 mod p  (2) 6 � h | 2n1 � h  2 ( � 0; n  1 ) . Từ (2) và theo định lý Fecmar ta có : � h | p 1 � n   2 2 2n �1 mod p  mà  bb� Nếu : 0 � �n �  ab�  � �ab�  � �1 mod p  từ đó �  � n  ab�  �  bb�   mod p  a 2 từ (1) và (3) �2a 2 0  mod p  2n 2n n b 2  mod p  (3) n n 2Mp (vô lí) n 1  Vậy   n  1 � 2n1 | p  1 � p  2 k  1  k �Z  (đpcm) Bài toán 1.1 có thể coi là một bài toán tổng quát cho một số bài toán có dạng trên . Bài toán 1.2: Cho n là số nguyên dương lẻ khác 1. 1. Chứng minh rằng nếu: n | 6n  7 n thì n M13 . 2. Chứng minh rằng tồn tại vô số số nguyên dương n sao cho n | 6n  7 n . Giải :1) Gọi p là ước nguyên tố nhỏ nhất của n � p lẻ,từ giả thiết ta có 6n  7n �0  mod n  � 6n  7n �0  mod p  (1) .Tacó  6, p    7, p   1 � tồn tại duy nhất x � 1,2,3,..., p  1 sao cho 7 x �1 mod p  (2) Kết hợp với (1) với (2) ta được x n  6n  7 n  �0  mod n  �  6 x  n   7 x  n �0  mod p  � 1   6 x  n �0  mod p  n �  6 x  �1 mod p  (3) ( do n lẻ ). Gọi ord p  6 x   h (4) vậy ta có : n �  6 x  �1 mod p  � p 1 � 6x�    �1 mod p  � � h 6 x  �1 mod p   � � � 6 x �1 mod p  mà � 13  0  mod p  p h |n 1 � � h | p 1 � h p 1 p suy ra h  1 do cách chọn p. 7 x �1 mod p�  ‫���ۺ‬6 x�7 x 0  mod p  13 . Vậy n M13 (đpcm). 13x 0  mod p  k  2) Tồn tại vô số số nguyên dương n có dạng n  3  k �Z  để n | 6n  7 n . ( ta chứng bằng quy nạp toán học theo n) Bài toán tổng quát : Cho n , a , b là các số nguyên dương thoả mãn  a, b   1 , a  b là số nguyên tố và a n  b n Mn . 1) Chứng minh rằng : n Ma  b . 2) Chứng minh rằng tồn tại vô số số nguyên dương n sao cho a n  b n Mn và n Ma  b . 7 ‫ۺۺۺۺۺۺۺۺۺۺۺۺۺۺ‬ Bài toán 1.3.( THTT 6/2006) Cho a, b là hai số nguyên dương thoả mãn các số 2a  1 , 2b  1 và a  b là các số nguyên tố. Chứng minh rằng các số a a  bb và a b  b a đều không chia hết cho ab. Giải : Vì các số 2a  1 , 2b  1 và a  b là các số nguyên tố � a  1 , b  1 � a  b là số nguyên tố lẻ . Không mất tổng quát giả sử a chẵn , b lẻ � a b  bb Ma  b . Giả sử trái lại a b  b a Ma  b ( với a  b trường hợp b  a lý luận tương tự ) a b  b a  a b  bb  bb  b a b  1 Ma  b � bb  b a b  1 Ma  b mà bb M  a  b � a  b | b � a  b �b (vô lý) từ đó suy ra ba b 1  mod a b   1 . Do a  b là các số nguyên tố nên theo  b a b  1 Ma b a b a b 1  1 �0  mod a  b  suy ra định lý Fecmar ta có b  b Ma  b � b  b b a b1 1�  0���  a b  mod  a b) (2) b a b1 1 mod a b  ( do b M 1 mod a b  . Từ (1) và (2) ta có : Gọi ord a bb  h  a h h|a b � � h | 2a  1 mà 2a  1 là số nguyên tố nên h  1 hoặc h  2a  1 � h | a  b 1 � a  1 �ab�1۳M 2a 1 a b 1 2a 1 b a (vô lý )  h 2� 1 �b1 mod a b  b 1Ma b (do b 1) � b  1 �a  b (vô lý )  h   a  b lập luận tương tự a a  bb M  a  b (đpcm) Vậy điều giả sử là sai � a b  b a M Bài toán 1.4. Cho p là số nguyên tố p �5. p 1. Chứng minh rằng tồn tại số nguyên tố q khác p sao cho q |  p  1  1 . 2. Giả sử  n p  1  1  �piai (trong đó pi là số nguyên tố, ai ��* ) .Chứng p i 1 p2 p a � . � i i 2 i 1 n minh rằng p Giải : 1. Ta có p p 1   p  1  1  p p �tồn tại số nguyên tố q khác p sao cho q |  p  1  1 bởi vì  p  1  1 là hợp số . p p n n i 1 i 1 2. Đặt A  �pi ai , B  �ai . 8 p 1  Nếu B � theo bất đẳng thức AM-GM ta có : 2 p 1 p2 p p 1 B B A �B  p  1  1  B p � A  p B �p 2  2 p 1  Nếu  B  p theo bất đẳng thức AM-GM ta có : 2 p 1 2 p �p  1 � p p 1 B B A �B  p  1  1  B p  Bp B  � p  � �2 � 2  Nếu B �p p p 2p do q |  p  1  1  q �p  �  p  1 �1 mod q  �  p  1 �1 mod q  h �p � h2 � � h| 2p � � Gọi ord q  p  1  h � � h  2p � � h | q  1 � Nếu h  2 �  p  1 �1 mod q  � p  p  2  �0  mod q  � p  2 �0  mod q  . Khi p đó 0 � p  1  1 �2  mod q  � q  2 (vô lý do q lẻ ). 2 2 p � 2p� | q 1 Nếu h  q 2p p pi p i 1, n p2 Từ đó ta có A �p  a1  a2  ...  an   Bp �p  (đpcm) 2 Bài toán với đánh giá tốt hơn như sau : 2 n p a 3. Cho p là số nguyên tố p �5. Giả sử  p  1  1  �pi i ( trong đó pi là số i 1 n nguyên tố, ai ��* ) .Chứng minh rằng �p a �p i 1 2 i i Bài toán 1.5. Chứng minh rằng tồn tại vô hạn cặp số nguyên tố  p, q  thoả mãn điều kiện sau � 2 p 1 �1 mod q  � đây : �q 1 2 �1 mod p  � k k  Giải: Bổ đề : Cho a, b �Z ,  a, b   1 , p là một ước nguyên tố lẻ của a 2  b 2 Khi  đó p �1 mod 2 Ta có p | a 2 k 1 k 1  .( đã chứng minh ở bài toán 1.1 ). Thật vậy: k 1  b 2 , p | a p 1  b p 1 . Gọi h là số nguyên dương nhỏ nhất sao cho a h �b h  mod p  � h   2k 1, p  1 � h  2 s  s �� . b 2 � ta có a 2  �  mod p  s s a2 s 1 b2 s 1  mod p  L Giả sử s �k a2 k b 2  mod p  k 9 Mặt khác a 2 �b2  mod p  nên ta có 2a 2 �0  mod p  mà k  p,2 1 k a2 k k p 1 mod 2k 1  (đpcm).  h  2k 1 0  mod p  (mâu thuẫn). Vậy Áp dụng bổ đề: Xét các số dạng Fn  22  1  n �� 1. Nếu Fn  p là số nguyên tố ,ta xét q là một ước nguyên tố của Fn1 khi đó n  2n p 1 2 2 ta có : 2  1  2  1  L  2 2n 1   1 22 2n  2 2 2n  n  1 nên trong phân tích trên có thừa số 2 n 1 q 1 mod 2n1  mặt khác theo bổ đề q | 2 �1 � đó 2q 1  1  22 n2 t  1 M22     1   1  1 .... 22  1 22  1 n 1 M 1 q q  vì 2 p 1 1 mod q  2n1 t 1  t �*  do  1  22  1 2 2  1 L  2 2  1 � 2q 1  1Mp. 14 2 43 n 2 n 1 n p Vậy cặp  p, q  thỏa mãn n 2. Nếu Fn là hợp số ta xét p �q là ước nguyên tố lẻ của Fn  22  1 cũng theo n 1 * bổ đề � p  x.2n1  1 và q  y.2  1  x, y ��  . Từ đó suy ra : n 1 n 1 n 2 p 1  1  2 x .2  1 M22  1 M22  1 Mq 2q 1  1  2 y .2  1 M22  1 M22  1 Mp vậy cặp  p, q  thoả mãn. 3.Cuối cùng ta xét trường hợp không thoả mãn (1) và (2) tức là n n Fn  22  1  p k  p ��, k ��*  � 22  p k  1   p  1  p k 1  p k  2  L  p  1 n 1 n 1 n 2 2 * từ đó suy ra p k 1  p k 2  L  p  1 M2 � k M2 � Fn  2  1  z  z ��  n u �z  1  2 � 2   z  1  z  1 � � � 2v  2u  2 � u  1, v  2 � mâu thuẫn v �z  1  2 Từ đó ta có Đpcm. 2n Bài toán 1.6. Chứng minh rằng với mọi m, n nguyên dương thì tồn tại x nguyên dương thoả � 2 x �1999  mod3m  � mãn : � x 2 �2009  mod5n  � � Giải : Bổ đề 2 là căn nguyên thuỷ của mod 5m , mod 3n. � 2 x1 �1999  mod3m  � 2 x1 �1 mod3  � � Từ đó tồn tại x1 , x2 : � x do � x2 vì x1 , x2 chẵn n 2 2 � 4 mod5 2 �2009  mod5    � � � 10 � x1 t� mod3m1   � � 2 Suy ra hệ phương trình đồng dư � có nghiệm. x n  1 2 � t� mod 4.5  � 2  � � 2t �x1 mod   3m   2.3m1 2 x �1999  mod3m  � � �� Chọn x  2t thì � đpcm x n 2 � 2009 mod5 2t �x2 mod   5n   4.5n1   � � � �     Bài toán 1.7. n Chứng minh rằng : n |   a  1 với mọi a, n γ �* , a 2. Giải : Với n  1 ta có điều phải chứng minh . n n Nếu n �2 , đặt m a 1 a 1 mod m  . Gọi h  ord m a . h n Nếu h  n ta có 1  a  a  1  m  do a , n �2  . Mà m | a h  1 � a h  m vô lí. n Vậy h  n . Ta lại có h |   m  ( hệ quả) � n |   a  1 điều phải chứng minh. Bài toán 1.8. (VMF-4/2010) n Chứng minh rằng giữa các số 10  3  n  1,2,3,.... có vô số hợp số � 100 �1 mod 7  , 101 �3  mod 7  , 102 �2  mod 7  , 103 �6  mod 7  , � Giải: Ta có � 4 10 �4  mod 7  , 105 �5  mod 7  , 106 �1 mod 7  , 107 �3  mod 7  ,.... � � 10 là căn nguyên thuỷ mod 7 � tồn tại k � 1,2,3,4,5,6 | 10k  3 �0  mod 7  . n 6t  k t Xét nt  6t  k  t �� � 10  3  10  3 �10  3 �0  mod 7  . Vậy dãy số :  10 nt  3 t��* gồm vô hạn hợp số. Bài toán 1.9. n n Cho a �Z Chứng minh rằng mọi ước nguyên tố của a 2.6  a 6  1 đều có dạng  6n1 k  1 trong đó k , n �Z . Giải : n n n n Gọi p là một ước nguyên tố bất kỳ của a 2.6  a 6  1 p� | a 2.6 a 6 1 p 3    n n 6 2.6 6 a 2.6  a 6  1 �0  mod p  � a  1 a  a  1 �0  mod p  ord p aΣ h | 6n1 Gọi h �� 1. Nếu t �n  a 3.6 n n n  mod p  . (2) h 3k 2t  k , t �, k , t 0  mod p  � vô lý � a 3�6  1 �0  mod p   a 6 n n n 1 1 n 1 ta có hai trường hợp sau 11 n1& k 2. Nếu t  � a 2.6 n 1 mod p  kết hợp với n giả thiết  a 6 2  mod p   a 3.6 9 �0  mod p  � p  3 vô lí n n 8  mod p  (3). Từ (2), (3) ta có p 1 Nếu t  n  1& k  n  1 � h  6n1 � 6n1 | p  1 do a �1 mod p  đpcm Bài toán 1.10. Cho p là số nguyên tố , p �3  mod8  hoặc p �5  mod8  , p  2q  1 trong đó q là p1 số nguyên tố .Chứng minh rằng : 2  4  8  L  2  1 với  là một nghiệm khác 1 của phương trình  p  1 . p 1 Giải: p ��3  mod8  � 2 không là số chính phương  mod p  2 2 1 mod p   2q 1 mod p  22 q 1 mod p  . Gọi h  ord p 2 � h | p  1  2q do q �� nên ta có hoặc h  1 hoặc h  2 hoặc h  2q .    Nếu h 1 21 1 mod p  1 0  mod p  vô lý 22 1 mod p  3 0  mod p  p 3 vô lý  Nếu h  2�  Nếu h  2q � h  p  1    p  � 2 là căn nguyên thuỷ mod p suy ra tập  2 , 2 , 2 ,..., 2  là hệ thặng dư thu gọn mod p điều này tương đương với:  2 , 2 , 2 ,..., 2  � 1,2,..., p  1 . Từ đó ta có     1         L         L      1 . 1 2 3 p1 1 2 3 p1 2 4 8 2 p 1 p 1 1 2 3 p 1  1 p  1 Bài toán 1.11. Cho p là số nguyên tố, q  2 p  1 cũng là số nguyên tố . Chứng minh rằng tồn tại một bội của q có tổng các chữ số không lớn hơn 3. Giải : p  2 � q  5 thì tồn tại số 10 thoả mãn yêu cầu bài toán q 5� q� ;10�  1 10q1 1 mod q   10 p 1  10 p 1 Mq  10 p  1 Mq ta có đpcm. � � 10 p  1 Mq r : 10r  1 Mq  � p ta cần chỉ ra tồn tại � điều này tương q 10  1 M r , k : 10r  10k  1 Mq � � r r k đương với r : 10 �1  mod q  hoặc r , k : 10 �10  1  mod q  . Ta chứng minh trong dãy số sau 100 , 101 ,102 , 103 ,....,10 p 2 , 10 p1. không có hai số nào có cùng số dư khi chia cho q .Giả sử tồn tại � 1 i��� j�p�1 :10i 10 j  mod q  10 j i 1 mod q  do p  ord q10 � j  i Mq vô lí 12 p 1 Xét hai tập hợp A   0,1,10,...,10  p 1 và tập B   1, 1  10,..., 1  10  Suy ra tồn tại a �A , b �B nào đó � q  mod mà a �b  mod q   mod q  có A  p  1 B  p 1 có � b �10r  1  mod q  �r 10 10k 1  mod q  � �r 10 �1  mod q  � điều phải chứng minh. Bài toán 1.12(Bungaria MO2006) Cho p là số nguyên tố với p 2 | 2 p 1  1 . Chứng minh rằng với mọi số nguyên n dương n thì số  p  1  p !  2  có ít nhất ba ước số nguyên tố phân biệt. n Giải. Ta có p  1 | p ! � gcd  p  1, p !  2  là luỹ thừa của 2 . Ta cần chứng minh mỗi số p  1 , p !  2n mỗi số có ít nhất một ước nguyên tố lẻ nữa là đủ. k k   Giả sử p  1  2 � p  2  1  k �Z  . Nếu s �3 là ước lẻ của k khi đó ta có p  2st  1   2t  1 2t  s 1  2t  s 1  L  2t  1 là hợp số vô lí, nên k  2t ta có   2t k 2 p 1  1  22  1  22  1  22 2t 1   1 22  2t 1   t  t 1   1 K 2 2  1 2 2  1 ( với t ��) . Từ giả thiết p 2 | 2 p 1  1 mà p 2 không là ước của tích vế phải biểu thức trên  i j  t 1 2 k 2 2 (do 2  1,2  1  1 i �j. và 22  1  22  1  p ) Vô lý Vậy p  1 không là luỹ thừa của 2 (1)  p !  2n  2k � k  n � p !  2k  2n  2n  2k n  1 vì p lẻ � p | 2 k  n  1 Đặt h  ord p 2 � h | k  n & h | p  1 giả sử p  1  ht khi đó :   2 p 1  1  2ht  1   2h  1 2h t 1  2h t 2  L  2h  1 Mp 2 từ 2h �1 mod p  suy ra 2h t 1  2h t 2   L  2h  1 �t �0  mod p  � 2h  1 Mp 2 do h | k  n � p 2 | 2 k n  1 � p 2 | p! vô lý. Vậy p !  2n không là luỹ thừa của 2.(2) n Từ (1) và (2) mọi số nguyên dương n thì số  p  1  p !  2  có ít nhất ba ước số nguyên tố phân biệt. II .2. Ứng dụng trong giải các bài toán tìm số nguyên thoả mãn một tính chất cho trước. Bài toán 2.1: 13 Tìm tất cả các cặp số nguyên tố  p, q  thoả mãn p p  q q  1 Mpq Giải : Từ giả thiết ta thấy p �q do vai trò p, q như nhau không mất tổng quát giả sử p  q . + Nếu p  2 từ giả thiết � q q  5 M2q � 5 Mq � q  5. + Nếu p  2 � p, q là các số nguyên tố lẻ q  p �2 p p 1 Mq (*) p 2 p 1 mod q  . p p  q q  1 Mpq  � Gọi h ord q p p h 1 mod q  , Theo định lý Fecmart thì p q 1 �1 mod q  ,từ đó ta h |2p � có � từ (*) h | q 1 � p 1 mod q  p 1 q vô lý - Nếu h �1 � p p 1 mod q  , mà  từ (*)  p p 1 mod q  , kết hợp lại ta Nếu h  p được 2 �0  mod q  � 2  q vô lí. 2� p2 1 mod q  p 1Mq p 1Mq vô lí - h � h  2 p � q  1 M2 p � q  1 Mp từ đó ta có ; 0 �1  p p  q q �1  p p  1 �2  mod p  � p  2 vô lý. Từ đó chỉ có cặp  p, q    2,5  thoả mãn .Vậy có 2 cặp số nguyên tố  p, q  thoả mãn p p  q q  1 Mpq là  p, q     2,5  ,  5,2   . - Bài toán 2.2: Tìm tất cả các cặp số nguyên tố  p, q  thoả mãn 7 p  7q Mpq Giải : + Nếu p  q � 2.7 p Mp 2 � p  7  q + Nếu p �q do vai trò p, q như nhau không mất tổng quát giả sử p  q . - Nếu q  7 �  p,7    q,7   1 . Từ đề bài 7 p  7 q Mpq ta suy ra � 7 p 1 �1  mod q  7 2 p 1 �1  mod q  � 7 p 1  1 Mq � � � � �q1 � �2 q 1 �q 1 7  1 Mp � 7 �1  modp  � 7   �1  modp  � Gọi h  ord q 7 , k  ord p 7 kết hợp với định lí Fécmart ta có h | 2  q  1 � k | 2  p  1 � � � * h | q 1 & � k | p  1 Đặt q  1  2 u , p  1  2 v ( u , v lẻ, , ��). � � � h | p 1 k | q 1 � � � h  21 u� u� | u �p  1M21u� �  �  1 � � � 1 � Khi đó � � vô lý � 1  �   1 � � � k  2 v v | v q  1 M 2 v   � � � - Nếu q �7 xét lần lượt với q � 2,3,5 14   q  2 � 7 p  49M2 p � p  7 3 p � p  5, p  7 ( loại )  q  3 � 7 p  343M �p  7 (tm) p 5p � �  q  5 � 7  16807M �p  1201 (loai ) �p  13 (tm) p 7 7p��  q 7�7 7 M �p  181(tm) Các cặp số nguyên tố  p, q  thoả mãn 7 p  7 q Mpq là ( 2,7),(7,2), (5,7), (7,5) , (13,7), (7,13),( 181,7),(7,181), (7,7). Bài toán 2.3. Tìm tất cả các số nguyên dương a sao cho với mỗi k nguyên dương ta có a k  1 M12321 . Giải : Ta có 12321  32.372 | a k  1 a 2 �0,1 mod3 , k lẻ thì a k �a  mod3 a 1�  mod3 a3 1 mod9  a k  � 1 mod37  a 2 k 1 mod37  . Gọi h  ord37 a theo định lý fécmar ta có � h | 2k � h | k � h  2t ( t ��* , t | k , t lẻ ) � � h |   37   36 �  � a t �1 mod37  a  9 37 t |9 a9 1 mod37  đặt a 9  1  b � 37 | b a  1 mod3   1   b  1  1 M37 2 . Do a 9 1�  mod 37  a  1 mod3 �   t | 18 37 a3 1 mod32  a 9�37 9 37 1 mod37  2 9 k Giả sử tồn tại k sao cho a  1M12321 thì a �1 mod37  , a �1 mod3  a 1,3,4, 7, 9, 10,11, 12,, 16  mod37  a 11,41,61,62,65,77,95,101,104,110  mod111 Bài toán 2.4 2n  1 Mp �� � Tìm số nguyên dương lẻ nhỏ nhất n sao cho : �n 2  1 Mp  2 �� � n 1 Giải : Từ giả thiết  2 2  mod p  p 2   do n lẻ � 2 là số chính phương mod p, p  2 � p 7  mod8  ; p 2 1  mod8  . Cặp nguyên tố nhỏ nhất thoả mãn là ( 71,73 ). ord 71 2  2h 1 mod 71 Gọi h ��� 2 hM h | 35 h 35 . Tương tự 15 l� � � ord  73 2 2l 1 mod 73 2 lM l | 72 h 9 , l  1,3 loại vậy l  9 từ đó ta 2n  1 M71 � n 9 35 315 tức là nmin  315 � n M9 � 35  � có �n 2  1 M 73 � Bài toán 2.5 ( USA TST 2003) �p | q r  1 � q q| r  1 Tìm tất cả các bộ ba số nguên tố  p, q, r  thoả mãn : � � r | pq  1 � Giải : ta thấy các số nguyên tố p, q, r phân biệt . Ta sẽ chứng minh trong 3 số p, q, r phải có một số bằng 2. r 2r 1 ( mod 2) . Gọi h  ord p q theo trên và Giả sử p, q, r  2 , ta có p | q 1 q h | r � h2 � � h | 2r � � theo định lỷ Fecmart ta có � h  2r � � h | p 1 �  h  2r � 2r | p  1 � p q  1 � 1  1 �0(mod r ) q 0(mod r ) 2 0  mod r  r 2 mà p  1� 2  h  2 � p | q  1. 2 r + Nếu p | q  1 � p | q  1 mà p | q  1 � p | 2 ( Loại) q 1 + Nếu p | q  1 mà q  1 chẵn, p lẻ � p | . Tương tự ta có 2 p 1 r 1 q 1 r 1 p 1 q| ; r| � pqr�   � p  q  r �3 (vô lý) 2 2 2 2 2 2 q Vậy phải có ít nhất một số bằng 2. Giả sử p  2 � q, r lẻ và q | r  1 , r | 2  1 2 Ta có t  ord r 2 � t | 2q & t | q � t | 2 � r | 2  1  3 � r  3 � q |10 � q  5 Vậy bộ  p, q, r  =   2,5,3 ;  3,2,5  ;  5,3,2   thoả mãn đề bài. q Bài toán 2.6 (Russia MO 2000) Có tồn tại hay không các số nguyên dương a, b, c ,  a, b    b, c    c, a   1 16 2a  1 Mb � �b 2  1 Mc � thoả mãn : �c 2  1 Ma � Giải . Bổ đề : Với mỗi số nguyên dương n . Gọi   n  là ước nguyên tố nhỏ nhất y  của n .Chứng minh rằng nếu p ��, y �Z thoả mãn 2  1 Mp , p    y  thì p  3 . h Thật vậygọi h ord p 2 2 1 mod p  theo định lý Fecmar ta có 2 p 1 1 mod � �p  h| p 1 h p 1 � h    y  và  h, y   1 mặt khác ta có : 22 y �1 mod p  � h | 2 y do h  1 ,  h, y   1 � h | 2 � h  2 � p  3 . Áp dụng : giả sử tồn tại các số nguyên dương a, b, c đôi một nguyên tố cùng nhau a b c thoả mãn điều kiện đề bài 2  1 Mb ,2  1 Mc ,2  1 Ma . � a, b, c đều lẻ theo đề bài �  a, b    b, c    c, a   1 �   a  ,   b  ,   c  . là 3 số nguyên phân biệt . Không mất tính tổng quát giả sử   b     a  ,   c     a  . Theo bổ đề trên  p, y      a  , c  nên ta có   a   3 đặt a  3a0 ta chứng minh rằng  a0 ,3  1 thật vậy giả sử a0 M3 thì theo đề bài ta có 2c  1 M 9 � 22 c  1 M 9 � 2c M 6    9  � cM3 �  a, c   3 ( vô lý ) vậy  a0 ,3  1 . Đặt q    a0bc  ta có q    q  �min    b  ,   c   Ta sẽ chứng minh b Mq .  Nếu a0 Mq theo bổ đề trên với  p, y    a, c  � q  3 � a0 M3 vô lý  Nếu cMq do  b, c   1 � q    c     b  do đó theo bổ đề trên với  p, y    q, b  � q  3 vô lý ord�  2 2k 1 mod p  k|q 1 k q 1  Vậy b Mq � 2a  1Mq gọi k  q 2a nên   a0   q  h &  a0 , h   1 do 2  1Mq � h | 2a � 6a0 Mh . Vì  a0 , h   1 Mh ���26  1 mod q  q 7 . Mặt khác 2a  1   23   1 �2  mod 7  Nên 6 � Vô lý , vậy điều giả sử là sai từ đó ta có điều phải chứng minh a0 Bài toán 2.7 ( IMO 1990) 2 n Tìm tất cả các số nguyên dương n thoả mãn điều kiện n | 2  1 . Giải : 1) n  1 thoả mãn điều kiện bài toán 2) Nếu n  1 trước tiên ta chứng minh n M3 Gọi p là ước nguyên tố nhỏ nhất của n , ta có p lẻ do n lẻ. 2n  � 1 �� 0  mod  n2  2 n 1 0  mod p  2 2 n 1 mod p  17 h | 2n � � gọi h ord p 2 2h 1 mod p  vậy ta có � h | n � h p 1 � h | p 1 � 2 � 2 1 mod p  p 3 vậy n M3 .   m,2    m,3  1 k 3 ) Đặt n  3 m k 2 k 1 2k dưvới 1  mod3  k 32 k 1 3� m M2.32 k 1 23 m k 3k M 32 k 1 2 k 1 23 k 1 mod32 k  là phần tử duy nhất trong Z/  3  đồng 2k 2 m� 3 ta có 3 m | 2  nhưng 2 là căn nguyên thuỷ mod32 k � 23  mod3  2k  p�h2 hM 1 k 2m�3 2k 23 2 k 1  3k m  1 mod32 k  từ đó suy ra 2k 1 � k �1 � k  1   m,2    m,3  1 ta đi tìm m giả sử m  1 . Gọi q là ước n 1 mod q  2 2 n 1 mod q  mà nguyên tố nhỏ nhất của m � q  3 . Ta có 2  � q 1 1 mod q  2 2 n ,q 1 1 mod q  do q | m � q | n từ đó ta theo định lý Fecmar 2 � 4) Vậy n  3m có �  q  1, n   1 � q  1,2n   2 �� � �q  1, n   3 � q  1,2n   6 q  3  voly  � 22 �1 mod q  � � �6 �� � m 1� n  3 7 2 � 1 mod q q  7 loai do  2 �  1 mod 7       � � Vậy n  3 và n  1 thoả mãn điều kiện bài toán. Bài toán 2.8 (Bulgaria 1995) p p q q Tìm tất cả các cặp số nguyên tố  p, q  sao cho pq là ước của  5  2   5  2  . p p q q Giải . Ta có  5  2   5  2  M2 và M5 (giả sử tồn tại p, q )  p, q 2,5 . Không mất tính tổng quát ,giả sử p �q p p  Nếu p | 5 p  2 p từ định lý Fecmar ta có 5  3 �5  2  3  mod p  � p  3 q  3  3q |  5q  2 q  .117  q |  5q  2 q  .3.13  q  13 q | 5q  2q  q  3 Vậy có các cặp  p, q    3,3 ,  p, q    3,13 thoả mãn  p | 5q  2 q q q + q | 5  2   p, q    3,3 p p + q | 5  2 do  2, p   1,  2, q   1  a, b   1,2,..., p  1 q q sao cho 2a �5  mod p  và 2b �5  mod q  . Từ giả thiết p | 5  2 18  5q 2q  mod p   5.a  q  2.a  q q 5q  mod p   a 1 mod p  tương tự ta h|q � p cũng có  b 1 mod p  . Đặt h  ord p a � � h | p 1 � q ��  h 1 a 1 mod p  2a 2 5  mod p  � p  3 tương do p �1q,� tự ta có q  3 . Vậy có các cặp  p, q    3,3 ,  p, q    3,13 ,  p, q    13,3 thoả mãn Bài toán 2.9 (Bulgaria 1995) 3 pq Tìm tất cả các cặp số nguyên tố  p, q  sao cho a �a  mod3 pq  với mọi số nguyên dương a Giải. Giả sử chọn đươc bộ  p, q  thoả mãn yêu cầu bài toán . Gọi a là một căn 3 pq 1 �1 mod3 pq  � a 3 pq 1 �1 mod p  nguyên thuỷ của p � ord p a  p  1 , ta có a 3 pq  1Mp  1 � � 3 pq  1Mp  1 � 3q  p  1  3q  1Mp  1 � 3q  1Mp  1 .Vậy � 3 pq  1Mq  1 � 3q  1 � 1,2,3,4 giả sử p �q � 3q  1 �p  1 & 3q  1 �3 p  1 � p 1 1. 3q  1  p  1 � p  3q �� loại 2 p 1 2 p 1 do 3 p  1Mq  1 � 3 p  1M 1� 2. 3q  1  2  p  1 � q  3 3 9 p  3M2 p  4 � 9 p  3Mp  2 � 15Mp  2 � p  2 � 1,3,5,15 � p � 3,5,7,17 �  p, q     5,3 ,  17,11  . 3. 3q  1  3  p  1 vô lý 1 4  p 1 � 3p 1 4. 3q ���� p 3 p  2,3  p, q    3,3  Vậy  p, q  γ   3,3 ,  17,11 ,  5,3    p q  Cho a  3 dễ dàng loại được  p, q    5,3 và  p, q    3,3 Với  p, q    17,11 � 3 pq  561 là số Carmichael nên ta có điều phải chứng minh 3 pq Vậy các cặp số nguyên tố  p, q  sao cho a �a  mod3 pq  với mọi số nguyên dương a là  17,11 &  11,17  Bài toán 2.10 (Turkey TST 2013) n m Tìm tất cả các cặp số nguyên dương  m, n  sao cho 2   n    n   1 !  n  1     Giải.Gọi n  p1 p2 ... pk với p1  p2  ...  pk là các ước nguyên tố của n ,  i �Z . 1 2 k 19 p1 p2 ... pk   p1  1  p2  1 ... pk  1 n  1   1. p1 p2 ... pk p1 Nếu k  1 và 1  2 thì n    n   1  p1 . Ta xét phương trình đã cho theo mod p1 n p 1 Ta có p1 | 2  1, p1 | 2  1 ( theo định lý Fecmar) � ord p 2 |  p1  1, n  nên tồn tai số nguyên tố q |  p1  1, n  � q  p1 vô lý. 2 Cho nên ta chỉ có hoặc n  p �� hoặc n  p  n  p � 2 p  p m � p  2, m  2, n  2  n  p 2 � 2 p   p  1 !  p 2 m  1 (*) Nếu p lẻ, xét theo mod 4 ta được Ta thấy rằng n    n   1  n. 1 1 2 VP(*) đồng dư với 2 mod 4 suy ra  p  1 ! �2  mod 4  � p  4 � p  3 ta thấy không thoả mãn (*) sử dụng mod8 , còn p  2 ta có một nghiệm duy nhất  n, m    2,4  n m Vậy các cặp số nguyên dương  m, n  sao cho 2   n    n   1 !  n  1 là  m, n  �  2,2  ,  4,2   Bài toán 2.11 Tìm tất cả các số nguyên tố p để phương trình sau có nghiệm nguyên dương. x p 1  x p 2  x p 3  L  x  2  y 3 (1) Giải : Phương trình (1) � x p 1  x p 2  x p3  L  x  1  y 3  1 � x p  1   x  1  y 3  1 (2) �y  1  1 �y  2 3 2 �� + Nếu x  1 từ (1) � p  y  1   y  1  y  y  1 � � 2 �y  y  1  p �p  7 3 x p 1 Mq x p 1  mod q  . +Nếu x  1 gọi q là số nguyên tố q | y  1 từ (2)���� h q 1 Gọi h  ord q x  x 1 mod q  , mặt khác theo định lý Fecmar x �1 mod q  . h| p h 1 � � �� Vậy ta có � h | q 1 � h p �  Nếu h  1 x 1 mod q  từ (1) � x p 1  x p 2  x p 3  L  x  1  y 3  1 p 1 p2 3 nên ta có x  x  L  x  1 �p  mod q  , y  1 �0  mod q  � p  q 3  * Do đó y  1  p   ��  + Nếu y  2 � p  7,   1 � x  1 (loại) Mp y 1 mod p  y2 +Nếu y �2�y1� y 1 3  mod p  �y  1  3m  m, n �� Mặt khác p | y  y  1 � p  3 từ đây ta có � 2 n �y  y  1  3 � n  1, y  1 (loại ) 2 20