Bài Toán Tồn Tại (toán Rời Rạc) - Randomq - Dạy Nhau Học

Có thể bạn quan tâm

randomqmath Tiger March 20, 2019, 1:34pm #1 Mình có bài toán rời rạc mà nghĩ mãi không ra, cao nhân nào xử giúp

Cho 2 số m, n nguyên tố cùng nhau; với mỗi (a, b) sao cho 0 ≤ a < n, 0 ≤ b < m; chứng minh: tồn tại số x chia n dư a, chia m dư b.Tiện thể mình share quyển Discrete Mathematics 7th edition của Kenneth H. Rosen mà mình tham khảo (search google là có). rogp10 (rogp10) March 20, 2019, 1:30pm #2 Áp dụng định lí Bezout

3 Likes tntxtnt (‏) March 25, 2019, 8:46am #3 Gọi h là số nguyên thỏa mãn yêu cầu đề bài.Ta có:

Vì h mod n = a, h = q1n + a, với q1 là 1 số nguyên nào đó

vì h mod m = b, h = q2m + b, với q2 là 1 số nguyên nào đó

Vậy q1n + a = q2m + b (1)Đề bài chuyển thành chứng minh tồn tại cặp số nguyên q1, q2 thỏa mãn phương trình (1)(1) tương đương với q1n - q2m = b - a

Nếu a = b, ta có q1 = m, q2 = n thỏa mãn yêu cầu đề bài

Nếu a khác b:

Theo định lý Bezout ta có: tồn tại cặp số nguyên x, y sao cho gcd(n, m) = xn + ym. Mà n, m nguyên tố cùng nhau nên tồn tại cặp số nguyên x, y sao cho xn + ym = 1 (2)
Nhân b - a là 1 số khác 0 cho 2 vế của (2) ta có: x(b - a)n + y(b - a)m = b - a.
Vậy ta có q1 = x(b - a), q2 = -y(b - a) thỏa mãn yêu cầu đề bài

Nếu m, n ko nguyên tố cùng nhau thì xn + ym = gcd(n, m) = g với g khác 1, nếu g ko chia hết cho b - a thì sẽ ko tìm được số h như vậy :VVí dụ n = 7, m = 14, a = 3, b = 4, ta có 7q1 + 3 = 14q2 + 4, hay q1 = (14q2 + 1) / 7 = 2q2 + 1/7 ko phải là số nguyên nên sẽ ko có số nào chia 7 dư 3 và chia 14 dư 4. Còn nếu a = 2, b = 9 chẳng hạn thì ta sẽ có q1 = 2q2 + 1 nên sẽ có tồn tại số h chia 7 dư 2 và chia 14 dư 9. Ví dụ h = 23 :V4 Likes