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 đó m₁,m₂,...,m_k đôi một nguyên tố cùng nhau. Trong bài toán Hàn Tín k = 3 và m₁ = 3,m₂ = 5,m₃ = 7.
Định lý


Hệ phương trình đồng dư nói trên có nghiệm duy nhất theo mođun

M = m₁.m₂...m_k
là

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

M₁ = M / m₁,M₂ = M / m₂,...,M_k = M / m_k
y₁ = (M₁) ^{− 1}(mod m₁), y₂ = (M₂) ^{− 1}(mod m₂),..., y_k = (M_k) ^{− 1}(mod m_k)

Trong đó

(M₁) ^{− 1}(mod m₁) là nghịch đảo theo modulo của m₁
với

y₁ = (M₁) ^{− 1}(mod m₁) < = > y₁M₁ = 1(mod m₁)

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;M₁ = 5.7 = 35,M₂ = 3.7 = 21,M₃ = 3.5 = 15.
y₁ = 35 ^{− 1}(mod 3) = 2 ^{− 1}(mod 3) = 2;
y₂ = 21 ^{− 1}(mod 5) = 1 ^{− 1}(mod 5) = 1;
y₃ = 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)

Đị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 [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ó:

• [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.], với k nguyên.
  

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

• 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.
  

Để lý giải cho dễ, theo công thức chung thì:
a₁ = 2
a₂ = 3
a₃ = 4
a₄ = 6
sau mod là các số chia, tức là
m₁ = 5
m₂ = 7
m₃ = 8
m₄ = 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 M₁. M₁ là lấy M to, chia cho số chia (m₁ sau chữ mod) của dòng đó. (Hoặc nhân các số chia m₂ x m₃ x m₄, của các dòng khác với dòng 1). Tương tự đối với M₂, M₃, M₄.

M₁ = M/m₁ = 7 x 8 x 13 = 728
M₂ = M/m₂ = 5 x 8 x 13 = 520
M₃ = M/m₃ = 5 x 7 x 13 = 455
M₄ = M/m₄ = 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ố y₁ là nghịch đảo của số M₁ với số chia m₁. Nghĩa là lấy số M₁ (trên tính được là 728) nhân thử với y₁ là các số 1, 2, 3, 4... rồi chia cho số chia. Chọn lấy số y₁ nào mà có tích (M₁ nhân y₁) chia cho m₁ (là 5, phải dư 1).

Có:
y₁ = m₁-1(mod m₁) = 728-1 (mod 5) = 2 (do 728 x 2= 1456 mod 5 = 1)
Tương tự ta có:
y₂ = m₂-1(mod m₂) = 520 - 1(mod 7) = 4 (do 520 x 4 mod 7 = 1).
y₃ = m₄-1(mod m₄) = 455-1(mod 8) = 7
y₄ = m₄-1(mod m₄) = 280-1(mod 13)= 2

Hệ 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.

- đừng có làm mò số to thế, chuyển sang số nhỏ hơn mà mò

ví dụ:
Y₁ = 728^-1(mod5) = 3^-1(mod5)
-->(Y₁*3)=1(mod5)
--> Y₁ = 2(mod5)

Tương tự ta có:
y₂ = m₂^-1(mod m2) = 520 ^{- 1}(mod 7) = 2 ^{- 1}(mod 7). (Do 520 = 74 * 7 + 2)
--> y₂*2 = 1(mod 7) --> y₂ = 4 (mod 7)

y₃ = m₃^-1(mod m4) = 455^-1(mod 8) = 7^-1(mod 8)
--> y₃*7 = 1 (mod 8) -- > y₃ = 7 (mod 8)

y₄ = m₄^-1(mod m4) = 280^-1(mod 13)= 7^-1(mod 13)
-->y₄*2=1 (mod 13)-->y₄ = 2 (mod 13)

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.

Đề 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.

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.]

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:
m₁ = 6
m₂ = 10
m₃ = 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 m₁ 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.

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?

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

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ố.

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 đó.

em đã hiểu rõ. cảm ơn anh nhiều nha

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

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.]

          giai cua thya hay that day

Admin đã viết:Giải hệ phương trình đồng dư:

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

Ghét ...!!! Admin ka ka. Em thích bài này