Luận văn Thạc sĩ toán học: Phương trình đồng dư

Chia sẻ: Tran Van Lam | Ngày: | Loại File: PDF | Số trang:55

Thêm vào BST

Báo xấu

283
lượt xem 81
download

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

Trong số học, thường ta phải xác định tất cả các số với tính chất p cho trước. Có thể có những số thỏa mãn tính chất p, nhưng có nhiều khi không có. Trong số học, thường ta phải xác định tất cả các số với tính chất p cho trước. Có thể có những số thỏa mãn tính chất p, nhưng có nhiều khi không có.

Chủ đề:

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

Lưu

Nội dung Text: Luận văn Thạc sĩ toán học: Phương trình đồng dư

Đ I H C THÁI NGUYÊN TRƯ NG Đ I H C KHOA H C Đ NG TH HUY N TRANG PHƯƠNG TRÌNH Đ NG DƯ LU N VĂN TH C SĨ TOÁN H C Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Đ I H C THÁI NGUYÊN TRƯ NG Đ I H C KHOA H C Đ NG TH HUY N TRANG PHƯƠNG TRÌNH Đ NG DƯ Chuyên ngành: PHƯƠNG PHÁP TOÁN SƠ C P Mã s : 60.46.40 LU N VĂN TH C SĨ TOÁN H C NGƯ I HƯ NG D N KHOA H C PGS.TS ĐÀM VĂN NH Thái Nguyên - Năm 2012 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i M cl c M cl c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . i L I NÓI Đ U 1 N i dung 4 1 Lý thuy t đ ng dư 4 1.1 Phép chia trong vành Z . . . . . . . . . . . . . . . . . . . . 4 1.2 Quan h đ ng dư và tính ch t . . . . . . . . . . . . . . . . 8 1.3 Vành Zm các l p th ng dư môđun m . . . . . . . . . . . . . 11 1.4 Đ nh lý Euler và Đ nh lý Fermat . . . . . . . . . . . . . . . 14 1.5 M t vài ví d t ng h p . . . . . . . . . . . . . . . . . . . . 15 2 Phương trình đ ng dư 20 2.1 Phương trình đ ng dư m t n . . . . . . . . . . . . . . . . 20 2.2 Phương trình đ ng dư b c nh t . . . . . . . . . . . . . . . 22 2.3 H phương trình đ ng dư m t n . . . . . . . . . . . . . . . 24 2.4 Phương trình đ ng dư m t n b c cao . . . . . . . . . . . . 26 2.5 Phương trình đ ng dư b c cao theo môdun p . . . . . . . . 31 2.6 Th ng dư b c hai . . . . . . . . . . . . . . . . . . . . . . . 33 3 Phương trình Mordell 38 √ 3.1 Chu n trong vành Z[ d] và s h c . . . . . . . . . . . . . . 38 3.2 Phương trình Mordell . . . . . . . . . . . . . . . . . . . . . 43 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
i K t lu n 49 Tài li u tham kh o 51 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
1 L I NÓI Đ U Trong s h c, thư ng ta ph i xác đ nh t t c các s v i tính ch t p cho trư c. Có th có nh ng s th a mãn tính ch t p, nhưng có nhi u khi không có. N u ta xét t t c các s thu c t p Z thì đây là m t công vi c không th th c hi n đư c. Nhưng n u ta xét trên m t t p h u h n nào đ y thì vi c ki m tra có th th c hi n đư c. Lý thuy t đ ng dư chính là vi c chuy n nh ng bài toán xét trên t p vô h n Z v m t t p h u h n nh ng l p đ ng dư theo m t môđun m nào đ y. Ch ng h n: Xác đ nh x, y nguyên th a mãn: x2 + 1 = 3y . Gi s phương trình có nghi m nguyên. L y mođun 3 ta có x2 + 1 ≡ 0(mod 3). Bi u di n x = 3k ho c x = 3k ± 1. khi đó x2 + 1 = 3h + 1 ho c 3h + 2. V y x2 + 1 ≡ 0 (mod 3): Mâu thu n. Tóm l i phương trình vô nghi m. Xác đ nh x, y nguyên th a mãn: x2 + 2 = 5y . Gi s phương trình có nghi m nguyên. L y mođun 5 ta có x2 + 2 ≡ 0(mod 5). Bi u di n x = 5k ho c x = 5k ± 1ho c x = 5k ± 2. Khi đó x2 + 2 = 5h + 2 ho c 5h + 3 ho c 5h + 6 . V y x2 + 2 ≡ 0 (mod 5): Mâu thu n. Tóm l i phương trình vô nghi m. Qua ví d trên thay cho vi c x, y thu c t p Z vô h n thì ta ch vi c ki m tra x nh n 0, 1, 2, 3, 4. N i dung lu n văn đư c chia thành ba chương: Chương 1 “ Lý thuy t đ ng dư” bao g m 5 m c. M c 1.1 đư c dành trình bày v Phép chia trong vành Z, k t qu chính trình bày l i thu t toán Euclid d tìm ƯCLN và đ nh lý cơ b n c a s h c. M c 1.2 đư c dành trình bày v Quan h đ ng dư và tính ch t k t qu chính đã ch ra Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
2 đư c nh ng tính ch t cơ b n c a quan h đ ng dư. M c 1.3 Vành Zm các l p th ng dư môđun m ch ng minh đư c Z là vành giao hoán, ch ng minh đư c Z∗ là nhóm nhân. M c 1.4 Đ nh lý Euler và Đ nh lý Fermat . M c m 1.5 M t s ví d t ng h p. Chương 2 “Phương trình đ ng dư” bao g m 6 m c. M c 2.1 Phương trình đ ng dư m t n. M c 2.2 Phương trình d ng dư b c nh t. M c 2.3 H phương trình đ ng dư m t n. M c 2.4 Phương trình đ ng dư m t n b c cao. M c 2.5 Phương trình đ ng dư m t n b c cao theo môđun p. M c 2.6 Phương trình đ ng dư b c hai. K t qu chính c a chương là trình bày chi ti t vi c gi i m t s d ng phương trình đ ng dư và trình bày l i ch ng minh đ nh lý Wilson. Chương 3 “ Phương trình Mordell” bao g m 5 m c. M c 3.1 Chu n √ trong vành Z[ d] và s h c. M c 3.2 Khái ni m phương trình Mordell. M c 3.3 M t vài phương trình có nghi m. M c 3.4 M t vài phương trình vô nghi m. M c 3.5 ng d ng c a th ng dư b c 3. K t qu chính c a chương là trình bày đư c phương trình Mordell. Đã ch ra m t s d ng phương trình có nghi m ho c vô nghi m. Trình bày đư c th ng dư b c ba. Do th i gian và ki n th c còn h n ch nên trong quá trình vi t lu n văn cũng như trong x lý văn b n ch c ch n không tránh kh i nh ng sai sót nh t đ nh. Tác gi lu n văn r t mong nh n đư c s góp ý c a các th y cô và các b n đ ng nghi p đ lu n văn đư c hoàn thi n hơn. Nhân d p này, tác gi xin bày t lòng bi t ơn sâu s c đ n th y hư ng d n PGS.TS Đàm Văn Nh đã t n tình giúp đ trong su t quá trình làm lu n văn. Tác gi xin trân tr ng c m ơn các th y, cô giáo Trư ng Đ i h c Khoa h c- Đ i h c Thái Nguyên đã gi ng d y và t o m i đi u ki n thu n l i trong quá trình tác gi h c t p và nghiên c u. Tác gi cũng xin chân thành c m ơn t p th b n bè đ ng nghi p và gia đình đã quan tâm giúp đ , đ ng viên tác gi hoàn thành t t lu n văn này. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
3 Thái Nguyên, tháng 07 năm 2012. Tác gi lu n văn Đ ng Th Huy n Trang Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
4 Chương 1 Lý thuy t đ ng dư Phương pháp đ ng dư do Gauss đ xu t là m t phương pháp h u ích trong vi c gi i quy t nhi u v n đ có liên quan đ n tính chia h t c a các s nguyên. 1.1 Phép chia trong vành Z Đ nh lý 1.1.1. V i m i c p s nguyên a và b = 0, luôn t n t i duy nh t m t c p s nguyên q, r v i 0 ≤ r < |b| đ a = qb + r. Ch ng minh: S t n t i: Đ t T = {n |b| sao cho n |b| ≤ a, n ∈ Z,}. Vì |b| ≥ 1 nên − |a| |b| ≤ − |a| ≤ a Do đó − |a| |b| ∈ T. V y T = 0. Vì T là t p b ch n triên T có m t s l n nh t m |b| . T m |b| ≤ a ta suy ra r = a − m |b| ≥ 0. Ta l i có (m + 1) |b| = m |b| + |b| > m |b| . Do m |b| l n nh t trong T nên (m + 1) |b| . Như v y |b| > a − m |b| = r và ta có a = qb + r v i 0 ≤ r < |b| . Bây gi ta ch ng minh tính duy nh t. Gi s có hai bi u di n a = qb + r v i 0 ≤ r < |b| và a = q1 b + r1 v i 0 ≤ r1 < |b| . Tr t ng v , ta có r − r1 = b(q1 − q). T |r − r1 | < |b| ta Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
5 suy ra |q1 − q| |b| < |b| . V y q = q1 và do đó r = r1 . Gi s a = qb + r, 0 ≤ r < |b| . Khi đó n u r = 0 thì q đư c g i là thư n c a phép chia a cho b.., n u r ≤ 0 thì q g i là thương h t, còn g i r là s dư c a phép chia a cho b. Đ nh lý 1.1.2. [Đ nh lý cơ b n c a s h c] M i s t nhiên l n hơn 1 đ u phân tích đư c thành m t tích h u h n th a s nguyên t , và phân tích này là duy nh t n u không k đ n th t các th a s . Ch ng minh: Xét t p F g m t t c các s nguyên l n hơn 1 không bi u di n thành tích m t s h u h n các th s nguyên t . Ta ch c n ch ra F = φ. Th t v , gi s F = φ. Khi đó có hai sô nguyên dương q1 , q2 > 0 đ m = q1 q2 . Vì q1 , q2 < m nên q1 , q2 ∈ F. Như v y ta có phân tích / q1 = t1 , t2 , ..., th và q2 = u1 , u2 , ..., uk , đó các ti , uj đ u là các s nguyên t . Khi đó m = q1 q2 = t1 t2 ...th u1 u2 ...uk . Đi u này mâu thu n v i gi thi t m ∈ F. Như v y F là t p r ng. Do đó m i s t nhiên l n hơn 1 đ u phân tích đư c thành tích c a h u h n th a s nguyên t t. Bây gi gi s m t s đư c phân tích thành hai tích d ng A và B các th a s nguyên t . Khi đó A = B. B ng cách lư c b các t t c các th a s nguyên t xu t hi n trong c A và B, ta nh n đư c đ ng th c tương đương C = D. Ta c n ph i ch ng minh C = D = 1. Th t v y gi s trái l i C = D ≤ 1. G i p là th a s nguyên t xu t hi n trong C. Khi đó p không th là th a s xu t hi n trong bi u th c tích c a D. Có nghĩa là D không là b i c a p, và do đó C cũng không là b i c a p (mâu thu n!). V y C = D = 1. Đi u này ch ng t r ng s phân tích ra các th a s nguyên t c a m t s nguyên >1 là duy nh t n u không k đ n th t các th a s . Khi phân tích các s t nhiên q > 1 thành tích các th a s nguyên t , có th m t s nguyên t xu t hi n nhi u l n. N u các s nguyên t p1 , ...., ps Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
6 xu t hi n theo th t α1 , ..., αs l n, ta vi t q = pα1 pα2 ...pαs và ta g i tích 1 2 s này là d ng phân tích tiêu chu n hay d ng phân tích chính t c c a q. Khi hai s nguyên dương a, b d ng phân tích tiêu chu n, có th a s nguyên t pc a a nhưng không là c a b, thì ta có th b sung vào phân tích c a b th a s p0 (và ngư c l i). Khi đó ta luôn vi t đư c a = pu1 pu2 ...pus 1 2 s và b = pv1 pv2 ...pvs , 1 2 s trong đó có th có nh ng s mũ 0. Như v y v i hai s nguyên dương a, b luôn t n t i các s nguyên t p1 , p2 , ...., ps đ a = pu1 pu2 ...pus 1 2 s và b = pv1 pv2 ...pvs , 1 2 s v i các s mũ nguyên không âm. Khi đó d th y r ng: min(u1 ,v1 ) min(u2 ,v2 ) (a, b) = p1 p2 ...ps s ,vs ) min(u max(u1 ,v1 ) max(u2 ,v2 ) max(us ,vs ) [a, b] = p1 p2 ...ps . Thu t toán Euclid: Gi s a và b là hai s nguyên dương v i a ≥ b và đ t r0 = a, r1 = b. B ng cách áp d ng liên ti p thu t toán chia, ta đư c: r0 = r1 q0 + r2 , r1 = r2 q2 + r3 , ..., rn−2 = rn−1 qn−1 + r2 , rn−1 = rn qn V i r1 > r2 > ... > r0 > 0. Cu i cùng, s 0 s xu t hi n trong dãy phép chia liên ti p, vì dãy các s dư b = r1 > r2 > ... ≥ 0 không ch a quá b s Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
7 dư c. T đây suy ra (a, b) = (r0 , r1 ) = (r1 , r2 ) = ... = (rn −2, rn −1) = (rn −1, rn ) = (rn , 0) = rn . Do đó ư c chung l n nh t c a a và b là s dư khác 0 cu i cùng trong dãy phép chia. T thu t toán Euclid cùng v i các tính ch t nêu trên, ta d dàng tìm đư c ư c chung l n nh t c a hai s nguyên, và do đó nhi u s nguyên. √ √ √ √ Ví d 1.1.3. Đ t (1 + 4 3 2 − 4 3 4)n = an + bn 3 2 + cn 3 4 cho m i n nguyên kgoong âm và an , bn , cn nguyên. Ch ng minh an chia cho 8 dư 1, còn bn , cn cũng chia h t cho 4. √ √ √ √ √ Bài gi i: Ta có an+1 + bn+1 3 2 + cn+1 3 4 = (an + bn 3 2 + cn 3 4)(1 + 4 3 2 − √ 4 3 4). V y   an+1 = an − 8bn + 8cn an+1 ≡ an (mod 8) bn+1 = 4an + bn − 8cn ⇒ bn+1 ≡ bn (mod 4) cn+1 = −4an + 4bn + cn . cn+1 ≡ cn (mod 4).   T a1 = 1, b1 = 4, c1 = −4 ta suy ra đi u c n ch ng minh. Ví d 1.1.4. Cho 2012 hình ch nh t v i đ dài các c nh là nh ng s nguyên a, b th a mãn 100 a b 1. Hình ch nh t v i đ dài các c nh (a, b) đư c g i là ch a đư c hình ch nh t v i đ dài các c nh (c, d) n u c a, d b. Ch ng minh r ng khi đó có ít nh t 41 hình ch nh t l n lư t ch a đư c nhau. Bài gi i: Ta chia 2012 hình ch nh t này ra làm 50 l p  {(100, b1 ) | 100  b1 1} ∪ {(a1 , 1) | 100 a1 1} {(99, b2 ) | 99   b2 2} ∪ {(a2 , 2) | 99 a2 2}  {(98, b3 ) | 98 b3 3} ∪ {(a3 , 3) | 98 a3 3}  ...  {(52, b49 ) | 52   b49 49} ∪ {(a49 , 49) | 52 a49 49}  {(51, b50 ) | 51 b50 50} ∪ {(50, 50)}.  Hình ch nh t (a, b) thu c m t trong 50 l p trên và các hình ch nh t Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
8 thu c cùng m t l p thì ch a nha. Do s hình ch nh t là 2012 phân vào 50 l p, nên ph i có ít nh t m t l p ch a nhi u hơn 40 hình ch nh t. 1.2 Quan h đ ng dư và tính ch t Đ nh nghĩa 1.2.1. Cho s nguyên dương m.Hai s nguyên a và b đư c g i là đ ng dư theo môđun m n u hi u a − b chia h t cho m. N u a đ ng dư vơi b theo môđun m thì ta vi t a ≡ b( mod m) và g i đó là m t đ ng dư th c. M t s tính ch t sau đây c a đ ng dư th c là hi n nhiên. M nh đ 1.2.2. Cho s nguyên dương m. Ta có: (i) a ≡ b( mod m) khi và ch khi a = b + mt, t ∈ Z, hay a − b chia h t cho m. (ii) Quan h đ ng dư theo môđun m là m t quan h tương đương trong t p Z. Do quan h đ ng dư là m t quan h tương đương nên các ph n t thu c t p Z s đư c phân ra thành các l p tương đương.Ký hi u t p thương Z/ ≡ b i Zm Đ nh nghĩa 1.2.3. Các l p tương đương theo quan h đ ng dư theo môđun m đư c g i là các l p th ng dư theo môđun m. M nh đ 1.2.4. S các l p th ng dư theo môđun m đúng b ng m. Đ nh nghĩa 1.2.5. N u t m i l p th ng dư theo môđun m ta l y ra m t đ i di n, thì t p các đ i di n đó đư c g i là m t h th ng dư đ y đ theo môđun m. N u t m i l p th ng dư đ y đ theo môđun m ta l y ra m t đ i di n không âm bé nh t, thì t p h p các đ i di n đó đư c g i là m t h th ng dư đ y đ không âm bé nh t theo môđun m. H th ng dư đ y đ không âm bé nh t theo môđun m là 0, 1,..., m − 1 , Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
9 còn h th ng dư đ y đ v i giá tr tuy t đ i nh nh t theo môđun m là {− m − 1 , − m − 1 + 1, . . . , m − 1 }   khi m l   2 2 2 m m m  {− , − + 1, . . . , − 1} ho c   m 2 2 2 {− + 1, − + 2, . . . , m } m  khi m ch n.  2 2 2 Đ nh lý 1.2.6. Cho a, b là nh ng s nguyên tùy ý. N u (a, m) = 1 và x ch y kh p m t h th ng dư đ y đ theo môđun m thì ax + b cũng ch y kh p m t h th ng dư đ y đ theo môđun m. Ch ng minh: N u x1 , x2 nguyên và ax1 + b ≡ ax2 + b (mod m) thì a(x1 − x2 ) ≡ 0 (mod m). Do (a, m) = 1 nên x1 ≡ x2 (mod m). Đi u này ch ng t khi x ch y qua các l p tương đương khác nhau ax + b cũng ch y qua các l p tương khác nhau. V y, n u (a, m) = 1 và x ch y kh p m t h th ng dư theo môđun m thì ax + b cũng ch y kh p m t h th ng dư theo môđun m. Tính ch t c a đ ng dư th c M t s tính ch t sau đây c a đ ng dư th c là hi n nhiên. n n (i) N u ai ≡ bi (mod m), i = 1, . . . , n, thì ai ≡ bi (mod m). i=1 i=1 (ii)N u a ≡ b + c (mod m) thì a − c ≡ b (mod m). (iii) N ua ≡ b (mod m) thì a + hm ≡ b (mod m). n n (iv) N u ai ≡ bi (mod m), i = 1, . . . , n, thì ai ≡ bi (mod m). i=1 i=1 (v) N u a ≡ b (mod m) thì ah ≡ bh (mod m). (vi) N u ai ≡ bi (mod m), i = 1, . . . , n, và x ≡ y (mod m) thì ta luôn có n n ai x i ≡ bi y i (mod m). i=1 i=1 a b (vii) N u a ≡ b (modm) , d ∈ uc (a, b) , (m, d) = 1 thì ≡ (modm) . d d (viii) N u a ≡ b (mod m) thì ah ≡ bh(modmh). a b m (ix) N u a ≡ b (modm) , d ∈ uc (a, b, m) thì ≡ mod . d d d (x) N u a ≡ b (mod m) thì (a, m) = (b, m). Tính ch t (x), ta th y các s c a cùng m t l p th ng dư theo môđun m Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
10 có cùng ư c chung l n nh t v i (m). Do đó ta đ nh nghĩa: (a, m) := (b, m), ∀ b ∈ a. Khi (a, m) = 1 thì l p a đư c g i là l p nguyên t v i môđun m. Đ nh nghĩa 1.2.7. N u t m i l p th ng dư nguyên t v i môđun m ta l y ra m t đ i di n, thì t p h p các l p đ i di n đó đư c g i là m t h th ng dư thu g n theo môđun m. Thông thư ng ta ch n h th ng dư thu g n theo môđun m t h th ng dư đ y đ không âm bé nh t {0, 1, . . . , m − 1}. Ký hi u ϕ(m) là s các s a ∈ {0, 1, . . . , m − 1} và (a, m) = 1. Khi đó s các ph n t c a m t h thu g n theo môđun m là ϕ(m). Ví d 1.2.8. H th ng dư thu g n theo môđun 14 là {1, 3, 5, 9, 11, 13} và ϕ(14) = 6. H th ng dư thu g n theo môđun 18 là {1, 5, 7, 11, 13, 17}, ϕ(18) = 6. Đ nh lý 1.2.9. N u (a, m) = 1 và x ch y kh p m t h th ng dư thu g n theo môđun m thì ax cũng ch y kh p m t h th ng dư thu g n theo môđun m. Ch ng minh: N u x1 , x2 nguyên và ax1 ≡ ax2 (mod m) thì a(x1 −x2 ) ≡ 0 (mod m). Do (a, m) = 1 nên x1 ≡ x2 (mod m). Đi u này ch ng t khi x ch y qua các l p tương đương khác nhau thì ax cũng ch y qua các l p tương đương khác nhau. V y ϕ(m) giá tr c a x cho ϕ(m) giá tr c a ax và các giá tr này không đ ng dư theo môđun m. Vì (a, m) = 1 và (x, m) = 1 nên (ax, m) = 1. Đi u này ch ng t ϕ(m) giá tr c a ax l p thành m t h th ng dư thu g n theo môđun m. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
11 1.3 Vành Zm các l p th ng dư môđun m Xét t p thương Zm = {a | a ∈ Z} các l p th ng dư môdun m. Đ bi n t p này thành m t vành ta đ nh nghĩa hai phép toán c ng và nhân sau đây: a + b = a + b, a.b = ab, ∀a, b ∈ Z. M nh đ 1.3.1. Xét t p thương Zm các l p th ng dư môđun m. Khi đó (i) V i phép c ng Zm tr thành m t nhóm giao hoán. (ii) V i phép nhân Zm tr thành m t v nhóm giao hoán. (iii) V i phép c ng và nhân, Zm là m t vành giao hoán có đơn v 1. Đ nh nghĩa 1.3.2. Zm đư c g i là vành các l p th ng dư theo môđun m.L p a ∈ Zm đư c g i là l p kh ngh ch n u có b ∈ Zm đ a.b = 1. Đ nh lý 1.3.3. L p a ∈ Zm là kh ngh ch n u và ch n u (a, m) = 1. Ch ng minh: Gi thi t l p a ∈ Zm là kh ngh ch. Khi đó có b ∈ Zm đ a.b = 1 hay ab = 1. Như v y ab ≡ 1 (mod m), t c là có x ∈ Z đ ab + mx = 1. Ta có (a, m) = (a, m) = 1. Ngư c l i, gi s a, m) = (a, m) = 1. Ta có b, x ∈ Z đ ab + mx = 1. V y a.b = ab = 1 và ta có l p a ∈ Zm là kh ngh ch. Ký hi u Z∗ là t p các ph n t kh ngh ch c a vành các l p th ng dư Zm . m Đ nh lý 1.3.4. T p Z∗ là m t nhóm giao hoán. m Ch ng minh:Trư c tiên ta ch ra Z∗ đóng kín đ i v i phép nhân. Gi m s l p a, b ∈ Z∗ . Theo Đ nh lý 1.3.3 có(a, m) = 1, (b, m) = 1. Do đó m (ab, m) = 1. Đi u này ch ng t a.b ∈ Z∗ hay Z∗ đóng kín đ i v i phép m m nhân. Hơn n a, phép nhân các l p th ng dư th a mãn lu t k t h p1 ∈ Z∗ . m Do đó Z∗ là m t v nhóm. m Ta ch ra, n u l p a ∈ Z∗ thì l p a có ngh ch đ o cũng thu c Z∗ . Th t m m vây, vì a ∈ Z∗ nên có b ∈ Zm đ a.b = 1. Hi n nhiên b ∈ Z∗ và b là ngh ch m m đ o c a a. Tóm l i Z∗ là m t nhóm v i phép nhân nói trên. Nhóm này m Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
12 giao hoán vì phép nhân giao hoán. Chú ý 1.3.5. Khi m = p là s nguyên t . Do đó Zp là m t trư ng và Z∗ p có p − 1 ph n t hay ϕ(p) = p − 1. 2 3 4 5 Ví d 1.3.6. Nhóm Z∗ = {1, 2, 2 = 4, 2 = 8, 2 = 7, 2 = 5} là m t 9 nhóm xiclic c p 6. T đó suy ra 22011 = 26.331+1 chia cho 9 dư 2. Ví d 1.3.7. Nhóm Z∗ = {1, 2, 4, 8, 7, 11, 13, 14} là m t nhóm c p 8. Các 15 ph n t c a Z∗ ch có c p 2 ho c c p 4. T đó suy ra 282011 = 284.502+3 15 chia cho 15 dư 7. Ví d 1.3.8. Tìm t t c các nghi m nguyên c a phương trình x3 + y 3 = z 6 + 3. Bài gi i: N u phương trình có nghi m trong Z thì nó cũng có nghi m trong Z7 . Khi đó có x, y, z ∈ Z7 đ x3 + y 3 = z 6 + 3. 3 3 3 3 3 3 3 Trong Z7 có 0 = 0, 1 = 1, 2 = 1, 3 = −1, 4 = −1, 5 = −1, 6 = −1. V y x3 hay y 3 ch có th là 0 ho c 1 ho c −1. Qua ki m tra ta có x3 + y 3 ch có th là 0, 1, 2, −1, −2. Nhưng z 6 + 3 ch có th là 0 + 3 = 3 ho c 1 + 3 = 4. Đi u này ch ng t phương trình vô nghi m. Ví d 1.3.9. Xét hai dãy s (xn ), (yn ) v i x0 = 0, y0 = 2 và s h ng khác: xn+1 = 17xn − 6yn + 22 yn+1 = 35xn − 12yn + 48, n 0. Ch ng minh r ng xn ≡ 3n+2 −1( mod 2n+3 ), yn ≡ −5.2n+2 +1( mod 3n+1 ). xn+1 + 1 = 17(xn + 1) − 6(yn − 1) Bài gi i: Th c hi n phép bi n đ i yn+1 − 1 = 35(xn + 1) − 12(yn − 1). N u coi xn + 1 và yn − 1 như an và bn thì có bi u di n sau đây  a0 = 1, b0 = 1 an+1 = 17an − 6bn bn+1 = 35an − 12bn  an = −8.2n + 9.3n Quy n p theo n ch ra công th c xác đ nh như sau: bn = −20.2n + 21.3n . Do v y xn ≡ 3n+2 − 1( mod 2n+3 ), yn ≡ −5.2n+2 + 1(mod3n+1 ). Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
13 an+1 17 −6 an Chú ý 1.3.10. Bi u di n d ng ma tr n bn+1 = 35 −12 bn . 17 −6 2 3 2 0 −7 3 Vì 35 −12 = 5 7 0 3 5 −2 nên ta có ngay bi u n a 2 3 2 0 −7 3 1 di n b n = 5 7 0 3n 5 −2 1 hay có bi u di n n xn + 1 −8.2n + 9.3n xn = −8.2n + 9.3n − 1 yn − 1 = −20.2n + 21.3n hay yn = −20.2n + 21.3n + 1. Do v y xn ≡ 3n+2 − 1( mod 2n+3 ), yn ≡ −5.2n+2 + 1(mod3n+1 ). Ví d 1.3.11. Ba dãy s (xn ), (yn ), (zn ) xác đ nh b i các phương trình sau:  x0 = 12, y0 = 8, z0 = 16  xn = 30xn−1 + 21yn−1 − 21zn−1  yn = 14xn−1 + 23yn−1 − 14zn−1  zn = 28xn−1 + 28yn−1 − 19zn−1 , n 1.  Hãy ch ng minh xn ˙ 24n+2 , yn ˙ 24n+3 , zn ˙ 24n+4 vàxn ˙ 24n+3 , yn ˙ 24n+4 , : : : : : zn ˙ 24n+5 v i m i n : 0. Bài gi i: Xét xn + tyn = (30 + 14t)xn−1 + (21 + 23t)yn−1 − (21 + 14t)zn−1 . Ch n t sao cho 21 + 23t = t(30 + 14t) hay 2t2 + t − 3 = 0 và như v y t = 1 3 3 3 3 ho c t = − . V i t = − ta có xn − yn = 9(xn−1 − yn−1 ) và suy ra 2 2 2 2 3 3 3 3 xn − yn = 9n (x0 − y0 ) = 9n (12 − 8) = 0. Ta nh n đư c xn = yn . Xét 2 2 2 2 yn + uzn = (14 + 28u)xn−1 + (23 + 28u)yn−1 − (14 + 19u)zn−1 . Ch n u sao cho (23 + 28u)u = −14 − 19u hay 28u2 + 42u + 14 = 0 và như v y u = −1 1 1 1 1 ho c u = − . V i t = − ta có yn − zn = 9(yn−1 − zn−1 ) và suy ra 2 2 2 2 1 n 1 n 1 1 yn − zn = 9 (y0 − z0 ) = 9 (8 − 16) = 0. Ta nh n đư c yn = zn . 2  2 2 2 x = y  n 3 x = z 3 n  n n Tóm l i ta đã có 2 hay 4 y = 1 z  n y = 1 z , n 0. n  n n 2 2 Quy n p theo n d dàng suy ra xn = 12.16n , yn = 8.16n , zn = 16.16n . Tóm l i xn = 3.24n+2 , yn = 24n+3 và zn = 24n+4 th a mãn xn ˙ 24n+2 , yn ˙ 24n+3 , zn ˙ 24 : : : và xn ˙ 24n+3 , yn ˙ 24n+4 , zn ˙ 24n+5 v i m i n : : : 0. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
14 1.4 Đ nh lý Euler và Đ nh lý Fermat Đ nh lý 1.4.1. [Euler] N u a, m ∈ Z, m > 0, (a, m) = 1 thì aϕ(m) ≡ 1 (mod m). Ch ng minh: Vì (a, m) = 1 nên a ∈ Z∗ . Gi s Z∗ = {a1 , . . . , aϕ(m) }. m m Vì Z∗ là m t nhóm giao hoán h u h n theo Đ nh lý 1.3.4, nên Z∗ = m m {aa1 , . . . , aaϕ(m) }. Nhân t t c các ph n t c a Z∗ theo hai cách vi t m ϕ(m) ϕ(m) ϕ(m) trên ta có ai = aϕ(m) ai . Do ai kh ngh ch nên aϕ(m) = 1 hay i=1 i=1 i=1 ϕ(m) a ≡ 1 (mod m). Đ nh lý 1.4.2. [Fermat bé] N u s nguyên a không chia h t cho s nguyên t p thì ap−1 ≡ 1 (mod p). Ch ng minh: Ta có ϕ(p) = p−1. Vì a không chia h t cho p nên (a, p) = 1. Theo Đ nh lý 1.4.1, ta có ap−1 ≡ 1 (mod p). H qu 1.4.3.N u p là s nguyên t thì ap ≡ a (mod p) v i m ia ∈ Z. Ch ng minh: N u a không chia h t cho p thì ap−1 ≡ 1 (mod p) theo Đ nh lý 1.4.2. Nhân hai v v i a ta nh n đư c ap ≡ a (mod p). N u a chia h t cho p, thì a ≡ 0 (mod p) và lũy th a p l n có ap ≡ 0 (mod p). V y ap ≡ a (mod p). Đ nh lý 1.4.4. [Wilson] V i s nguyên t p có (p−1)!+1 ≡ 0( mod p). Ch ng minh: Khi p = 2, k t qu là hi n nhiên. Khi p > 2, m i s nguyên n th a mãn 1 n p−1 đ u nguyên t v i p. V y có đúng m t s nguyên p−1 s th a mãn 1 s p − 1 và ns ≡ 1( mod p). Ta có c p (n, s) như 2 p−3 v y. L y tích các phương trìnhns ≡ 1( mod p) v i n 2 như v y 2 đư c 2.3.4 . . . (p − 3)(p − 2) ≡ 1( mod p). Nhân hai v phương trình này v i tích 1 và p − 1 đư c (p − 1)! + 1 ≡ 0( mod p). p−1 2 Ví d 1.4.5. Phương trình ! + 1 ≡ 0( mod p) th a mãn v i 2 t t c các s nguyên t p d ng 4n + 1. Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
15 Bài gi i: Theo Đ nh lý 1.4.4 có (p − 1)! + 1 ≡ 0( mod p) hay có th vi t p−1 p−1 2 2 k (p − k) + 1 ≡ 0( mod p). k=1 k=1 p−1 p−1 p−1 p−1 2 2 2 Vy ! + 1 = (−1) 2 k (p − k) + 1 ≡ 0( mod p). 2 k=1 k=1 1.5 M t vài ví d t ng h p Ví d 1.5.1. Tìm t t c các nghi m nguyên c a phương trình sau đây: x2 + 4y 4 = z 6 + 6. Bài gi i: N u phương trinh trong có nghi m trong Z thì nó cũng có nghi m trong Z8 . Khi đó có x, y, z ∈ Z8 đ x2 + 4y 4 = z 6 + 6. Trong Z8 ccó các h 2 2 2 2 2 2 2 2 th c: 0 = 0, 1 = 1, 2 = 4, 3 = 1, 4 = 0, 5 = 1, 6 = 4, 7 = 1. V y x2 ch có th là 0 ho c 1 ho c 4 và 4y 4 ch có th là 0 ho c 1. Qua ki m tra ta có x3 + 4y 4 ch có th là 0, 1, 2, 4, 5. Nhưng z 6 + 6 ch có th là 0 + 6 = 6 ho c 1 + 6 = 7. Đi u này ch ng t phương trình vô nghi m. Ví d 1.5.2. Gi s A và B là hai s đ u g m 9 ch s dương v i tính ch t: N u m t ch s b t kỳ c a A đư c thay b i m t ch s c a B vào đúng v trí tương ưng thì s nh n đư c chia h t cho 7. Ch ng minh r ng s nh n đư c qua vi c thay đ i ch s c a B b i m t ch s c a A vào đúng v trí tương ng cũng chia h t cho 7. Tìm m t s nguyên d > 9 đ tính ch t trên còn đúng khi A và B là hai s đ u g m d ch s dương. Bài gi i: Bi u di n duy nh t A = ad 10d + ad−1 10d−1 + · · · + a1 10 + a0 và B = bd 10d + bd−1 10d−1 + · · · + b1 10 + b0 . Đ t A∗ = ad 10d + ad−1 10d−1 + · · · + bk 10k + · · · + a1 10 + a0 và s này chia h t cho 7 theo gi thi t. V y Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
16 A∗ − A ≡ −A( mod 7) hay 10k (bk − ak ) ≡ −A( mod 7) v i b t kỳ s nguyên không âm k. Cho k = 0, 1, . . . , d và c ng t t c l i, ta nh n đư c A − B ≡ dA( mod 7). Ta ch ra k t qu đúng cho b t kỳ ≡ 2( mod 7). Khi đó A − B ≡ 2A( mod 7) hay A ≡ −B( mod 7). Đi u này ch ra 10k (ak − bk ) ≡ −B( mod 7) v i b t kỳ s nguyên không âm k. Do đó, khi thay m t ch s b t kỳ trong B b i m t ch s b t kỳ tương ng trong A ta cũng đư c m t s chia h t cho 7. Ví d 1.5.3. Cho s nguyên t p > 3. Ch ng minh r ng dư c a phép chia p s (j 2 + 1) cho p là 0 ho c 4. j=1 Bài gi i: Ta xét trư ng h p các l p th ng dư Zp . M r ng trư ng thành trư ng Zp [i] v i i2 = −1. Ta vi t j ∈ Zp qua j, phân tích p p p 2 (j + 1) = (j + i). (j − i) = f (i).f (−i), j=1 j=1 j=1 p trong đó f (x) = (j + x). Hi n nhiên f (x) ≡ xp − x trên Zp và như v y j=1 p (j 2 + 1) = (ip − i)((−i)p + i) = i(−i)[ip−1 − 1][(−i)p−1 − 1] j=1 p−1 = [(−1) 2 − 1]2 . p p−1 Do đó (j 2 + 1) = [(−1) 2 − 1]2 chia cho p dư 0 ho c 4. j=1 Ví d 1.5.4. Cho s nguyên t p > 3. Ch ng minh r ng n u dư c a phép p−1 chia s p cho 8 b ng 1 thì 2 2 − 1 chia h t cho p. Bài gi i: Ta xét trư ng h p các l p th ng dư Zp . M r ng trư ng thành Zp (α) v i α4 = −1. Khi đó trư ng Zp (α) có đ c s p = 8t + 1, t ∈ N∗ . Ta có(α + α−1 )p = αp + α−p = α + α−1 . Nhân hai v v iα + α−1 ta nh n đư c h th c dư i đây: −1 2 p+1 −1 2 2 −2 α4 + 1 [(α + α ) ] 2 = (α + α ) = α + 2 + α =2+ = 2. α2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn