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

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

Đượ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 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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

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 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

Đị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

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

4

Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri May 20, 2011 8:06 am

Bài gửi : 70
Điểm : 543
Được cảm ơn : 201
Ngày gia nhập : 14/05/2011

Để 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]= 2Hệ 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]

5

Re: [Hướng dẫn]Cách giải hệ phương trình đồng dư Fri May 20, 2011 8:22 am

Bài gửi : 104
Điểm : 1674
Được cảm ơn : 382
Ngày gia nhập : 15/05/2011

- đừ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 am

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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 pm

Bài gửi : 785
Điểm : 14376
Được cảm ơn : 10442
Ngày gia nhập : 11/05/2011

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 pm

Bài gửi : 7
Điểm : 74
Được cảm ơn : 24
Ngày gia nhập : 17/07/2011

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 pm

Bài gửi : 127
Điểm : 866
Được cảm ơn : 221
Ngày gia nhập : 16/05/2011

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 pm

Bài gửi : 7
Điểm : 74
Được cảm ơn : 24
Ngày gia nhập : 17/07/2011

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 pm

Bài gửi : 10
Điểm : 115
Được cảm ơn : 19
Ngày gia nhập : 24/07/2011

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 pm

Bài gửi : 7
Điểm : 74
Được cảm ơn : 24
Ngày gia nhập : 17/07/2011

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 am

Bài gửi : 11
Điểm : 150
Được cảm ơn : 38
Ngày gia nhập : 26/07/2011

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 am

Bài gửi : 1
Điểm : 8
Được cảm ơn : 0
Ngày gia nhập : 23/12/2013

          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 am

Bài gửi : 2
Điểm : 12
Được cảm ơn : 3
Ngày gia nhập : 25/08/2013

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