Mình không rõ phần:
By induction on t,it suffices to prove that m1 and m2 are relatively prime,the length k of the LCG senquence determined by the parameters (X0,a,c,m1m2) is the LCM of the length k1 and k2…and (X0 mod m2 ,a mod m2,c mod m2,m2)
Bổ đề Q phần 3.2.1.2 của "The art of computer programming" (Vol.2)?
Mình không rõ phần:
Tức là quy nạp theo thừa số nguyên tố 
1, 2, 3, … thừa số.
Định nghĩa BCNN của a và b: a | m && b | m <=> BCNN(a,b) | m mà a, b nguyên tố cùng nhau nên tương đương ab | m.
X[n] = X[k] (mod m1*m2) <=> m1*m2 | (X[n] - X[k]). Vậy ta suy ra được (4).
tò mò?
Rất nhiều người đọc sẽ tự hỏi sao kì vậy Do chia hết (và chia hết cho, đương nhiên) là quan hệ thứ tự (bạn đọc chứng minh), nên a chia hết cho b tức là a “lớn hơn hoặc bằng” b và ngược lại. Vậy theo đúng định nghĩa của min thì BCNN(a, b) phải chia hết m ^^
1 Like
m1 = x1 * x2 * … * xn(Với x1,x2,…xn là các lũy thừa có cơ số nguyên tố như 2^3,5^7,…)
m2 = y1 * y2 * … * yn(Định nghĩa yn tương tự)
m = m1*m2 =x1 * x2 * … * xn * y1 * … * yn
Giả sử bổ đề đúng,khi đó:
Dãy (X0,a,c,m1m2) sẽ có length k bằng BCNN của các length k(i) của các dãy (X0 mod x1,a mod x1,c mod x1,x1);(X0 mod x2,a mod x2,c mod x2,x2);…
Nói cách khác:Nếu ta chứng minh được BCNN của các length k(i) bằng k thì bổ đề sẽ đúng!
BCNN của các giá trị k(i) bằng:
BCNN[k(x1),k(x2),…,k(xn),k(y1),…k(yn)] =
BCNN( BCNN[k(x1),…k(x2)] ; BCNN[k(y1);…;k(yn)] ) (!?)
Ta thấy BCNN[k(x1),…k(x2)] chính là length của dãy (X0 mod m1,a mod m1,c mod m1,m1)
Thật vậy:
Dãy (X0 mod m1,a mod m1,c mod m1,m1) sẽ có length u bằng BCNN của các length u(i) của các dãy [(X0 mod m1)mod x1,(a mod m1)mod x1,(c mod m1)mod x1,x1];…
(Có được từ định nghĩa m1)
Rõ ràng:(X0 mod m1) mod x1 = X0 mod x1 (Vì m1 | x1)
Ta cũng chứng minh được:
(a mod m1) mod x1 = a mod x1
(c mod m1) mod x1 = c mod x1
Tương tự với dãy (X0 mod m2,a mod m2,c mod m2,m2) (Gọi length dãy này là v)
Vậy tóm lại,ta cần chứng minh k = BCNN(u;v) để bổ đề đúng
Không biết suy luận của mình có ổn không?(Cá nhân mình thấy khá ổn,trừ chỗ mình ghi dấu (!?))
Tức là nếu ko dùng quy nạp thì xét mỗi m là đủ, thì ta cần X mod m mod x1 == X mod x1 làm sao đó để tương đương với x1 | m. Bạn áp dụng định nghĩa của phép mod xem. (à mà cũng ko tránh khỏi bước gamma = BCNN(gamma_1, gamma_2, ...) )
Dùng toán tử mod là đường vòng 
bạn phải học đồng dư thức, nó dễ lập luận hơn nhiều mod là để cho máy tính. Giống như với forEach ta không cần nhắc đến a.length và ++i gì cả viết đồng dư thức thì không cần nhắc đến thương số.
1 Like
Sách ghi proof hơi ngược nên bạn thấy khó hiểu thôi.
Ban đầu xem xét bổ để con Q1 sau (bổ đề con để chứng minh bổ đề Q):
Cho dãy random sequence Xn được xác định bởi 5 số nguyên (X0, a, c, m1m2), trong đó gcd(m1, m2) = 1.
Dãy Yn và dãy Zn được xác định như sau:
Yn = Xn mod m1
Zn = Xn mod m2
Khi đó dãy Yn là random sequence được xác định từ 4 số (X0 mod m1, a mod m1, C mod m1, m1), Zn xác định từ 4 số (X0 mod m2, a mod m2, C mod m2, m2).
Nếu l, l1, l2 lần lượt là period của Xn, Yn, Zn, chứng minh l = lcm(l1, l2).
Nội dung chứng minh trong sách là chứng minh cho Q1.
Phần còn thiếu trong sách là bước sử dụng Q1 và tính chất kết hợp của lcm để chứng minh Q bằng phương pháp quy nạp (induction) bằng cách chọn m1 và m2 trong biểu diễn thừa số nguyên tố của m.
Tính chất kết hợp (associative rule) của lcm:
lcm(lcm(a, b), c) = lcm(a, lcm(b, c)), với a, b, c là các số nguyên dương.
Ví dụ: m = p1ap2bp3cp4d.
Ban đầu, chọn m1 = p1a, m2 = p2b.
Tiếp theo, m1 = p1ap2b, m2 = p3c.
Cuối cùng, m1 = p1ap2bp3c, m2 = p4d.
4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?