Một số tự nhiên a chia cho 5 dư 3, chia cho 9 dư 4, chia cho 11 dư 1. Hỏi số a chia cho 495 dư bao nhiêu?

Để tìm số a chia cho 495 dư bao nhiêu, ta sẽ tìm số tự nhiên nhỏ nhất thỏa mãn các điều kiện đã cho và sau đó tăng lên 495 cho đến khi không còn dư.

Ta có hệ thức sau:
a ≡ 3 (mod 5)
a ≡ 4 (mod 9)
a ≡ 1 (mod 11)

Đầu tiên, ta tìm số tự nhiên nhỏ nhất thỏa mãn các điều kiện trên. Ta có thể sử dụng định lý Trung Hoa để giải hệ phương trình đồng dư này.

Gọi x là số tự nhiên nhỏ nhất thỏa mãn các điều kiện trên. Ta có:
x ≡ 3 (mod 5)
x ≡ 4 (mod 9)
x ≡ 1 (mod 11)

Áp dụng định lý Trung Hoa, ta có:
x ≡ 3 * 9 * 11 * a1 + 4 * 5 * 11 * a2 + 1 * 5 * 9 * a3 (mod 5 * 9 * 11)

Ở đây, a1, a2, a3 là các số nguyên thỏa mãn a1 * 9 * 11 + a2 * 5 * 11 + a3 * 5 * 9 = 1 (định lý Euclid mở rộng).

Tìm a1, a2, a3 bằng cách sử dụng thuật toán Euclid mở rộng:
9 * 11 * a1 + 5 * 11 * a2 + 5 * 9 * a3 = 1

Áp dụng thuật toán Euclid mở rộng, ta có:
9 * 11 * 1 + 5 * 11 * (-2) = 1

Vậy a1 = 1, a2 = -2, a3 = 1.

Thay vào công thức trên, ta có:
x ≡ 3 * 9 * 11 * 1 + 4 * 5 * 11 * (-2) + 1 * 5 * 9 * 1 (mod 5 * 9 * 11)
x ≡ 297 - 440 + 45 (mod 495)
x ≡ -98 (mod 495)

Để tìm số a chia cho 495 dư bao nhiêu, ta tăng x lên 495 cho đến khi không còn dư:
x + 495 ≡ -98 + 495 (mod 495)
x + 495 ≡ 397 (mod 495)

Vậy số a chia cho 495 dư 397.