Bài toán tồn tại (toán rời rạc)

[Tiger]

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]

Áp dụng định lí Bezout

[tntxtnt]

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 = q₁n + a, với q₁ là 1 số nguyên nào đó
• vì h mod m = b, h = q₂m + b, với q₂ là 1 số nguyên nào đó

Vậy q₁n + a = q₂m + b (1)

Đề bài chuyển thành chứng minh tồn tại cặp số nguyên q₁, q₂ thỏa mãn phương trình (1)

(1) tương đương với q₁n - q₂m = b - a

• Nếu a = b, ta có q₁ = m, q₂ = 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ó q₁ = x(b - a), q₂ = -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 :V

Ví dụ n = 7, m = 14, a = 3, b = 4, ta có 7q₁ + 3 = 14q₂ + 4, hay q₁ = (14q₂ + 1) / 7 = 2q₂ + 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ó q₁ = 2q₂ + 1 nên sẽ có tồn tại số h chia 7 dư 2 và chia 14 dư 9. Ví dụ h = 23 :V