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

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.
Nội dung trích xuất từ tài liệu:
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ữacắ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 Ihcomèriun m nếu trang p h é p chia a và b cho in ta đ ư ợ cc ù 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 ấ 2d ó 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 thoa — 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 + rhay là b = m(q, - t) + r,trong đ ó CỊI — t là một số n « u v è n và 0 < r < m. chonô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 gdư. 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 —hv à 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ềuHồ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òngtí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 2b (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òđượca a i + 2 + ...+ a k = b i + b + . . . 4 - b - f m (ti ± 2 k l ±...±). ...