Chủ đề này có 5 trả lời

[rox_rook]

Chả là em đang đọc 1 cuốn sách vè số học của tác giả Hà Huy Khoái nhưng có vẻ do khâu in ấn cẩu thả hay sao mà cách Cm cũng như ví dụ cho kết quả em chỉ muốn xé cuốn sách, đọc mãi mà chẳng hiểu nỗi nó CM cái gì ! Mong các bạn giúp đỡ.
Định lý phát biểu như sau :

Giả sử m1, m2,m3 là các số nguyên tố cùng nhau từng cặp. Khi đó các hệ đồng dư tuyến tính :
x1 a1 ( mod m1 )
x2 a2 ( mod m2 )
x3 a3 ( mod m3 )
....
..
có nghiệm duy nhất M = m1.m2.m3....mR

Mong các bạn CM giúp mình định lý này ! Vì mình đang học về giải mã, mà cái này có liên quan đến cơ cấu cộng 2 số lớn của máy tính ! Nên nó thực sự rất cần thiết đối với mình. Mình sẽ ghi ra toàn bộ phần ví dụ mà trong cuốn sách đó để mấy bạn dễ quan sát :
Ví dụ

Tính tổng : x = 123684, y = 413456

Ta có :
x 33 ( mod 99 ) x 9 ( mod 97 )
y 32 ( mod 99 ) y 42 ( mod 97 )
x 8 ( mod 98 ) x 89 ( mod 95 )
y 92 ( mod 98 ) y 16 ( mod 95 )

Do đó :
x + y 65 ( mod 99 )
x + y 5 ( mod 98 )
x + y 51 ( mod 97 )
x + y 10 ( mod 95 )

Ta có : M = 99.98.97.95 = 89 403 930
M1 = M/99 = 903 070
M1 = M/98 = 912 285
M1 = M/97 = 921 690
M1 = M/95 = 941 094

Mặt khác, có thể tìm thấy được :
y1 37 ( mod 99 )
y1 38 ( mod 98 )
y1 24 ( mod 97 )
y1 4 ( mod 95 )

Vậy : x + y = (65 x 903070 x 37) + (2 x 912285 x 33) + (51 x 921690 x 24 ) + (10 x 941094 x 4 )
= 339 788 480
= 537 140 ( mod 89 403 930 )

Rõ ràng x + y < 89 403 930 nên ta có x + y = 537 140

END

Thiệt là không biết chắc sách nó có in sai hay mình suy luận sai mà đọc mãi không hiểu nó tính cái gì ! Mong các bạn giúp đỡ ! Cám ơn rát nhiều !

Bài viết đã được chỉnh sửa nội dung bởi rox_rook: 21-06-2007 - 13:04

[toiratthichtoan]

Cái này nếu mình nhớ không nhầm thì nó đặt $ M_{i} $ là tích của các $ m_{j} $ trừ $ m_{i} $, sau đó nó chỉ luôn ra nghiệm của cái hệ này.
(Ngày mai em sẽ post công thức tổng quát và cả hệ quả của định lý này cho)

[toiratthichtoan]

Đây rùi:

Đặt $ M_{i} = \dfrac{ m_{1} m_{2}...m_{r} }{ m_{i} } $ với i chạy từ 1 đến r.
Vì $m_{1}, m_{2},..., m_{r}$ nguyên tốt cùng nhau từng đôi mottj => $M_{i}$ không chia hết cho $m_{i}$ và $M_{i}$ $m_{i}$ với mọi i.

Xét $ M_{i}.y $ 1 (mod $ m_{i} $ có nghiệm duy nhất vì ($ M_{i} $, $ m_{i} $) = 1

=> Xét x = $ a_{1} y_{1} M_{1} + a_{2} y_{2} M_{2} + ... + a_{r} y_{r} M_{r} $, ta có $a_{1} y_{1} M_{1}$ $ m_{j} $ với i khác j.

=> x $ a_{i} $ (mod $ m_{i} $)
=> x là nghiệm của hệ.

Giả sử x' cũng là nghiệm của hệ.
=> x x' $ a_{i} $ (mod $ m_{i} $)
=> x - x' $ m_{i} $ (mọi i)
=> x x' (mod $ m_{1}m_{1}m_{1}...m_{1} $)
=> Hệ có nghiệm duy nhất theo mod $ m_{1}m_{1}m_{1}...m_{1} $

Chứng minh xong.

[Duck_Pro]

Cái này nếu mình nhớ không nhầm thì nó đặt $ M_{i} $ là tích của các $ m_{j} $ trừ $ m_{i} $, sau đó nó chỉ luôn ra nghiệm của cái hệ này.
(Ngày mai em sẽ post công thức tổng quát và cả hệ quả của định lý này cho)

Hệ quả của định lý:
Hệ đồng dư
x $ a_{1} $ (mod $ m_{1} $)
x $ a_{2} $ (mod $ m_{2} $)
x $ a_{3} $ (mod $ m_{3} $)
........
x $ a_{r} $ (mod $ m_{r} $)
có nghiệm ($ m_{i}, m_{j}$) \ $ a_{i} - a_{j} $ với mọi cặp số nguyên (i,j); 1 i j r và nếu nghiệm tồn tại thì nghiệm đó là duy nhất theo mod M = [$ m_{1} ,m_{2} ,m_{3} ,...,m_{r} $].

[nguyen duc hieu]

trời ơi sao toán cấp 2 mà toàn bài khó vậy, mình đọc sách 10 năm chưa chắc đã hiểu được mấy cái này, mà mấy cái này chắc các bạn đi học bồi dưỡng học sinh giỏi

[Duck_Pro]

Cái này là chương trình chuyên. Nói vậy thôi chứ nếu bạn đọc cẩn thận thì cũng hiểu thôi, nó dễ thôi mà. Nếu cần thì bạn có thể hỏi, mọi người sẽ trả lời hết mà. Lúc nào tui post cả chuyên đề lên cho. OK?