Lý thuyết Số học phổ thông: Phần 2

Chia sẻ: Lê Na | Ngày: | Loại File: PDF | Số trang:134

Thêm vào BST

Báo xấu

113
lượt xem 29
download

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

Phần 2 Tài liệu Số học phổ thông trình bày các nội dung: Lý thuyết đồng dư, phương trình đồng dư. Cuối Tài liệu có các lời giải của các bài tập. Tham khảo nội dung Tài liệu để nắm bắt nội dung chi tiết.

Chủ đề:

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

Lưu

Nội dung Text: Lý thuyết Số học phổ thông: Phần 2

BÀI THỨ SẢI LÝ T H U Y Ế T ĐỒNG Dư 5 1. ĐỒNG D ư T H Ứ C Trong b à i này chúng ta sẽ n g h i ê n cứu quan hệ giữa cắc số n g u y ê n vê p h ư ơ n g d i ệ n số d ư trong p h é p chia ữkc số n g u y ê n cho m ệ t số l ự n h i ê n . ì - ĐỊNH NGHĨA ĐỒNG DƯ THỨC 1. Đ ị n h nghĩa. Cho m là một số tự n h i ê n k h á c k h ô n g ' Ta nói hai sỗ n g u y ê n a và b là riềng dư với nhau Ihco mèriun m nếu trang p h é p chia a và b cho in ta đ ư ợ c c ù n g m ệ t số d ư . Khi a và b đồng d ư v ớ i nhau theo m ô đ u n m ta v i ế t a as b (međm) (1) H ệ thức (1) gọi là một đềiiỊỊ dư thức. Ví dụ 9 B i 3 (iĩiodỏ); 8 Jấ 4 ( m o d t ì ) ; 8=£ 3 (rnodô). 2. Các đ i ề u k i ệ n t ư ơ n g đ ư ơ n g v ơ i đ ị n h nghía. Đ ị n h l ý . Các mệnh đe sau dày là lương dương: («) a sm b (modm); (b) m ị a — b; (é) có sỗ nguyên l sao cho a = b + mi. Chứng minh. Ta sẽ chứng m i n h (a) »*(b) .=4 (c) - K a ) . (a) *. (b). Theo (lịnh nghĩa của a se b (modrii), ta có a = mq, + r, b = m q + r. q,, q , r 2 z, 0 < r < m . T ấ 2 d ó ta đ ư ợ c a - b = m(qi — q ) l ứ c là m í a - b. 2 (b) (c). Giả sử ra I a - b, k h i ấ y ắt có t ^ z sao "tho a — b = m i , nghĩa là a = b + mt, t ^ z. 137
(c) (n). Già sử có srt níỊKvên ! sao cho 0 = lì 4- nít. Gọi r là sô'(.lư d o n g phốp chia a cho m, nghía là a = mq, + r, qi, r £ z, 0 < r < m Khi %y ta có b + mỉ = mqj + r hay là b = m(q, - t) + r, trong đ ó CỊI — t là một số n « u v è n và 0 < r < m. cho nôn sỗ d ư trong j>!ú'j> chia b cho m c ù n g là r, nói k h á c đi a 9 b (modni). Định lý đ ư ợ c chửng minh. Định lý này cho p h é p la l ẫ v mệnh đ ề (b) hoặc mệnh đô (c) trong định lý í hay cho định nghĩa k h i ĩ n i ệ m đ ò n g dư. T i ong thực íể n g ư ờ i ta hay dùnịỉ các mệnh de (b) hoặc (c) h ơ n , bởi vi các m ệ n h đẽ n à v đ ư a khái n i ệ m đ ò n g (lư vẻ các khái n i ệ m đã quen biẳl là chia hết và bằng nhau có (hề d i ẳ n tả b ở i các đẳng thức. Chúng ta chú ý rằng, ( r ư ờ n g họp đặc biệt a >rm 0 (modm) có nghĩa là a cilia hổi cho m. li - CÁC T Í N H C H Ấ T CỦA Đ Ồ N G DƯ T H Ứ C 1. Quan hệ đồng dư là một quan hệ lương diiơíiỊỊ trên tập hợp số nguyên, nghĩa là nó có các tính c h ã i đ ơ n giản sau đ â y : ú) VỚI mọi số nguyên a la có a a s a (mocìm) ; b) nêu (ì =2 b (modm) thì b =i a (modm); C) nêu a 3» b (modm) và b s= c (modm) IM a am c (mo dm ). > Chứng minh. a) V ớ i số n g u y ê n a t ù y Ỷ la 0 a - ả = 0 i m nên « » e (ui o ă m ị 138
b) T ử a S E 1) (niodm) la c ó m I a — à , k h i ẫ y cũng c ó i i i I b — a cho n ê n b a > a (modm). c) T ừ a a b (modm) v à b S i c ( m o è U ì ) ta c ó m I a —h v à m I b - c, k h i ấ y in I (a — b) + (b - c) hay ni I a - c , ...giũa là n — c (modm). d 2. a ) Ta có thề cộng hoặc. trừ từng ík một của nhiều Hồng dư [hức theo cùng mội môditn. C ụ t h ê là n ê u c ó 5— bị (raodra), i = Ì, 2 k thì ta c ư n g c ó a a a i ~b. 2 r t ••• + v — ki + •• -±- bk í m o d r a l b ) Ta có Hử nhăn lừng vẽ lìĩộ' với nhau nhiêu dòng tíu thức theo càng một Ììĩỏđun. C ụ t h ề là n ế u c ó a i : bị ( m o d m ) , i = Ì, 2,..., k thì ta c ũ n g c ó a]a ... a = b]b ... 2 k 2 b (modra). k Chứng minh. T ừ ai = b i ( m o d m ) , i = Ì, 2,..., k suy r a ắt c ó ti £ z, i = Ì, 2,..., k sao cho ai = b i + mtj, i = Ì, 2,..., k. (2) C.ộníỊ (hoặc ( r ù ) iừng v ẽ m ộ t c á c đ ẳ n g thức (2) la sò được a a i + 2 + ...+ a k = b i + b + . . . 4 - b - f m (ti ± 2 k l ±...±\). 2 Đẳng Ihửe n à y c h ứ n g tỏ a a a i zt 2 dt— = b i í — bi + b. -4-... ± 2 b k (modm). T a l ố i n h â n từng v ẽ m ộ t c á c đ ẳ n g t h ứ c (2) ta s è đ " , ợ c một (ÌẲĩìíị [hức m à ở v ế phải, n g o à i s ố hống là tích bib ... bk c ò n c á c s ố hống k h á c đ ề u c ó ít nhai m ộ i thừa 2 số in n ê n la c ó aia ... a 2 k = bibo... bit + mt. t ^ z. Dẳng thức n à v chứng l ủ g a líu... a k b,b ... b 2 k (modrn). 3. Các hệ quả của lính chãi 2. a) Tu có the thèm Dào hay bởi đi cùng ir.ộl sò vào hai DĨ của mội đong dư thức, nghĩa lù n ê u iu c ó 138
a m b (modm) t h i ta c ũ n g có a + c Sãb + c(modm) v ớ i c l à m ộ t số n g u y ê n í à y ý . Chứng minh. Thật v ậ y , theo g i ả I h i ế t a s b (mod'VI) v à theo t í n h c h ã i Ì c S i c ( m o ù m ) nên á p (íụný lịnh c h ấ t 2 ta đ ư ợ c a 4- c S 3 b ± c ( m o đ i ì ì ) . b) Ta cỏ Hử chuyền oe các sô lựuĩịỊ cùa một đnnq dư thức như lì) phai dồi đáu lúa xô hạìig ,7
a b (modin) (hi (a c ũ I ì £ có a" X 3 b" (modm) v ó i ì) là m ộ t số n g u y ê n cltrong. ClìứìHỊ minh. Áp đ ụ n g linh chất 2 bằng cách nhân đong dư t h ứ c a sm b ( n i O i i m ) v ó i chính nó t i m " vế mội n l ă n , c h ú n g ta đ ư ợ c k ế t qua cần chứng minh. n g) Clin sử f (.r) = o x + On-iX"- n+ . . . + (tiX + a 1 0 lù mội da ỉ hữ': với. hộ sô nguyên. Xài la có a sa p (nicù in). Un lu cũng có ĩ ( « ) 3= í'(jl) (modni) Dộc biệì nêu ta có i'0) ^ 0 (modm) ỉ hỉ ta cũng có f ( a + k m ) =3 0 ( n i d d m ) với i:-ọi k £E z. Chứng minh. T h e o g i ả íliĩếí -j. Ị5 ( m ó c ! ' l i ) ó i ; đ ó a j i x ' s s a i ^ (inodm) vói ì = Ì, 2, n. T ử (ló ta được a„a" + a _,a -' n n + . . . + a , a + Í1„ - o p" n + .In-Ip"" 1 + - + + aiP + a c (i)HKlni), nghĩa l à ỉ (7.) == f(|3) ( m o d n ì ) . Đặc b i ệ t v ì a = a + k i n (mo;! ì ), k z, n ê n f ( « ) S3 £••• f(st + k m ) ( m o d n i ) . N i l ù lì í-; ^ 0 (liiocl.w) n ê n l a l uiìg có f(
a = b (modm). Chứnq minh. Theo giả thiết ne s be ( m o d m ) vậy m I ác ~ be hay m I c ( a - b ) . N h ư n g (c,in) = Ì n ê n la phải v có D í i a - b , níỊliĩa íà a 3 = b (inodni). - 5. a) Tá\'ỏ liu- nhân lìdi lữ vù môrìun cùn mội đung dư l/ìửc vùi CÙIĨ(J mội sỗ nguyên dương. C ụ thề là n ế u ta c ó a =3 b (modm) thi cùng cỏ á c =3 be (modme) v ớ i c là một s ố n g u y ê n dương. b) Ta có the chia hai uế vù mòdun của mội clone] du thức cho một ước cliunq dựơny cửa chúng. C ụ t h ê là n ê u ta c ó a — b (modm) v à 6 > 0, ỏ I (a, b, m) thì la cũng c ó ố & V 6 / Chứng minh. a) T h e o giả thiết a se b (modm) v ậ y c ó s ỗ n g u y ê n t sao cho ii = h + mi. N h à n hai vổ c ủ a dẳng thức n à y v ớ i c ta đ ư ợ c á c — b c + m c l , nghĩa là á c a be (mod me). b ) T ừ g i ả t h i ế t f t I (a. b , m ) t a đ ặ t a = ốa„ b = ốbi, m = ốm, v ớ i ai, bi, m, ^ z . N h ư n g a = b + mt n ê n ốai = Abi + ốii)it- C h i a c ả hai v ế cho ố ta đ ư ợ c ai = bi + ni! t, nghĩa l à ai mmfc)!(modnii) hay là -— SÌH-^- /mod — ì . ố é V ố / 6. Nếu tim sỗ a và b dền ọ dư vời nhau [heo nhiêu mòduiì l/ỉi chúng cũnq dồn) dư nới nhau Iht.ù môứun là BCNN cửu vác mỏưun dỏ. C ụ t h ề là n ê u ía có a B b ( m o đ i n , ) , 1=1, 2, .... k thì la cũng c ó a « b (modm), trong đ ó m = lmi. m , 2 m j. k 142
€hứiựị minh. Thật vậy theo giả thiêu a - b là b ộ i chung của mi, m , 2 n i n ê n a —b cũng là bội của m = k íiĩìị, m , 2 m ] nghĩa là a sai b (modm). k 7 . Nêu a và b đông dư VỚI nhau theo mỡđun m ílìì chúng cũ/? 7 dòng dư với nhau theo mỏđun lừ ước của ni. Cụ thề là nếu a —i b (rnodm) và 6 I m, 6 > 0, thì la cũng có a a== b (modố). Chứng minh. Theo giả t h i ẽ l ra I a - b mà ố I in nén ố I a — b nghĩa là a ™ b (mod ố). 8. NỖI! a và b dồng dư ười nhau theo môdun m Hù lợp hụp các ước chunq của a và ni liiui j DƠI lặp hụp các ước chung của b và in. Đặc biệt la cỏ (u, m) — (b, ni). T h ậ t v ậ v , bởi v i a s b (modm) n ê n ắt có t < z sao cho a = b + m t . Đẳng thức này chửng lò rằng lập hợp các nức chung của a và ni t r ù n g vói tận hợp các ước chung của b và m, và do đó ta có (a, m) = (b, m). § 2. CÁC L Ớ P THẶNG DƯ ì-HỆ THẶNG DƯ ĐẦY ĐỦ 1. Định nghĩa. Cho UI là một số l ị nhiên lớn hơn Ì, khi ấy lập hợp H-— Ị(), Ì, m - Ì ị gom các sỗ Thuyên đôi một k h ô n g đon." d ư với nhau theo nióđun m và m ọ i số n g u y ê n đ ề u đồng ức, vái m ọ i số nào đó của H. Thật vạy v ớ i a, b ^ i ỉ , a ^ ỉ) iu có 0 < I a —b I < in n ê n a b (modm). Giả su X là một sỗ nguyên tùy V , í hễ thì ắt cỗ cập số n ^ u v ê n 'q, r sao cho X —qni + r, 0 < r < m. Cúc hệ (hức này chứng l ò X 3= r (modỉn), r £ l i . Hộ các sò n g u y ê n H = ị ( ) , Ì,..., in — Ì ị (lược g ọ i là hệ liíậny dư dày đủ moduli m klíòny ùm nhỏ nhái. 143
Tồng q u á t ta có định nghĩa: một tập hợp H những sò nguyên dược gọi là mội hệ thặng dư đay đủ llìeo môdun m ( v i ế t tắt là h ệ T D Đ Đ modm) n ế u v à chì n ế u : — các số ngu vén trong H đ ô i m ộ t k h ô na' đồng d ư v ớ i nhau theo raỏđun m ; — m ọ i số nguyên đ ề u (long dư theo moduli m vơi m ộ t sè nào d ó (rong H . M ỗ i một sẽ nguyên của l i được gọi là m ộ t //ỉặ/ỉ
n à o đ ó t r o n g H , Lừ đó suy r& rẫĩỉg trong hệ Ịo, Ì, 2,..., m — Ì j có hai số n à o đó đỏng d ư v ớ i nhau theo niôđun in cũng là điều k h ô n g I h ễ đ ư ọ c . Vậy Heo đ ú n g ni (hăng dư. b) Mọt hệ qồm m số nguyên đôi một không dồng dư với nhau theo môdun in dầu họp thành mội hệ thặng dư đầy đủ môdun m.; Chứng minh. Giả sử H = | a , ai, a _ i I là h ệ gồm 0 m m sẽ n g u y ê n d ô i một k h ô n g đ ò n ? d ư v ớ i phau theo m ô ẩ u n i n . Ta p h ả i chứng m i n h rỊng m ỗ i s ố n g u v ê n X đ ề u đ ồ n g d ư v ớ i m ộ t số n à o đ ó thuộc H . BỊng c á c h chia a„, a a _ i cho ni ta đ ư ợ c b m »1 = meỊi + T i , q l'j £ z, 0 < Ti < m, i = 0 , Ì, h m—1. Dỗ thấy rằng lập hợp Ị Ti I i = 0 , Ì, m — Ì ị l à lập hợp (0, Ì, ni - l ị . Thật vậy với 0 < i, j < < in — Ì thì 1-ị =f= Tị, bởi vì n ế u Tị = Tị thì ta có ai s = a j (modm), i ~fc j , h ói v ớ i giả t h i ế t là các phần tử của H đ ô i một k h ô n g d ỏ n g d ư v ớ i nhau theo m ô đ u r i m. (Hả sử X là m ộ t sẽ n g u y ê n t ù y ý, chia X cho m ta dược X = mq + r, q. r í= z, 0 < r < m. T ừ đ ó r phai là một số Tị n à o đ ó v é i i = 0, Ì, m— Ì v à s a r (inodm). B ở i v ậ y X Sĩ Tị ( m » đ m ) và vì ai = Tị (modm) n ê n " X s a i ' f m e d i u ) v ớ i i nà© đ ó ( 0 < Ị i " ^ m — 1). c) Cho a lù mội nõ mpiyèn nguyên, lô với in oà b là e mội sế nguyên lùi} ý. Khi ấy nếu X chạy qua một hệ lliknẹ dư ắtìỵ dã niòilun in Ihi ax + b cũng chạy qua mội hệ !liặii tiu diìt 4ủ mêầun m. Chứiìíi minỉì (jìiả sử X c h ạ y qua m ệ t h ệ thặng d ư đ ẵ v đủ m o đ u n i n Ị X i , X o , Xi,, ị la phải chứng minh ị a x i + b, ax 2 + fe, .... aXjfc 4- b ị cũng l à m ộ t h ệ thặng d ư đ â y đ ủ môdiin i n . Theo lính chát b) ở t r ê n ta chỉ cần chứng 10-SllPii 145
minh rằng v ớ i i =5*= j (Ì < ; i , j < in) có a \ j + b ỉ £ a x j + b (modm). T h ậ t v ậ y nếu nhu' a.Vj + b = a.\j + b (niodm), thì ax, == a \ j (niodm) t ừ đó do (a, m) = Ì ta có Xi = Xj ( n i o d m ) , i =f= j . Điều này là k h ô n g t h ề đ ư ợ c vì X i và X j là hai thặng d ư k h á c nhau của m ộ t hệ T D Đ Đ modm. li - CÁC L Ớ P T H Ặ N G DƯ ỉ. G i ả sử l i = ị a , ai, .... a,„_i Ị là một hệ T D Đ Đ 0 modiu. Ta xét b ộ p h ậ n ã " i ( i = 0, Ì, m — 1) của l ậ p hợp số n g u y ê n z xác định n h ư sau: ãT = Ị X ệ z I X s ai (mo dm) ị, ( i = 0, Ì, m - 1). Ta gỌiT„, ~ã"u . . . . " ă n , , ! x á c đ ị n h như thế là những lớp thặng dư theo môđun m. 2. Giả sử H = Ị a , 0 au .... a » _ i j là một hệ TD ĐĐ mocìm. Khi ồụ ta cổ:. m-1 _ a) y Ri = z; b) ái n 57 = ệ, i 4* j (0 < i , j < m - 1). Chứng minh : m-l_ m-1 _ a) Rõ r à n g y a, c z. Ngược l ạ i ta c ó z c u a it i=xO i=0 thật vậy giả s ử X € z, k h i ấ y ắ t c ó Rị (0 < i < m - 1) đ ễ X 33 ai (modm), nói khác đi X ^ã~|. m-1 _ & Đ i ề u n à y k é o theo X € u i' í=»0 146
_ b ) Ta chứng minh với ì =f* j (0 < i , j < m - 1) thi ai n aj = ệ. Thật vậy nếu ai n »j =f= ệ thì ắt có X ^ ai và x £ a j , từ đó suy ra x = 3 j (modm) và X a aj (modm), và từ đó ta có a i HE âị (modm). Điều này là không thê được vì a i ^ a j là hai thặng dư khác nhau của một hệ TDĐĐ modm. 3. Tập hợp các lớp thặng dư dầy đủ môdun m, ký hiệu bởi z , có in phần lử. Gọi các phần tử của z là m m A , Ai, ... Am.] ỉa sẽ cỏ ô Zm = ị A A i , A _ ! j = |ã7, ái, .... ã » _ i ị = ị 0, Ì, m .... m - TỊ. Ta có thề định nghĩa một hệ TDĐĐ modm là một tập hợp gởm các số nguyên lẫy ở mỗi lớp thặng dư môđun m một và chỉ một số. 4. Tái cả cúc tíìặng dư của cùng một lớp thặng dư cộ cùng các ước chung với môđun, nói rung có cùng ước chung lớn nhái với môđun. Thật vậy, điêu này suy ra trực tiếp từ tính chất 8, l i , § í . ' . Ước chung lớn nhất của các thặng d ư của cùng một lớp thặng dư với môđun được gọi là ước chung lớn nhát cùa lớp dó với rnôđnn, hay trong những lúc không sợ lầm lẫn ta gọi là ước chung lớn nhất của lớp dó. Cụ thê là nếu d = (a, ni) với a ^ A thì la đ ạ i (A, m) = d. Nếu irức chung lớn nhất của một lớp với môđun mà bằng ỉ Ihì ta nói lớp đó nguyên tố với môdun,ị bay không sợ lầm lẩn gọi tắt là lớp nguyên tồ. I U - H Ệ T H Ặ N G DƯ T H U GỌN 1. Các lốp t h ặ n g dư thu gọn. Cho Zm là lập h ợ p các lớp thặng du môđun m. Bộ phận Z* gởm các lớp của 147
z , n g u y ê n tố v ớ i m ô đ u n , đ ư ợ c gọi là lập hụp m cức lớp thặng dư thu gọn môđun m. Z* = ị A
T í n h chất cùn h ệ ( h ạ n g d ư thu g ọ n . (ì) MỖI hệ thặng (lư thu gọn môdun in đ è n qồm (f(m) í hạng dư. . Thật vậy, diều n à y suy ra từ hệ quả ở t r ê n là tập hợp Z* có đ ú n g (f(m) phần l ử . b) Mọi hệ gồm y(m) sỗ nguyên nguyên lõ với m và dài một không dòng dư VỚI nhau theo môdun m lập nén mội hệ llìận§ dư thu gạn mồdun m. Chửng minh. G i ả s ử K = Ị gi, ga,..., g f ( m ) Ị, (gi, m)==l, g. 4= gj (modal), i =h j , Ì < í. j < (m). K>ề chứng m i n h K là một bệ TDTG modm ta còn phải chứng minh m ồ i số n g u y ê n n g u y ê n l ố v ớ i m đ ề u đỏng d ư v ớ i m ộ t số n à o đó thuộc K. c m a Bẹng cách chia gi, g2 g(p(m) h ° ^ được gi = mqi + Ti, qi, 1-j £ z, 0 < 1-ị < m , ( i = Ì, 2,..., cp(in)). Dễ í h ẫ v r ẹ n g t ậ p hẹp ị Ti j i = l , 2,...,
r r 2 r S l S l s ' - cp( ) = m -
HI - CÁC Ví D Ụ ÁP D Ụ M Định l ý ơ l e và đ ị n l i l ý P h é c m a có n h i ề u ứ n g đụng. ở đây ta n ê u lên một v à i v í d ụ v è v i ệ c lìm số d ư trong p h é p chia một l ũ y thừa cho m ộ t sẽ đ ã cho. 100 Vi dạ Ì: T ì m số d ư trang p h é p chia 3 cho 13, Theo định l ý P h é c m a (lo 13 k h ô n g chia h ế t 3 v à cp(l3)= 12 17 ta có 3 ái 5 (mod 13) Hơn nữa 100 = 12.8 + 4 cho n ê n 3100 = (312)« 34 _ 34 ( m o dl3). N h ư n g 3* = 81 ai 3 (mod 13) nôn ta có 1 0 0 3 =2 3 (medl3), nghĩa l à d ư trang p h é p chia 3 100 cho 13 là 3. 3J5 Ví dụ 2. T ì m số d ư trong p h é p chia 109 cho 14 345 Bởi vì 109 a a - 3 ( m o d l ề ) n ê n 109 = ( 5 3ý" (modl4) Theo đ ị n h l ý ơ l e t ừ ( - 3 , 1 4 ) =• Ì ta có (-3)*( ) H B Ì (moẩlế) n h ư n g
Mặt khác 151 ^ l i (mod 20) 1 V n nên 2 _ 2 (mod 25) và do 2" = 2048 = - 2 (mod25) ta có 2"' ^ - 2 (meẩ 25). T ừ đồng dư thức sau cùng ở trên sau khi nhân hai vẽ và môđun của đồng dir thức với 4 ta được 153 2 ^ _ 8(m«ẩl00), hay là , S 3 2 — 92 (mod 100), 153 nói khác đi, số dư trong phép chia 2 cho 100 là 92. 153 Ta cũng có thề nói rằng khi viết s© 2 trang hệ thập phân thì hai chữ số tận cùng bên phải là 92. BÀI T Ậ P %l. Chứng minh rằng a) 100a+10b + c s à o (mod21) k h i v à c h ì k h i a - 2 b + ' t c 3« 0 (mod21); n + 4 b) 3" 3= - Ì ( m e d i o ) k h i v à c h ỉ k h i 3 3» —Ì ( m o d 10) 6.2. T ì m sỗ d ư t r o n g c á c p h é p c h i a 5 56 28 a) 8 ! e h i a c h o l l ; b) 1532 — Ì c h i a cho 9 ; c) ( 1 2 3 7 1 + 3 4 ) chia c h o 111. 6.3. Chứng minh rằng a) 220 i 102; ỉ n + I n + 2 b) 6 +5 : 31 ( n = 9, Ì , 2,...). 0.4. H ã y n g h i ê n c ứ u d ẫ u h i ệ u chia h ẽ t cho 2; 3; 4; 5; 6; 7; 8; 9; li của c á o sỗ t ự n h i ê n v i ế t t r o n g h ệ g h i sỗ t h ậ p p h ầ n . (ì.5. Chứng m i n h rằng v ớ i ni, n là hai số t ự nhiên l ẻ , ta c ó n J«1 + 2« + ... - I - m S B 0 (modm). tì.6, Cho p là m ộ t số t ự n h i ê n l ớ n h ơ n 1. C h ứ n g m i n h r à n g c á c m ệ n h đ ề sau l à t ư ơ n g đ ư ơ n g : Ỉ53
a) p là số n g u y ê n trt ĩ k t>) C p — 0 (modp), v ớ i m ọ i k = Ì , 2, . . . . p - 1 ; . k ị . c) C p _ J ss ( - 1 ) ( m o d p ) v ớ i m ọ i k = 0, Ì , . ., p — 1. 6.7. Cho m và n l à hai sỗ t ự n h i ê n k h á c . k h ô n g . Chửng minh m n + 1 r ằ n g n ế u a 3= b ( m o d m ) t h i a n m as b (modm >. 6.8; Chứng m i n h rằBg n 1 a) 2 = — Ì ( m o d 3 + ) . n = Ì , 2. . . . Ị b) Có n h i ê u vỏ hạn s ố tự n h i ê n a thỏa mẫn a I 2" + 1. 6.9. C h ứ n g m i n h r ằ n g a ) V ớ i m là m ộ t sỗ l ự n h i ê n l ẻ ] > Ì c h o t r ư ớ c ta c ó 1 r + 1 (m - Ì)" " = - l(modm ), ri = Ì, 2, . . . ; b) Có n h i ề u v ô h ạ n s ô t ự n h i ê n a thỏa m ã n a I 2 2 a + ì. 6.10. Cho m i , ni2 Hik l à n h ữ n g s ỗ t ự n h i ê n l ớ n h ơ n Ì đ ô i một nguyên tố cùng nhau, b là một số nguyên tùy ý. m Đặt m = mini2... mít và a i = — , i = Ì , 2, k. mi V a) Chứng minh rang k h i XI, X ỉ , . . . , Xk l ầ n l ư ợ t chạy qua các hệ thặng dir đ à y đ ủ m ô đ u n mi, môđun mj, niòđun mk t h i a i x i + H X Ì + . . . + akXk + b c h ạ y qua hệ thặng dư đây đủ m ô đ u n m. b) C h ứ n g m i n h r ằ n g k h i X I , X ỉ , . . . . . Xk l à n l ư ợ t c h ạ y qua c á c hỉ t h ặ n g ' d ư thu g ọ n m ô đ u n mi. môđun mi,..,, n i ô í l u n mii thi a i x i + a^xỉ + ... + akXk c h ạ y q u a hệ t h ặ n g d ư t h u g ọ n mòđuH m. 6.11. C h ứ n g m i n h r ằ n g m ỗ i l ớ p t h ặ n g d ư m ố d u n ni g ồ m vả c h ỉ gồm k l ớ p thặng d ư m ô đ u n k i n . 6.12. C h ử n g m i n h r ằ n g n ê u (&, m ) — ì v à a, p là h a i số t ự f n h i ê n sao cho a — p ( m o d ( m ) ) l h i ta c ó a* — a ( m o d n i ) . 6.13. T i m SŨ d ư t r o n g c á c p h é p c h i a 50 2 < 0 7 0 r>0 ' a ) o ' c h i a cho l i ; b ) 3 c h i a cho 8 3 ; o) 5 + 7 chia 75 1 0 0 l ồ 0 c h o 12; d ) 3.J3 + 4 . 7 chia cho 1 3 2 ; e) 3 5 chia c h o 425; ì , lo ' "* "' 10 10 10 g) lo + lo +...+ lo c h i a cho 7. 1 5 4 *
s ) T ỉ m l a i (Ì ũ sỗ tận c ù n g bên phẳi của c á c số sau đ ầ y viết Irciig Ì ê ghi cơ s ổ thập p h à m b) C h ứ n g minh ràng hai c h ữ số tận cfing bên phải (viồt 9 •• ong h ệ ghi lírong cơ số thập p h â n ) c ủ a 8* và 9* là như nhau. 16.15. Chứng minh rống 7 0 7 0 1 5 S 0 + 1 a) 2 + 3 • 13; b) 2 0 -1 ỉ l l . 3 1 . f l l l e) 2 +3 ỉ li 2 n + nJ tn=0, Ì, 2,...); d) 2 +3 : 19 (li = 0 , Ì, 3,...); e) a - , —Ì í n (v*i n ià số l ự n h i ê n l è ) . 6.16. C h ứ n g minh rẻng 4 I, a) Vóri ( a , 240) = Ì ta c ó a - Ì : 240; 8 b) V ớ i (a, 5) = Ì la c ổ a i t ^ ^ - 4 a • 100; p P c) V ó i số nguyên lỗ p>7 ta c ó : ) - 2 - Ì : 42p. n . 6.17 «t) T i m lát eả cảo số tự nhiên n sao cho n I 2 - l . P b) T i m tiít cả c á c s ô n g u y ê n tố p sao cho p [ 2 +1. 6. IS. Cho m và n là hai sổ tự nhiên lớn hơn Ì nguyên* tố cùng nhau. Chứng min li rẻng m T(n) + n ẹ(m)_ J ( m o d m n ) t 6.19. Clio p là một l ố n g u y ê n tố l ẻ . C h ứ n g minh rồng v ớ i hai s ỗ tự nhiên ni, n k h á c 0, ta c ó a m(p-l) + a n ( p - l ) ^ ( m o d p ) k h i và chi khi a = 0 6.20. Chửng minh rẻng nêu ai+a +— 2 +a n — 0 (mod30), thỉ r ) 5 5 a ị + a., + . . . + = 0 (mod30). 6.21. Chứng minh rẻng 3 0 3 0 30 a) Ì + 2 +... + 10 = - 1 (roodll); b) V ớ i p là một sỗ* n g u y ê n tố lẻ ta c ó : r l m +2 m + ... + ( p - l ) m i - Ì (modp) nêu m 53= 0 (mod (p-0); m m jm + 2 + .,.-f (p-i) == 0 (modp) nếu m ^ 0 (mod(p-D). 0.22. C h ó p là một s ỗ n g u y ê n ^ lẻ., C h ứ n g minh rẻng p _ I p 2 2 ix) a + a - + . . . + a + ! ỉ £ 0 (modp ) : r p r+< b) a S 3 Ì ( m o d p ) k h i và. chỉ khi a m Ì (moỢp ). 155
6.23. Chứng minh ràng a) Với các số l ự nhiốn a lớn hon b và li l ở n hon ì thì mòi n 1 4 ước nguyên tò cùa a - h" hoặc lù. ước của a - b v ớ i s là ước thực sự cùa n. hoặc có dạng n k + 1 . p b) V ớ i số nguyên tố Ị ) > 2 thì ưởc nguyên tố rủi! a - l hoặc là ước cù;ĩ a - l (n *h !) hoặc cổ dạng 2pk+ ì. Dặc hiệt, ta có P ước nguyên tó của sô Mp = 2 - Ì (p là sỗ nguyên tổ lê) có dạng 2pk + l . 6.24. Chửng mÌHli rằng: a) Véi các sè l ự nhiên a, b và n > Ì t h i m ỗ i ước nguyên n n s tố cùa a + b heặc là ước của a" + b với s là irớc thực sụ của n, heặc là cé dạng 2nk + l . p b) V ố i sè nguyên té p > 2 tki ước nguyên tó cùa u + l hoặc là ước của a-H h»ậc cé d ạ i i g 2 p k + l . 6.25. Chứng minh rằng: a) Nếu a và I) lộ hai tự n h i ê n khác 0. nguyên tố cùng 2 2 nhau thi mối ư è c nguyên tố l i của a + b phải cố dạng 4m + ì. b) Nếu a và b là hai số tự nhiên khác e, nguyên tố cứng 2 2 nhau thi m5i ước nguyên t ố lè cùa a + b phải cỏ dạng 2*+' m + 1. 6.26. Chứng minh rằng a) Cố nhiêu vô hạn sỗ nguyên tố dan,: 2pk+l (p là một sỗ nguyên tổ l ẻ cko t r ơ ố c ) . b) Có nhiều vô hạn số nguyên tố dạng 2 s + , k + l (s là một sỏ t ự nhiên cho t r ư ớ c ) . h 6.27. Cho p là một sỗ nguyên t6 và h i , h 2 a là những số tự nhiên khác 0- a) Chứag minh rằng ta c ỏ : p ( h i + h a + . . . + ha) - (h\ +hị + ... + bị) (modp). b) Tộ két quả câu á) suy' ra định lý Phèo ma. c) Từ định lý P h é c m a ỏ cảu b) tuy ra định lý ơ l e . 156