Đại học Lê Quý Đôn - 236 Hoàng Quốc Việt - Hà Nội

Chia sẻ kiến thức mọi mặt của các lớp cao học CNTT, Học viện Kỹ thuật Quân sự


[Hướng dẫn]Cách giải hệ phương trình đồng dư54.567


Chào mừng đã đến với forum khmt.123.st
  • Bạn chưa đăng kí (hoặc chưa đăng nhập) nên quyền lợi của bạn sẽ bị hạn chế. Việc đăng kí làm thành viên hoàn toàn miễn phí, sau khi đăngkí bạn có thể post bài, tham gia thảo luận , nhìn thấy link ở những box hạn chế ... và rất nhiều quyền lợi khác. Thủ tục đăng kí rất nhanh chóng và đơn giản, hãy Đăng kí làm thành viên !
  • Nếu bạn quên mật khẩu, xin nhấn vào đây !
  • Nếu bạn gặp trục trặc trong vấn đề đăng kí hoặc không thể đăng nhập, hãy liên hệ với chúng tôi.




  • Chuyển đến trang : 1, 2  Next

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Go down  Thông điệp [Trang 1 trong tổng số 2 trang]

    Admin


    Quản trị viên
    Quản trị viên
    Giải hệ phương trình đồng dư:

    [You must be registered and logged in to see this image.]
    [You must be registered and logged in to see this image.]
    [You must be registered and logged in to see this image.]
    [You must be registered and logged in to see this image.]




    Được sửa bởi Admin ngày Sun Jun 26, 2011 10:49 am; sửa lần 2.

    http://khmt.123.st

    2 Cách giải hệ phương trình đồng dư on Wed May 18, 2011 4:10 pm

    Admin


    Quản trị viên
    Quản trị viên
    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


    [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ới

    y1 = (M1) − 1(mod m1) < = > y1M1 = 1(mod m1)

    Ví dụ mẫu:



    Giải hệ phương trình đồng dư

    [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.]
    [You must be registered and logged in to see this image.]
    [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)

    http://khmt.123.st

    3 Một số kiến thức đồng dư on Wed May 18, 2011 4:51 pm

    Admin


    Quản trị viên
    Quản trị viên
    Định nghĩa


    Cho 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 quan hệ tương đương
    (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.][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 nguyên tố cùng nhau) 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



    • Nếu [You must be registered and logged in to see this image.] là một hệ thặng dư đầy đủ mô-đun n thì [You must be registered and logged in to see this image.] là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a.
    • Nếu [You must be registered and logged in to see this image.] là một hệ thặng dư đầy đủ mô-đun n thì [You must be registered and logged in to see this image.] là một hệ thặng dư đầy đủ mô-đun n với mọi số nguyên a nguyên tố cùng nhau với n.

    http://khmt.123.st

    hungbeo_fm2008


    Chuyên viên
    Chuyên viên
    Để lý giải cho dễ, theo công thức chung thì:
    a1 = 2
    a2 = 3
    a3 = 4
    a4 = 6
    sau mod là các số chia, tức là
    m1 = 5
    m2 = 7
    m3 = 8
    m4 = 13
    Bước 1: Tính số M là tích của tất cả các số chia (Những số ở đằng sau chữ mod ý)
    Ta có:
    M = 5 x 7 x 8 x 13 = 3510

    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)= 2

    Hệ phương trình có nghiệm duy nhất:

    x ≡ (a1.M1.y1 + a2.M2.y2 + a3.M3.y3 + a4.M4.y4) (mod M) (*)

    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)

    mrP


    Thành viên cao cấp
    Thành viên cao cấp
    - đừng có làm mò số to thế, chuyển sang số nhỏ hơn mà mò :D

    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.

    Admin


    Quản trị viên
    Quản trị viên
    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.

    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    Đề thầy cho tiếp
    1. 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.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    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.]Thử xem. Nháy vào đây để download



    Đượ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.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    Admin


    Quản trị viên
    Quản trị viên
    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 = 15

    Cá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.
    [You must be registered and logged in to see this image.]
    Trang phục may sẵn rẻ nhất Hà Nội ở 148 Vương Thừa Vũ
    ĐT: 043.568.1938

    [You must be registered and logged in to see this link.]
    [You must be registered and logged in to see this link.]
    http://khmt.123.st

    10 hệ phương trình đồng dư on Fri Jul 29, 2011 7:56 pm

    tranhue


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    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?

    http://khmt.123.st

    Tongmanhcuong


    Thành viên cao cấp
    Thành viên cao cấp
    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


    ================

    tranhue


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    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ố.

    http://khmt.123.st

    TuanNghia


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    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 đó.

    tranhue


    Thành viên chưa phát huy chia sẻ
    Thành viên chưa  phát huy chia sẻ
    em đã hiểu rõ. cảm ơn anh nhiều nha

    Ban QT: [You must be registered and logged in to see this link.]

    http://khmt.123.st

    tendep73


    Thành viên bắt đầu chia sẻ
    Thành viên bắt đầu chia sẻ
    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:
    File này nói quá chi tiết rồi, sao không đao về xem mà bắt người khác copy lên cho mình xem? Bạn có biết cách down bằng cách nháy vào link này không?

    AutoAdd: Anh em coi dùm tính yi dựa Euclid mở rộng

    Ban QT: Nhắc bạn nháy lên link trên down cái file trên về xem. Không hỏi những câu hỏi như vậy nữa, vì những câu hỏi của bạn trong file trên đã trả lời rất rõ rồi. Tại sao bạn cố tình không chịu đọc mà vẫn hỏi để bắt người khác copy dán hộ mình nhỉ?

    http://nguyenvantien.ucoz.com

    Xem chủ đề cũ hơn Xem chủ đề mới hơn Về Đầu Trang  Thông điệp [Trang 1 trong tổng số 2 trang]

    Chuyển đến trang : 1, 2  Next

    Permissions in this forum:
    Bạn không có quyền trả lời bài viết

     

    Ghi rõ nguồn khi copy các bài viết từ Website này.
    Bản quyền thuộc Khoa học Máy tính. Số lượt truy cập tính đến hiện tại:Website counter
    Modified skin by Nguyễn Anh Cường. Developed by Members of http://khmt.123.st

    Free forum | © PunBB | Free forum support | Liên hệ | Report an abuse | Create a free blog