Giải phương trình 2x 9 (mod 13)
1 [Hướng dẫn]Cách giải hệ phương trình đồng dư Thu May 12, 2011 9:19 pm Show
Bài gửi : 785 Được sửa bởi Admin ngày Sun Jun 26, 2011 10:49 am; sửa lần 2. 2 Cách giải hệ phương trình đồng dư Wed May 18, 2011 4:10 pmBài gửi : 785 Cách giải hệ phương trình đồng dư Lý thuyết:Giải hệ phương trình đồng dư bậc nhất[You must be registered and logged in to see this image.] trong đó m1,m2,...,mk đôi một nguyên tố cùng nhau. Trong bài toán Hàn Tín k = 3 và m1 = 3,m2 = 5,m3 = 7. Định lý Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mođun M = m1.m2...mk là [You must be registered and logged in to see this image.] trong đó M1 = M / m1,M2 = M / m2,...,Mk = M / mk y1 = (M1) − 1(mod m1), y2 = (M2) − 1(mod m2),..., yk = (Mk) − 1(mod mk) Trong đó (M1) − 1(mod m1) là nghịch đảo theo modulo của m1 vớiy1 = (M1) − 1(mod m1) < = > y1M1 = 1(mod m1) Ví dụ mẫu: [You must be registered and logged in to see this image.] ta cóM = 3.5.7 = 105;M1 = 5.7 = 35,M2 = 3.7 = 21,M3 = 3.5 = 15. y1 = 35 − 1(mod 3) = 2 − 1(mod 3) = 2; y2 = 21 − 1(mod 5) = 1 − 1(mod 5) = 1; y3 = 15 − 1(mod 7) = 1 − 1(mod 7) = 1.Từ đó [You must be registered and logged in to see this image.]. Như vậy x có dạng x = 68 + k.105, k là số nguyên (hoặc số nguyên thích hợp nếu tìm nghiệm tự nhiên) 3 Một số kiến thức đồng dư Wed May 18, 2011 4:51 pmBài gửi : 785 Định nghĩaCho số nguyên dương n, hai số nguyên a,b được gọi là đồng dư theo mô-đun n nếu chúng cho cùng số dư khi chia cho n (hay là a-b chia hết cho n). Kí hiệu là: [You must be registered and logged in to see this image.]Ví dụ: [You must be registered and logged in to see this image.] Vì 11 và 5 khi chia cho 3 đều cho số dư là 2.Tính chất Ngoài các tính chất của một [You must be registered and logged in to see this link.] (phản xạ, đối xứng, bắc cầu), phép đồng dư còn có thêm các tính chất sau: Có thể cộng, trừ, nhân và nâng lên lũy thừa các đồng dư thức có cùng một mô-đun, cụ thể. Nếu ta có:[You must be registered and logged in to see this image.] Thì ta có:Luật giản ước Nếu [You must be registered and logged in to see this image.] và (b,n)=1 (b,n [You must be registered and logged in to see this link.]) thì [You must be registered and logged in to see this image.] Nghịch đảo mô-đun Nếu số nguyên dương n và số nguyên a nguyên tố cùng nhau thì tồn tại duy nhất một số [You must be registered and logged in to see this image.] sao cho: [You must be registered and logged in to see this image.], số x này được gọi là nghịch đảo của a theo mô-đun n. Hệ thặng dư đầy đủ Tập hợp [You must be registered and logged in to see this image.] được gọi là một hệ thặng dư đầy đủ mô-đun n nếu với mọi số nguyên i, [You must be registered and logged in to see this image.], tồn tại duy nhất chỉ số j sao cho [You must be registered and logged in to see this image.]. Tính chất
4 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri May 20, 2011 8:06 amBài gửi : 70 Để lý giải cho dễ, theo công thức chung thì: Bước 2: Tính các M1. M1 là lấy M to, chia cho số chia (m1 sau chữ mod) của dòng đó. (Hoặc nhân các số chia m2 x m3 x m4, của các dòng khác với dòng 1). Tương tự đối với M2, M3, M4. M1 = M/m1 = 7 x 8 x 13 = 728 M2 = M/m2 = 5 x 8 x 13 = 520 M3 = M/m3 = 5 x 7 x 13 = 455 M4 = M/m4 = 5 x 7 x 8 = 280 Bước 3: Tính các số y cho từng dòng. Theo định nghĩa, số y1 là nghịch đảo của số M1 với số chia m1. Nghĩa là lấy số M1 (trên tính được là 728) nhân thử với y1 là các số 1, 2, 3, 4... rồi chia cho số chia. Chọn lấy số y1 nào mà có tích (M1 nhân y1) chia cho m1 (là 5, phải dư 1). Có:y1 = m1-1(mod m1) = 728-1 (mod 5) = 2 (do 728 x 2= 1456 mod 5 = 1) Tương tự ta có:y2 = m2-1(mod m2) = 520 - 1(mod 7) = 4 (do 520 x 4 mod 7 = 1). y3 = m4-1(mod m4) = 455-1(mod 8) = 7 y4 = m4-1(mod m4) = 280-1(mod 13)= 2Hệ phương trình có nghiệm duy nhất:
Bước 4. Thay vào (*) ta có nghiệm của hệ phương trình đã cho là:x ≡ 25252 (mod 3510) Lấy 25252 chia cho 3510 dư 682 x = 25252 mod 3510 = 682[You must be registered and logged in to see this image.] Vậy x = 682. Được sửa bởi Admin ngày Fri May 20, 2011 9:04 am; sửa lần 2. (Reason for editing : Có thể gõ vào Word, định dạng, rồi copy dán vào) 5 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri May 20, 2011 8:22 amBài gửi : 104 - đừng có làm mò số to thế, chuyển sang số nhỏ hơn mà mò ví dụ:Y1 = 728-1(mod5) = 3-1(mod5) -->(Y1*3)=1(mod5) --> Y1 = 2(mod5)Tương tự ta có: y2 = m2-1(mod m2) = 520 - 1(mod 7) = 2 - 1(mod 7). (Do 520 = 74 * 7 + 2) --> y2*2 = 1(mod 7) --> y2 = 4 (mod 7) y3 = m3-1(mod m4) = 455-1(mod 8) = 7-1(mod 8) --> y3*7 = 1 (mod 8) -- > y3 = 7 (mod 8) y4 = m4-1(mod m4) = 280-1(mod 13)= 7-1(mod 13) -->y4*2=1 (mod 13)-->y4 = 2 (mod 13) Được sửa bởi mrP ngày Fri May 20, 2011 10:24 pm; sửa lần 1. 6 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri May 20, 2011 9:08 amBài gửi : 785 Việc chuyển sang số nhỏ hơn cũng cần cảnh giác vì việc chia cho một số d để được số nhỏ hơn, thì số d và số chia (sau mod) phải là nguyên tố cùng nhau (USCLN =1). Nếu không để ý, sai luôn. 7 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Mon May 30, 2011 6:09 pmBài gửi : 785 Đề thầy cho tiếp1. Giải hệ phương trình đồng dư:x ≡ 2 (mod 3)x ≡ 3 (mod 7)x ≡ 2 (mod 11)2. Giải hệ phương trình đồng dư:x ≡ 4 (mod 7)x ≡ 6 (mod 11)x ≡ 9 (mod 13) Các đ/c cần nói rõ cách tính y, nếu không sẽ bị trừ hết điểm bài này. ================ Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền. 8 [Hướng dẫn]Chi tiết nhất về cách tính phần tử nghịch đảo hệ phương trình đồng dư Thu Jun 02, 2011 11:27 amBài gửi : 785 Việc giải các hệ phương trình đồng dư đã có hướng dẫn từng bước. Bước khó khăn nhất là tính phần tử nghịch đảo. Cách tính và giải thích các bước như thế nào.Bạn download file này về.Nhập vào: Số a, số m.Nhận được: Bảng chi tiết từng bước của từng giá trị.Đồng thời đặt hộp sáng ở giá trị nào, có giải thích chi tiết cách tính giá trị đó.Rất hữu ích đối với các bạn. [You must be registered and logged in to see this image.][You must be registered and logged in to see this link.] Được sửa bởi Admin ngày Thu Jun 02, 2011 12:27 pm; sửa lần 1. ================ Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền. 9 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Thu Jun 02, 2011 5:41 pmBài gửi : 785 Hôm nay kiểm tra mới thấy nhiều người không để ý, đã nhắc ở tiểu mục 6 là muốn áp dụng hệ đồng dư Trung Quốc phải đưa về dạng nguyên tố cùng nhau của các m. Tôi gõ lại để bạn nào đi vắng vẫn có thể đọc và nhận dạng câu hỏi loại nàyĐề bài:Giải hệ phương trình đồng dư:x ≡ 5 (mod 6)x ≡ 3 (mod 10)x ≡ 8 (mod 15)Ta thấy: m1 = 6 m2 = 10 m3 = 15Các m không phải là nguyên tố cùng nhau từng đôi một, nên không thể áp dụng phương pháp tìm nghiệm theo hệ thức của đồng dư Trung Quốc. Chính vì vậy phải biến đổi:x ≡ 5 (mod 6) tương đương với:x ≡ 1 (mod 2)x ≡ 2 (mod 3) Để có 2 phương trình đồng dư trên, các đồng chí phân tích m1 ra thừa số. Ví dụ trong trường hợp này 6 = 2 x 3, nên sẽ biến thành 2 biểu thức trên. Lấy số a = 5, chia cho từng số chia mới (2 và 3)được số dư mới là 1 và 2, tương ứng với mod mới là 2 và 3.Tương tự ta có:x ≡ 3 (mod 10) tương đương với:x ≡ 1 (mod 2)x ≡ 3 (mod 5)x ≡ 8 (mod 15) tương đương với:x ≡ 2 (mod 3)x ≡ 3 (mod 5)Tồng hợp, hệ phương trình đã cho tương đương với hệ:x ≡ 1 (mod 2)x ≡ 2 (mod 3)x ≡ 3 (mod 5) Giả theo đồng dư Trung Quốc sẽ nhận được x = 23. ================ Nếu Khách viếng thăm không đọc được các bài trong Kho bài chuẩn, là do Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.]. Sở dĩ nếu Khách viếng thăm không tham gia được vào nhóm [You must be registered and logged in to see this link.] là vì Khách viếng thăm khai báo thiếu họ, thiếu tên, không dấu hoặc khai báo linh tinh trong trường RN. Đừng xin xỏ uỷ quyền, vì uỷ quyền hoàn toàn tự động cho Thành viên đọc được mọi thứ (không chỉnh bằng tay được), các thành viên khác sẽ không bao giờ được uỷ quyền. 10 hệ phương trình đồng dư Fri Jul 29, 2011 7:56 pmBài gửi : 7 giải hệ phương trình đồng dưx=2(mod 3)x=4(mod 5)x=5(mod 7)x=7(mod 11)các bạn cho tớ hỏi giải hệ đồng dư trên có giống như giải hệ đồng dư 3 pt ko? 11 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri Jul 29, 2011 8:03 pmBài gửi : 127 Một câu hỏi thú vị? Bạn hỏi thế mình không biết phải trả lời thế nào? Vì mình không hiểu câu hỏi? Do vậy mình trả lời thế này: Giống hệt bạn ạ. Mong là đúng ý của bạn. Hihihihih 12 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri Jul 29, 2011 11:04 pmBài gửi : 7 em cảm ơn anh. nhưng anh cho hỏi chút nữa. ở bài đầu tiên anh làm x= 4 (mod 8)8 ở đây ko phải là số nguyên tố . tại sao anh vẫn giải nó như số nguyên tố bình thường Admin: Bạn nhầm lẫn khái niệm nguyên tố cùng nhau với số nguyên tố. 13 Có cần thiết phải lập bảng để làm theo TT Euler mở rộng Fri Jul 29, 2011 11:52 pmBài gửi : 10 Em thấy để tính được các y theo TT Euler phải lập bảng ra, trong bài thi, chúng ta có nhất thiết phải đưa cả bảng vào bài làm, hay lập bảng ngoài nháp rồi ghi kết quả vào là được?Mong các anh có ý kiến kẻo lại mất điểm Admin: Không hiểu câu hỏi TT Euler là gì, bài toán này không dùng khái niệm đó. 14 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Sun Jul 31, 2011 8:46 pmBài gửi : 7 em đã hiểu rõ. cảm ơn anh nhiều nha Ban QT: [You must be registered and logged in to see this link.] 15 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Mon Aug 01, 2011 6:17 amBài gửi : 11 Có bạn biết kẻ bảng euclid không kẻ lên cho mọi người xem với.Thnhks Ban QT: [You must be registered and logged in to see this link.]AutoAdd: Anh em coi dùm tính yi dựa Euclid mở rộng [You must be registered and logged in to see this link.] 16 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Mon Dec 23, 2013 9:25 amBài gửi : 1 giai cua thya hay that day 17 Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Thu May 01, 2014 7:44 amBài gửi : 2 Ghét ...!!! Admin ka ka. Em thích bài này |