Question

[nguyen long]

Tìm số tự nhiên nhỏ nhất khi chia 3 dư 2, chia 5 dư 3, chia 7 dư 2

Answer 1

[Nguyễn Thiện Nhân]

gọi số tự nhiên đó là a ( a thuộc z)

do a chia 3 dư 2; chia 5 dư 3 => a+1 chia hết cho 3 và 5

=> a+1 thuộc bc của 3 và 5 

3=3 ; 5=5 => bcnn của 3 và 5 = 3.5=15 

                      bc của 3 và 5 thuộc {0;15;30;.....}

=> a+1 thuộc {0;15;30;...}

=> a thuộc { 14; 29;......} ( vì a thuộc N)

Mà a nhỏ nhất a chia 7 dư 2 nên a = 44 

                                                        Vậy

Answer 2

[son 101]

Ta có thể giải bài toán này bằng cách sử dụng định lý dư dấu của Trung tâm Đa dạng (Chinese Remainder Theorem).

Gọi số tự nhiên cần tìm là x. Theo yêu cầu đề bài, ta có hệ phương trình tương đương sau:

x ≡ 2 (mod 3) x ≡ 3 (mod 5) x ≡ 2 (mod 7)

Theo định lý dư dấu, hệ phương trình này có nghiệm duy nhất modulo 3x5x7 = 105.

Để tìm nghiệm của hệ phương trình, ta có thể áp dụng thuật toán quy hoạch động (Dynamic Programming) như sau:

• Đặt i = 2, và x = 2. Ta kiểm tra xem x có thỏa mãn điều kiện thứ hai (x ≡ 3 (mod 5)) không. Nếu không, ta tăng giá trị x lên 105 (vì 105 chia hết cho cả 3, 5 và 7), và quay lại bước kiểm tra. Nếu x thỏa mãn điều kiện thứ hai, ta tiếp tục đến bước tiếp theo.
• Đặt i = 3, và x = 2. Ta kiểm tra xem x có thỏa mãn điều kiện thứ ba (x ≡ 2 (mod 7)) không. Nếu không, ta tăng giá trị x lên 105, và quay lại bước kiểm tra. Nếu x thỏa mãn điều kiện thứ ba, ta đã tìm được nghiệm của hệ phương trình.

Do đó, số tự nhiên nhỏ nhất cần tìm là 2 + 3x3x7 = 65. Vì vậy, khi chia 3 dư 2, chia 5 dư 3 và chia 7 dư 2, số tự nhiên nhỏ nhất là 65.