5 Định Lý Wilson Và định Lý Euler - Tài Liệu Text - 123doc

Có thể bạn quan tâm

Trang chủ >
Giáo án - Bài giảng >
Tư liệu khác >

5 Định lý Wilson và định lý Euler

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (938.6 KB, 139 trang )

353.5. ĐỊNH LÝ WILSON VÀ ĐỊNH LÝ EULERVí dụ 3.5.1. Nếu m là số nguyên dương thì:1. Hệ 0, 1, ..., m − 1 là một hệ thặng dư đầy đủ modulo m; chúng ta sẽgọi hệ này là hệ thặng dư không âm nhỏ nhất modulo m.2. Nếu m là số lẻ thì hệ−m−1m−3m−1, −, ..., −1, 0, 1, ...,222cũng là hệ thặng dư đầy đủ modulodư tuyệt đối nhỏ nhất modulo m.hệ này được gọi là hệ thặngm;Đònh lý 3.13. Nếu các số r1 , r2 , ..., rm là một hệ thặng dư đầy đủ modulo mvà a nguyên tố cùng nhau với m thì hệar1 + b, ar2 + b, · · · , arm + bcũng là một hệ thặng dư đầy đủ modulo m.Chứng minh. Chúng ta chỉ cân chứng minh rằng, nếu 1 ≤ i < j ≤ m thìari ≡ arj (mod m).DoThật vậy, nếu ari ≡ arj (mod m) thì arj − ari | m, hay a(rj − ri ) | m.(a, m) = 1 ta suy ra (rj − ri ) | m và điều này không thể xảy ra vì0 < rj − ri < m.Đònh lý 3.14. Đònh lý nhỏ Fermat. Nếup−1a≡ 1 (mod p).plà số nguyên tố và pathìChứng minh. Không có số nào trong các số a, 2a, · · · , (p − 1)a là chia hếtcho p; vì nếu p | ja thì do (a, p) = 1 nên p | j vô lý với 1 ≤ j ≤ p − 1. Mặtkhác, dễ dàng thấy rằng (p − 1) số a, 2a, · · · , (p − 1)a là đôi một khôngđồng dư với nhau modulo p; do đó chúng đồng dư modulo p với hệ1, 2, · · · , p − 1.Vậy:Suy ra:a · 2a · · · (p − 1)a ≡ 1 · 2 · · · (p − 1) (mod p).ap−1 (p − 1)! ≡ (p − 1)! (mod p).Vì ((p − 1)!, p) = 1, nên theo đònh lý 3.3 ta có:ap−1 ≡ 1 (mod p).363. ĐỒNG DƯNhận xét:1. Đònh lý nhỏ Fermat nói rằng nếu n là số nguyên tố và b là số nguyênbất kỳ thì bn ≡ b (mod n). Điều này cũng có nghóa là nếu có số nguyênb để bn ≡ b (mod n) thì n là hợp số hoặc n = 1.2. Nếu b là một số nguyên dương, n là hợp số và b n ≡ bnói n là số giả nguyên tố cơ sở b.(mod n)thì ta3. Hợp số n được gọi là số Carmichael nếu bn ≡ b (mod n) với mọi sốnguyên dương b mà (b, n) = 1.Đối với mỗi số nguyên dương n, chúng ta ký hiệu ϕ(n) là số các số nguyêndương không vượt quá n và nguyên tố cùng nhau với n. Hàm số ϕ(n) đượcgọi là phi-hàm Euler.Tập gồm ϕ(m) các số nguyên được gọi là hệ thặng dư thu gọn modulom nếu mọi số nguyên nguyên tố cùng nhau với m đều đồng dư với đúngmột số nguyên của hệ.Dễ dàng thấy rằng: một hệ các số nguyên là hệ thặng dư ûthu gọn modulom khi và chỉ khi hệ này có đúng ϕ(m) số, nguyên tố cùng nhau với m vàđôi một không đồng dư với nhau modulo m.Ví dụ 3.5.2. Các số 1, 3, 5, 7 là hệ thặng dư ûthu gọn modulo 8. Các số−3, −1, 1, 3 cũng là hệ thặng dư ûthu gọn modulo 8.Hệ gồm (p − 1) : số 1, 2, · · · , p − 1 là hệ thặng dư thu gọn modulonguyên tố p.Đònh lý 3.15. Nếu các số r1 , r2 , ..., rϕ(m) là một hệ thặng dư thu gọn modulomvà a nguyên tố cùng nhau với m thì hệar1 , ar2 , · · · , arϕ(m)cũng là một hệ thặng dư thu gọn modulo m.Chứng minh. Hệ ar1 , ar2 , · · · , arϕ(m) gồm ϕ(m) số nguyên.Từ (a, m) = (rj , m) = 1 dễ dàng suy ra (arj , m) = 1; vậy mỗi số của hệnguyên tố cùng nhau với m.373.5. ĐỊNH LÝ WILSON VÀ ĐỊNH LÝ EULERNếu có 1 ≤ i < j ≤ ϕ(m) để ari ≡ arj (mod m) thì m | a(ri − rj ). Do(m, a) = 1 ta suy ra m | (ri − rj ), hay ri ≡ rj (mod m), điều này vô lý vớigiả thiết ri ≡ rj (mod m).Đònh lý sau đây là một mở rộng của đònh lý FermatĐònh lý 3.16. Đònh lý Euler. Nếu m là số nguyên dương và (a, m) = 1 thìaϕ(m) ≡ 1 (mod m).Chứng minh. Lấy hệ thặng dư thu gọn ar1 , ar2 , · · · , arϕ(m) . Do (a, m) = 1,nên từ đònh lý trên ta có ar1 , ar2 , · · · , arϕ(m) cũng là hệ thặng dư thu gọn.Vậy các số của hệ này đồng dư modulo m với các số của hệ kia. Vậyar1 ar2 · · · arϕ(m) ≡ r1 r2 · · · rϕ(m)Hayaϕ(m) r1 r2 · · · rϕ(m) ≡ r1 r2 · · · rϕ(m)(mod m)(mod m)Vì (r1r2 · · · rϕ(m) , m) = 1 ta suy ra aϕ(m) ≡ 1 (mod m).Đònh lý Euler có rất nhiều ứng dụng. Chẳng hạn, ta có thể dễ dàng xácđònh nghòch đảo a của số nguyên a modulo m. Ta đã biết rằng số nguyêna có nghòch đảo modulo m khi và chỉ khi (a, m) = 1. Do Đònh lý Euler:a · aϕ(m)−1 = aϕ(m) ≡ 1 (mod m), ta có a = aϕ(m)−1 .Ví dụ 3.5.3. Tìm nghòch đảo modulo 10 của 3. Giải phương trình 3x ≡ 8(mod 10).Ta có 3 = 3ϕ(10)−1 = 34−1 = 27 ≡ 7(mod 10).3x ≡ 8 (mod 10) ⇔ 3·3x ≡ 3·8 (mod 10) ⇔ x ≡ 7·8 (mod 10) ⇔ x ≡ 6(mod 10)BÀI TẬP CHƯƠNG III383. ĐỒNG DƯ1. Giả sửa, b, c là các số nguyên, c > 0.(mod c) thì (a, c) = (b, c).2. Giả sử a, b, k, m là các số nguyên,minh rằng nếu ak ≡ bk (mod m) vàChứng minh rằng nếua ≡ bk, m > 0, (a, m) = 1. Chứngak+1 ≡ bk+1 (mod m) thì a ≡ b(mod m)3. Chứng minh rằng nếu p nguyên tố và k nguyên dương thì nghiệm duynhất của đồng dư x2 ≡ x (mod pk ) là x ≡ 0 hoặc x ≡ 1 (mod pk ).4. Giả sử m1, m2 , ..., mk là các số nguyên dương đôi một nguyên tố cùngnhau, M = m1m2 · · · mk và Mj = M/mj . Chứng minh rằngM1 a1 + M2 a2 + · · · + Mk akchạy trên hệ thặng dư đầy đủ modulo M khi a1 , a2 , ..., ak tương ứngchạy trên hệ thặng dư đầy đủ modulo m1, m2 , · · · , mk .5. Chứng minh rằng với mỗi số nguyên dương m đều có vô số số Fibonaccifn là bội của m.6. Giải các đồng dư saua) 19x ≡ 30 (mod 40)c) 980x ≡ 1500 (mod 1600)e) 6x ≡ 3 (mod 9)g) 15x ≡ 9 (mod 25)b) 103x ≡ 444 (mod 999)d) 3x ≡ 2 (mod 7)f) 17x ≡ 14 (mod 21)h) 128x ≡ 833 (mod 1001)7. Giải các đồng dư hai biến saua) 2x + 3y ≡ 1c) 6x + 3y ≡ 0(mod 7)(mod 9)b) 2x + 4y ≡ 6 (mod 8)d) 10x + 5y ≡ 9 (mod 15)8. Giả sử p là nguyên tố lẻ và k nguyên dương. Chứng minh rằng đồngdư x2 ≡ 1 (mod pk ) có đúng hai nghiệm không đồng dư nhau modulopk , đó là x ≡ ±1 (mod pk ).9. Chứng minh rằng đồng dư x 2 ≡ 1 (mod 2k ) có đúng bốn nghiệm khôngđồng dư nhau modulo 2k , đó là x ≡ ±1 (mod pk ) hoặc x ≡ ±(1 + 2k−1(mod pk ) khi k > 2. Chứng tỏ rằng khi k = 1 thì chỉ có một nghiệm vàkhi k = 2 thì có đúng hai nghiệm không đồng dư nhau.393.5. ĐỊNH LÝ WILSON VÀ ĐỊNH LÝ EULER10. Giả sử p là nguyên tố lẻ và a nguyên dương không chia hết cho p.Chứng minh rằng đồng dư x2 ≡ a (mod p) không có nghiệm hoặc cóđúng hai nghiệm không đồng dư nhau modulo p.11. Giải các hệ đồng dư saua)x ≡ 4 (mod 11)x ≡ 3 (mod 17)b) x ≡ 1 (mod 2)x ≡ 2 (mod 3)x ≡ 3 (mod 5)12. Chứng minh rằng hệ đồng dưx ≡ a1x ≡ a2(mod m1 )(mod m2 )có nghiệm khi và chỉ khi (m1, m2 ) | (a1 − a2 ); trong trương hợp cónghiệm thì nghiệm là duy nhất modulo [m1 , m2 ].Hãy phát triển cho bài toán tổng quát x ≡ a1 x ≡ a2 x≡ak(mod m1 )(mod m2 )...(mod mk )13. Giải các hệ đồng dư saua)c)x3x2xx++++3y4y3y5y≡1≡2≡5≡6(mod 5)(mod 5)(mod 7)(mod 7)b)d)4x2x4xx+ y ≡2+ 3y ≡ 1+ y ≡5+ 2y ≡ 4(mod(mod(mod(mod5)5)7)7)403. ĐỒNG DƯ14. Giải các hệ đồng dư saua) 2x + 3y + z ≡ 3x + 2y + 3z ≡ 12x + z ≡ 1(mod 5)(mod 5)(mod 5)b) 3x + y + 3z ≡ 1x + 2y + 4z ≡ 24x + 3y + 2z ≡ 3(mod 7)(mod 7)(mod 7)c) 2x + y + z ≡ 3x + 2y + z ≡ 1x + y + 2z ≡ 2(mod 11)(mod 11)(mod 11)15. Bằng cách sử dụng đònh lý Wilson hãy chứng tỏ rằng nếu p là sốnguyên tố và p ≡ 1 (mod 4) thì đồng dư x2 ≡ −1 (mod p) có hainghiệm không đồng dư nhau là x ≡ ±((p − 1)/2)! (mod p).16. Chứng minh rằng nếu(ap + (p − 1)! a).plà số nguyên tố vàalà số nguyên thìp |17. Chứng minh rằng nếu p nguyên tố và 0 < k < p thì (p − k)!(k − 1)! ≡(−1)k (mod p).18. Hãy sử dụng đònh lý Fermat để tìm thặng dư dương nhỏ nhất của 21000000modulo 17.19. Hãy sử dụng đònh lý Fermat để tìm chữ số cuối cùng của 3100 trong hệđếm cơ số 7.20. Hãy sử dụng đònh lý Fermat để giải các phương trìnha) 7x ≡ 12b) 4x ≡ 11(mod 17) ,21. Chứng minh rằng nếuq p−1 ≡ 1 (mod pq).p, q(mod 19).là các số nguyên tố khác nhau thì22. Chứng minh rằng nếu p là số nguyên tố,ap ≡ bp (mod p) thì ap ≡ bp (mod p2 ).a, bpq−1 +là các số nguyên và413.5. ĐỊNH LÝ WILSON VÀ ĐỊNH LÝ EULER23. Hãy sử dụng đònh lý Euler để tìm chữ số cuối cùng của:a) 71000.b) 51000000 trong hệ thập lục phân.24. Hãy tìm một hệ thặng dư thu gọn modulo 2m.25. Chứng minh rằng nếu m > 2 và c1 , c2 , · · · , cϕ(m) là hệ thặng dư thugọn modulo m thì c1 + c2 + · · · + cϕ(m) ≡ 0 (mod m).26. Chứng tỏ rằngϕ(m1 )x ≡ a1 M1ϕ(m2 )+ a2 M2ϕ(mk )+ · · · + ak Mk(mod M )là nghiệm duy nhất của hệ đồng dư x ≡ a1 x ≡ a2 x≡ak(mod m1 )(mod m2 )...(mod mk )trong đó các mj đôi một nguyên tố cùng nhau, M = m1 m2 · · · mk , Mj =M/mj , 1 ≤ j ≤ k.423. ĐỒNG DƯ4CÁC HÀM SỐ HỌC4.1 Nhận xét chungHàm số học là hàm nhận giá trò thực hoặc phức và xác đònh trên tập sốnguyên dương.Hàm số học f không đồng nhất bằng 0, được gọi là có tính nhân nếuuf (mn) = f (m)f (n), với (m, n) = 1. Hàm số học f không đồng nhất bằng0, được gọi là có tính nhân đầy đủ nếuu f (mn) = f (m)f (n), với mọi sốnguyên dương m, n.Hiển nhiên, hàm có tính nhân đầy đủ là hàm có tính nhân. Hàm f cótính nhân thì f (1) = 1.Ví dụ 4.1.1. Hàm đồng nhất bằng một, f (n) = 1 với mọi n, có tính nhânđầy đủ, vì f (mn) = 1 = f (m)f (n). Hàm đồng nhất, f (n) = n với mọi n,cũng có tính nhân đầy đủ, vì f (mn) = mn = f (m)f (n).Có nhiều hàm số học là không chính qui. Bởi thế người ta thường khôngxét hàm số học f mà xét hàm tổng của nó, đó làNF (N ) =f (n).n=1Sau đây là một số tính chất của hàm số học có tính nhân.43444. CÁC HÀM SỐ HỌCĐònh lý 4.1. Giả sử f là hàm có tính nhân và n = pα pα1 212lũy thừa nguyên tố của số nguyên dương n thì· · · pα kklà khai triểnf (n) = f (pα1 )f (pα2 ) · · · f (pαk ).12kChứng minh. Vì i = j thì pi và pj là các số nguyên tố khác nhau, ta suy raαk−1(pα1 pα2 · · · pk−1 , pαk ) = 1,1 2ktừ đóααk−1k−1f (pα1 pα2 · · · pk−1 pαk ) = f (pα1 pα2 · · · pk−1 )f (pαk ).1 21 2kkĐònh lý 4.2. Nếu f có tính nhân thì hàmf (d)g(n) =d|ncũng có tính nhân.Chứng minh. Hàm g không đồng nhất bằng không, vìf (1) = 1.g(1) =d|1β ββGiả sử m = pα pα · · · pα và n = q1 q2 · · · qs là khai triển lũy thừa nguyên1 2rtố tương ứng của các số nguyên dương m và n. Nếu (m, n) = 1 thì pi và qjlà các số nguyên tố khác nhau. Từ đây ta suy ra, mỗi ước d của121r2sβ ββmn = pα1 pα2 · · · pαr q1 1 q2 2 · · · qs s1 2rđược viết một cách duy nhất thành tích của các ước nguyên tố cùng nhau d1của m và d2 của n. Vậyf (d) =g(mn) =f (d1 d2 ).d1 | md2 | nd|mnVì f có tính nhân và (d1 , d2 ) = 1 nên f (d1 d2 ) = f (d1 )f (d2 ), suy rag(mn) =f (d1 )f (d2 ) =d1 | md2 | nf (d1 )d1 | mf (d2 ) = g(m)g(n).d2 | n454.1. NHẬN XÉT CHUNGĐònh lý 4.3. Nếu hàm số học f có tính nhân vàf (pm ) → 0khi pm → ∞trong đó p là số nguyên tố và m là số nguyên dương, thìf (n) → 0khi n → ∞.Chứng minh. Vì f (pm ) → 0 khi pm → ∞ nên ta có nhận xét rằng f thỏacác điều kiện sau:1. Có hằng số dương A sao cho với mọi m và p ta đều có|f (pm )| < A.2. Có hằng số dương B sao cho|f (pm )| < 1nếu pm > B.3. Với mọi ε > 0 đều có số N (ε), chỉ phụ thuộc vào ε, sao cho|f (pm )| < εGiả sửnếu pm > N (ε).n = pα 1 pα 2 · · · pα k1 2klà khai triển lũy thừa nguyên tố của số nguyên dương n > 1. Thế thìf (n) = f (pα1 )f (pα2 ) · · · f (pαk ).12kVì chỉ có hữu hạn các số dạng pα mà pα ≤ N (ε), nên ta suy ra rằngchỉ có hữu hạn các số nguyên mà tất cả các lũy thừa nguyên tố củanó đều không vượt quá N (ε). Đặt P (ε) là cận trên cho các số nguyênnhư vậy.Nếu n > P (ε), thì trong khai triển thành lũy thừa nguyên tố của n phảicó ít nhất một thừa số pα mà pα > N (ε). Gọi C là số các lũy thừanguyên tố pα mà pα ≤ B. Thế thì từ nhận xét trên ta suy raii|f (n)| < AC ε.

Xem Thêm